Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pathnode.c
4 : * Routines to manipulate pathlists and create path nodes
5 : *
6 : * Portions Copyright (c) 1996-2017, 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 "miscadmin.h"
20 : #include "nodes/nodeFuncs.h"
21 : #include "optimizer/clauses.h"
22 : #include "optimizer/cost.h"
23 : #include "optimizer/pathnode.h"
24 : #include "optimizer/paths.h"
25 : #include "optimizer/planmain.h"
26 : #include "optimizer/restrictinfo.h"
27 : #include "optimizer/var.h"
28 : #include "parser/parsetree.h"
29 : #include "utils/lsyscache.h"
30 : #include "utils/selfuncs.h"
31 :
32 :
33 : typedef enum
34 : {
35 : COSTS_EQUAL, /* path costs are fuzzily equal */
36 : COSTS_BETTER1, /* first path is cheaper than second */
37 : COSTS_BETTER2, /* second path is cheaper than first */
38 : COSTS_DIFFERENT /* neither path dominates the other on cost */
39 : } PathCostComparison;
40 :
41 : /*
42 : * STD_FUZZ_FACTOR is the normal fuzz factor for compare_path_costs_fuzzily.
43 : * XXX is it worth making this user-controllable? It provides a tradeoff
44 : * between planner runtime and the accuracy of path cost comparisons.
45 : */
46 : #define STD_FUZZ_FACTOR 1.01
47 :
48 : static List *translate_sub_tlist(List *tlist, int relid);
49 :
50 :
51 : /*****************************************************************************
52 : * MISC. PATH UTILITIES
53 : *****************************************************************************/
54 :
55 : /*
56 : * compare_path_costs
57 : * Return -1, 0, or +1 according as path1 is cheaper, the same cost,
58 : * or more expensive than path2 for the specified criterion.
59 : */
60 : int
61 14257 : compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
62 : {
63 14257 : if (criterion == STARTUP_COST)
64 : {
65 6955 : if (path1->startup_cost < path2->startup_cost)
66 4821 : return -1;
67 2134 : if (path1->startup_cost > path2->startup_cost)
68 1491 : return +1;
69 :
70 : /*
71 : * If paths have the same startup cost (not at all unlikely), order
72 : * them by total cost.
73 : */
74 643 : if (path1->total_cost < path2->total_cost)
75 466 : return -1;
76 177 : if (path1->total_cost > path2->total_cost)
77 0 : return +1;
78 : }
79 : else
80 : {
81 7302 : if (path1->total_cost < path2->total_cost)
82 7120 : return -1;
83 182 : if (path1->total_cost > path2->total_cost)
84 22 : return +1;
85 :
86 : /*
87 : * If paths have the same total cost, order them by startup cost.
88 : */
89 160 : if (path1->startup_cost < path2->startup_cost)
90 0 : return -1;
91 160 : if (path1->startup_cost > path2->startup_cost)
92 0 : return +1;
93 : }
94 337 : return 0;
95 : }
96 :
97 : /*
98 : * compare_path_fractional_costs
99 : * Return -1, 0, or +1 according as path1 is cheaper, the same cost,
100 : * or more expensive than path2 for fetching the specified fraction
101 : * of the total tuples.
102 : *
103 : * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
104 : * path with the cheaper total_cost.
105 : */
106 : int
107 195 : compare_fractional_path_costs(Path *path1, Path *path2,
108 : double fraction)
109 : {
110 : Cost cost1,
111 : cost2;
112 :
113 195 : if (fraction <= 0.0 || fraction >= 1.0)
114 131 : return compare_path_costs(path1, path2, TOTAL_COST);
115 192 : cost1 = path1->startup_cost +
116 128 : fraction * (path1->total_cost - path1->startup_cost);
117 192 : cost2 = path2->startup_cost +
118 128 : fraction * (path2->total_cost - path2->startup_cost);
119 64 : if (cost1 < cost2)
120 28 : return -1;
121 36 : if (cost1 > cost2)
122 36 : return +1;
123 0 : return 0;
124 : }
125 :
126 : /*
127 : * compare_path_costs_fuzzily
128 : * Compare the costs of two paths to see if either can be said to
129 : * dominate the other.
130 : *
131 : * We use fuzzy comparisons so that add_path() can avoid keeping both of
132 : * a pair of paths that really have insignificantly different cost.
133 : *
134 : * The fuzz_factor argument must be 1.0 plus delta, where delta is the
135 : * fraction of the smaller cost that is considered to be a significant
136 : * difference. For example, fuzz_factor = 1.01 makes the fuzziness limit
137 : * be 1% of the smaller cost.
138 : *
139 : * The two paths are said to have "equal" costs if both startup and total
140 : * costs are fuzzily the same. Path1 is said to be better than path2 if
141 : * it has fuzzily better startup cost and fuzzily no worse total cost,
142 : * or if it has fuzzily better total cost and fuzzily no worse startup cost.
143 : * Path2 is better than path1 if the reverse holds. Finally, if one path
144 : * is fuzzily better than the other on startup cost and fuzzily worse on
145 : * total cost, we just say that their costs are "different", since neither
146 : * dominates the other across the whole performance spectrum.
147 : *
148 : * This function also enforces a policy rule that paths for which the relevant
149 : * one of parent->consider_startup and parent->consider_param_startup is false
150 : * cannot survive comparisons solely on the grounds of good startup cost, so
151 : * we never return COSTS_DIFFERENT when that is true for the total-cost loser.
152 : * (But if total costs are fuzzily equal, we compare startup costs anyway,
153 : * in hopes of eliminating one path or the other.)
154 : */
155 : static PathCostComparison
156 83465 : compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor)
157 : {
158 : #define CONSIDER_PATH_STARTUP_COST(p) \
159 : ((p)->param_info == NULL ? (p)->parent->consider_startup : (p)->parent->consider_param_startup)
160 :
161 : /*
162 : * Check total cost first since it's more likely to be different; many
163 : * paths have zero startup cost.
164 : */
165 83465 : if (path1->total_cost > path2->total_cost * fuzz_factor)
166 : {
167 : /* path1 fuzzily worse on total cost */
168 40426 : if (CONSIDER_PATH_STARTUP_COST(path1) &&
169 1000 : path2->startup_cost > path1->startup_cost * fuzz_factor)
170 : {
171 : /* ... but path2 fuzzily worse on startup, so DIFFERENT */
172 201 : return COSTS_DIFFERENT;
173 : }
174 : /* else path2 dominates */
175 39225 : return COSTS_BETTER2;
176 : }
177 44039 : if (path2->total_cost > path1->total_cost * fuzz_factor)
178 : {
179 : /* path2 fuzzily worse on total cost */
180 24293 : if (CONSIDER_PATH_STARTUP_COST(path2) &&
181 290 : path1->startup_cost > path2->startup_cost * fuzz_factor)
182 : {
183 : /* ... but path1 fuzzily worse on startup, so DIFFERENT */
184 184 : return COSTS_DIFFERENT;
185 : }
186 : /* else path1 dominates */
187 23819 : return COSTS_BETTER1;
188 : }
189 : /* fuzzily the same on total cost ... */
190 20036 : if (path1->startup_cost > path2->startup_cost * fuzz_factor)
191 : {
192 : /* ... but path1 fuzzily worse on startup, so path2 wins */
193 8093 : return COSTS_BETTER2;
194 : }
195 11943 : if (path2->startup_cost > path1->startup_cost * fuzz_factor)
196 : {
197 : /* ... but path2 fuzzily worse on startup, so path1 wins */
198 1418 : return COSTS_BETTER1;
199 : }
200 : /* fuzzily the same on both costs */
201 10525 : return COSTS_EQUAL;
202 :
203 : #undef CONSIDER_PATH_STARTUP_COST
204 : }
205 :
206 : /*
207 : * set_cheapest
208 : * Find the minimum-cost paths from among a relation's paths,
209 : * and save them in the rel's cheapest-path fields.
210 : *
211 : * cheapest_total_path is normally the cheapest-total-cost unparameterized
212 : * path; but if there are no unparameterized paths, we assign it to be the
213 : * best (cheapest least-parameterized) parameterized path. However, only
214 : * unparameterized paths are considered candidates for cheapest_startup_path,
215 : * so that will be NULL if there are no unparameterized paths.
216 : *
217 : * The cheapest_parameterized_paths list collects all parameterized paths
218 : * that have survived the add_path() tournament for this relation. (Since
219 : * add_path ignores pathkeys for a parameterized path, these will be paths
220 : * that have best cost or best row count for their parameterization. We
221 : * may also have both a parallel-safe and a non-parallel-safe path in some
222 : * cases for the same parameterization in some cases, but this should be
223 : * relatively rare since, most typically, all paths for the same relation
224 : * will be parallel-safe or none of them will.)
225 : *
226 : * cheapest_parameterized_paths always includes the cheapest-total
227 : * unparameterized path, too, if there is one; the users of that list find
228 : * it more convenient if that's included.
229 : *
230 : * This is normally called only after we've finished constructing the path
231 : * list for the rel node.
232 : */
233 : void
234 63973 : set_cheapest(RelOptInfo *parent_rel)
235 : {
236 : Path *cheapest_startup_path;
237 : Path *cheapest_total_path;
238 : Path *best_param_path;
239 : List *parameterized_paths;
240 : ListCell *p;
241 :
242 63973 : Assert(IsA(parent_rel, RelOptInfo));
243 :
244 63973 : if (parent_rel->pathlist == NIL)
245 0 : elog(ERROR, "could not devise a query plan for the given query");
246 :
247 63973 : cheapest_startup_path = cheapest_total_path = best_param_path = NULL;
248 63973 : parameterized_paths = NIL;
249 :
250 138105 : foreach(p, parent_rel->pathlist)
251 : {
252 74132 : Path *path = (Path *) lfirst(p);
253 : int cmp;
254 :
255 74132 : if (path->param_info)
256 : {
257 : /* Parameterized path, so add it to parameterized_paths */
258 3702 : parameterized_paths = lappend(parameterized_paths, path);
259 :
260 : /*
261 : * If we have an unparameterized cheapest-total, we no longer care
262 : * about finding the best parameterized path, so move on.
263 : */
264 3702 : if (cheapest_total_path)
265 490 : continue;
266 :
267 : /*
268 : * Otherwise, track the best parameterized path, which is the one
269 : * with least total cost among those of the minimum
270 : * parameterization.
271 : */
272 3212 : if (best_param_path == NULL)
273 2985 : best_param_path = path;
274 : else
275 : {
276 454 : switch (bms_subset_compare(PATH_REQ_OUTER(path),
277 454 : PATH_REQ_OUTER(best_param_path)))
278 : {
279 : case BMS_EQUAL:
280 : /* keep the cheaper one */
281 0 : if (compare_path_costs(path, best_param_path,
282 : TOTAL_COST) < 0)
283 0 : best_param_path = path;
284 0 : break;
285 : case BMS_SUBSET1:
286 : /* new path is less-parameterized */
287 13 : best_param_path = path;
288 13 : break;
289 : case BMS_SUBSET2:
290 : /* old path is less-parameterized, keep it */
291 0 : break;
292 : case BMS_DIFFERENT:
293 :
294 : /*
295 : * This means that neither path has the least possible
296 : * parameterization for the rel. We'll sit on the old
297 : * path until something better comes along.
298 : */
299 214 : break;
300 : }
301 : }
302 : }
303 : else
304 : {
305 : /* Unparameterized path, so consider it for cheapest slots */
306 70430 : if (cheapest_total_path == NULL)
307 : {
308 63791 : cheapest_startup_path = cheapest_total_path = path;
309 63791 : continue;
310 : }
311 :
312 : /*
313 : * If we find two paths of identical costs, try to keep the
314 : * better-sorted one. The paths might have unrelated sort
315 : * orderings, in which case we can only guess which might be
316 : * better to keep, but if one is superior then we definitely
317 : * should keep that one.
318 : */
319 6639 : cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
320 6639 : if (cmp > 0 ||
321 8 : (cmp == 0 &&
322 8 : compare_pathkeys(cheapest_startup_path->pathkeys,
323 : path->pathkeys) == PATHKEYS_BETTER2))
324 1467 : cheapest_startup_path = path;
325 :
326 6639 : cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST);
327 6639 : if (cmp > 0 ||
328 0 : (cmp == 0 &&
329 0 : compare_pathkeys(cheapest_total_path->pathkeys,
330 : path->pathkeys) == PATHKEYS_BETTER2))
331 0 : cheapest_total_path = path;
332 : }
333 : }
334 :
335 : /* Add cheapest unparameterized path, if any, to parameterized_paths */
336 63973 : if (cheapest_total_path)
337 63791 : parameterized_paths = lcons(cheapest_total_path, parameterized_paths);
338 :
339 : /*
340 : * If there is no unparameterized path, use the best parameterized path as
341 : * cheapest_total_path (but not as cheapest_startup_path).
342 : */
343 63973 : if (cheapest_total_path == NULL)
344 182 : cheapest_total_path = best_param_path;
345 63973 : Assert(cheapest_total_path != NULL);
346 :
347 63973 : parent_rel->cheapest_startup_path = cheapest_startup_path;
348 63973 : parent_rel->cheapest_total_path = cheapest_total_path;
349 63973 : parent_rel->cheapest_unique_path = NULL; /* computed only if needed */
350 63973 : parent_rel->cheapest_parameterized_paths = parameterized_paths;
351 63973 : }
352 :
353 : /*
354 : * add_path
355 : * Consider a potential implementation path for the specified parent rel,
356 : * and add it to the rel's pathlist if it is worthy of consideration.
357 : * A path is worthy if it has a better sort order (better pathkeys) or
358 : * cheaper cost (on either dimension), or generates fewer rows, than any
359 : * existing path that has the same or superset parameterization rels.
360 : * We also consider parallel-safe paths more worthy than others.
361 : *
362 : * We also remove from the rel's pathlist any old paths that are dominated
363 : * by new_path --- that is, new_path is cheaper, at least as well ordered,
364 : * generates no more rows, requires no outer rels not required by the old
365 : * path, and is no less parallel-safe.
366 : *
367 : * In most cases, a path with a superset parameterization will generate
368 : * fewer rows (since it has more join clauses to apply), so that those two
369 : * figures of merit move in opposite directions; this means that a path of
370 : * one parameterization can seldom dominate a path of another. But such
371 : * cases do arise, so we make the full set of checks anyway.
372 : *
373 : * There are two policy decisions embedded in this function, along with
374 : * its sibling add_path_precheck. First, we treat all parameterized paths
375 : * as having NIL pathkeys, so that they cannot win comparisons on the
376 : * basis of sort order. This is to reduce the number of parameterized
377 : * paths that are kept; see discussion in src/backend/optimizer/README.
378 : *
379 : * Second, we only consider cheap startup cost to be interesting if
380 : * parent_rel->consider_startup is true for an unparameterized path, or
381 : * parent_rel->consider_param_startup is true for a parameterized one.
382 : * Again, this allows discarding useless paths sooner.
383 : *
384 : * The pathlist is kept sorted by total_cost, with cheaper paths
385 : * at the front. Within this routine, that's simply a speed hack:
386 : * doing it that way makes it more likely that we will reject an inferior
387 : * path after a few comparisons, rather than many comparisons.
388 : * However, add_path_precheck relies on this ordering to exit early
389 : * when possible.
390 : *
391 : * NOTE: discarded Path objects are immediately pfree'd to reduce planner
392 : * memory consumption. We dare not try to free the substructure of a Path,
393 : * since much of it may be shared with other Paths or the query tree itself;
394 : * but just recycling discarded Path nodes is a very useful savings in
395 : * a large join tree. We can recycle the List nodes of pathlist, too.
396 : *
397 : * As noted in optimizer/README, deleting a previously-accepted Path is
398 : * safe because we know that Paths of this rel cannot yet be referenced
399 : * from any other rel, such as a higher-level join. However, in some cases
400 : * it is possible that a Path is referenced by another Path for its own
401 : * rel; we must not delete such a Path, even if it is dominated by the new
402 : * Path. Currently this occurs only for IndexPath objects, which may be
403 : * referenced as children of BitmapHeapPaths as well as being paths in
404 : * their own right. Hence, we don't pfree IndexPaths when rejecting them.
405 : *
406 : * 'parent_rel' is the relation entry to which the path corresponds.
407 : * 'new_path' is a potential path for parent_rel.
408 : *
409 : * Returns nothing, but modifies parent_rel->pathlist.
410 : */
411 : void
412 127865 : add_path(RelOptInfo *parent_rel, Path *new_path)
413 : {
414 127865 : bool accept_new = true; /* unless we find a superior old path */
415 127865 : ListCell *insert_after = NULL; /* where to insert new item */
416 : List *new_path_pathkeys;
417 : ListCell *p1;
418 : ListCell *p1_prev;
419 : ListCell *p1_next;
420 :
421 : /*
422 : * This is a convenient place to check for query cancel --- no part of the
423 : * planner goes very long without calling add_path().
424 : */
425 127865 : CHECK_FOR_INTERRUPTS();
426 :
427 : /* Pretend parameterized paths have no pathkeys, per comment above */
428 127865 : new_path_pathkeys = new_path->param_info ? NIL : new_path->pathkeys;
429 :
430 : /*
431 : * Loop to check proposed new path against old paths. Note it is possible
432 : * for more than one old path to be tossed out because new_path dominates
433 : * it.
434 : *
435 : * We can't use foreach here because the loop body may delete the current
436 : * list cell.
437 : */
438 127865 : p1_prev = NULL;
439 168319 : for (p1 = list_head(parent_rel->pathlist); p1 != NULL; p1 = p1_next)
440 : {
441 76095 : Path *old_path = (Path *) lfirst(p1);
442 76095 : bool remove_old = false; /* unless new proves superior */
443 : PathCostComparison costcmp;
444 : PathKeysComparison keyscmp;
445 : BMS_Comparison outercmp;
446 :
447 76095 : p1_next = lnext(p1);
448 :
449 : /*
450 : * Do a fuzzy cost comparison with standard fuzziness limit.
451 : */
452 76095 : costcmp = compare_path_costs_fuzzily(new_path, old_path,
453 : STD_FUZZ_FACTOR);
454 :
455 : /*
456 : * If the two paths compare differently for startup and total cost,
457 : * then we want to keep both, and we can skip comparing pathkeys and
458 : * required_outer rels. If they compare the same, proceed with the
459 : * other comparisons. Row count is checked last. (We make the tests
460 : * in this order because the cost comparison is most likely to turn
461 : * out "different", and the pathkeys comparison next most likely. As
462 : * explained above, row count very seldom makes a difference, so even
463 : * though it's cheap to compare there's not much point in checking it
464 : * earlier.)
465 : */
466 76095 : if (costcmp != COSTS_DIFFERENT)
467 : {
468 : /* Similarly check to see if either dominates on pathkeys */
469 : List *old_path_pathkeys;
470 :
471 75710 : old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
472 75710 : keyscmp = compare_pathkeys(new_path_pathkeys,
473 : old_path_pathkeys);
474 75710 : if (keyscmp != PATHKEYS_DIFFERENT)
475 : {
476 74869 : switch (costcmp)
477 : {
478 : case COSTS_EQUAL:
479 7877 : outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
480 7877 : PATH_REQ_OUTER(old_path));
481 7791 : if (keyscmp == PATHKEYS_BETTER1)
482 : {
483 33 : if ((outercmp == BMS_EQUAL ||
484 33 : outercmp == BMS_SUBSET1) &&
485 66 : new_path->rows <= old_path->rows &&
486 33 : new_path->parallel_safe >= old_path->parallel_safe)
487 33 : remove_old = true; /* new dominates old */
488 : }
489 7758 : else if (keyscmp == PATHKEYS_BETTER2)
490 : {
491 321 : if ((outercmp == BMS_EQUAL ||
492 321 : outercmp == BMS_SUBSET2) &&
493 642 : new_path->rows >= old_path->rows &&
494 321 : new_path->parallel_safe <= old_path->parallel_safe)
495 321 : accept_new = false; /* old dominates new */
496 : }
497 : else /* keyscmp == PATHKEYS_EQUAL */
498 : {
499 7437 : if (outercmp == BMS_EQUAL)
500 : {
501 : /*
502 : * Same pathkeys and outer rels, and fuzzily
503 : * the same cost, so keep just one; to decide
504 : * which, first check parallel-safety, then
505 : * rows, then do a fuzzy cost comparison with
506 : * very small fuzz limit. (We used to do an
507 : * exact cost comparison, but that results in
508 : * annoying platform-specific plan variations
509 : * due to roundoff in the cost estimates.) If
510 : * things are still tied, arbitrarily keep
511 : * only the old path. Notice that we will
512 : * keep only the old path even if the
513 : * less-fuzzy comparison decides the startup
514 : * and total costs compare differently.
515 : */
516 14760 : if (new_path->parallel_safe >
517 7380 : old_path->parallel_safe)
518 2 : remove_old = true; /* new dominates old */
519 14756 : else if (new_path->parallel_safe <
520 7378 : old_path->parallel_safe)
521 8 : accept_new = false; /* old dominates new */
522 7370 : else if (new_path->rows < old_path->rows)
523 0 : remove_old = true; /* new dominates old */
524 7370 : else if (new_path->rows > old_path->rows)
525 0 : accept_new = false; /* old dominates new */
526 7370 : else if (compare_path_costs_fuzzily(new_path,
527 : old_path,
528 : 1.0000000001) == COSTS_BETTER1)
529 574 : remove_old = true; /* new dominates old */
530 : else
531 6796 : accept_new = false; /* old equals or
532 : * dominates new */
533 : }
534 58 : else if (outercmp == BMS_SUBSET1 &&
535 2 : new_path->rows <= old_path->rows &&
536 1 : new_path->parallel_safe >= old_path->parallel_safe)
537 1 : remove_old = true; /* new dominates old */
538 101 : else if (outercmp == BMS_SUBSET2 &&
539 90 : new_path->rows >= old_path->rows &&
540 45 : new_path->parallel_safe <= old_path->parallel_safe)
541 45 : accept_new = false; /* old dominates new */
542 : /* else different parameterizations, keep both */
543 : }
544 7791 : break;
545 : case COSTS_BETTER1:
546 24549 : if (keyscmp != PATHKEYS_BETTER2)
547 : {
548 18276 : outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
549 18276 : PATH_REQ_OUTER(old_path));
550 17778 : if ((outercmp == BMS_EQUAL ||
551 14848 : outercmp == BMS_SUBSET1) &&
552 29672 : new_path->rows <= old_path->rows &&
553 14824 : new_path->parallel_safe >= old_path->parallel_safe)
554 14775 : remove_old = true; /* new dominates old */
555 : }
556 24549 : break;
557 : case COSTS_BETTER2:
558 42529 : if (keyscmp != PATHKEYS_BETTER1)
559 : {
560 37687 : outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
561 37687 : PATH_REQ_OUTER(old_path));
562 31954 : if ((outercmp == BMS_EQUAL ||
563 29664 : outercmp == BMS_SUBSET2) &&
564 58298 : new_path->rows >= old_path->rows &&
565 28634 : new_path->parallel_safe <= old_path->parallel_safe)
566 28471 : accept_new = false; /* old dominates new */
567 : }
568 42529 : break;
569 : case COSTS_DIFFERENT:
570 :
571 : /*
572 : * can't get here, but keep this case to keep compiler
573 : * quiet
574 : */
575 0 : break;
576 : }
577 : }
578 : }
579 :
580 : /*
581 : * Remove current element from pathlist if dominated by new.
582 : */
583 76095 : if (remove_old)
584 : {
585 15385 : parent_rel->pathlist = list_delete_cell(parent_rel->pathlist,
586 : p1, p1_prev);
587 :
588 : /*
589 : * Delete the data pointed-to by the deleted cell, if possible
590 : */
591 15385 : if (!IsA(old_path, IndexPath))
592 14615 : pfree(old_path);
593 : /* p1_prev does not advance */
594 : }
595 : else
596 : {
597 : /* new belongs after this old path if it has cost >= old's */
598 60710 : if (new_path->total_cost >= old_path->total_cost)
599 49301 : insert_after = p1;
600 : /* p1_prev advances */
601 60710 : p1_prev = p1;
602 : }
603 :
604 : /*
605 : * If we found an old path that dominates new_path, we can quit
606 : * scanning the pathlist; we will not add new_path, and we assume
607 : * new_path cannot dominate any other elements of the pathlist.
608 : */
609 76095 : if (!accept_new)
610 35641 : break;
611 : }
612 :
613 127865 : if (accept_new)
614 : {
615 : /* Accept the new path: insert it at proper place in pathlist */
616 92224 : if (insert_after)
617 8994 : lappend_cell(parent_rel->pathlist, insert_after, new_path);
618 : else
619 83230 : parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
620 : }
621 : else
622 : {
623 : /* Reject and recycle the new path */
624 35641 : if (!IsA(new_path, IndexPath))
625 32576 : pfree(new_path);
626 : }
627 127865 : }
628 :
629 : /*
630 : * add_path_precheck
631 : * Check whether a proposed new path could possibly get accepted.
632 : * We assume we know the path's pathkeys and parameterization accurately,
633 : * and have lower bounds for its costs.
634 : *
635 : * Note that we do not know the path's rowcount, since getting an estimate for
636 : * that is too expensive to do before prechecking. We assume here that paths
637 : * of a superset parameterization will generate fewer rows; if that holds,
638 : * then paths with different parameterizations cannot dominate each other
639 : * and so we can simply ignore existing paths of another parameterization.
640 : * (In the infrequent cases where that rule of thumb fails, add_path will
641 : * get rid of the inferior path.)
642 : *
643 : * At the time this is called, we haven't actually built a Path structure,
644 : * so the required information has to be passed piecemeal.
645 : */
646 : bool
647 82371 : add_path_precheck(RelOptInfo *parent_rel,
648 : Cost startup_cost, Cost total_cost,
649 : List *pathkeys, Relids required_outer)
650 : {
651 : List *new_path_pathkeys;
652 : bool consider_startup;
653 : ListCell *p1;
654 :
655 : /* Pretend parameterized paths have no pathkeys, per add_path policy */
656 82371 : new_path_pathkeys = required_outer ? NIL : pathkeys;
657 :
658 : /* Decide whether new path's startup cost is interesting */
659 82371 : consider_startup = required_outer ? parent_rel->consider_param_startup : parent_rel->consider_startup;
660 :
661 95025 : foreach(p1, parent_rel->pathlist)
662 : {
663 88634 : Path *old_path = (Path *) lfirst(p1);
664 : PathKeysComparison keyscmp;
665 :
666 : /*
667 : * We are looking for an old_path with the same parameterization (and
668 : * by assumption the same rowcount) that dominates the new path on
669 : * pathkeys as well as both cost metrics. If we find one, we can
670 : * reject the new path.
671 : *
672 : * Cost comparisons here should match compare_path_costs_fuzzily.
673 : */
674 88634 : if (total_cost > old_path->total_cost * STD_FUZZ_FACTOR)
675 : {
676 : /* new path can win on startup cost only if consider_startup */
677 55582 : if (startup_cost > old_path->startup_cost * STD_FUZZ_FACTOR ||
678 : !consider_startup)
679 : {
680 : /* new path loses on cost, so check pathkeys... */
681 : List *old_path_pathkeys;
682 :
683 55488 : old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
684 55488 : keyscmp = compare_pathkeys(new_path_pathkeys,
685 : old_path_pathkeys);
686 55488 : if (keyscmp == PATHKEYS_EQUAL ||
687 : keyscmp == PATHKEYS_BETTER2)
688 : {
689 : /* new path does not win on pathkeys... */
690 44587 : if (bms_equal(required_outer, PATH_REQ_OUTER(old_path)))
691 : {
692 : /* Found an old path that dominates the new one */
693 42928 : return false;
694 : }
695 : }
696 : }
697 : }
698 : else
699 : {
700 : /*
701 : * Since the pathlist is sorted by total_cost, we can stop looking
702 : * once we reach a path with a total_cost larger than the new
703 : * path's.
704 : */
705 33052 : break;
706 : }
707 : }
708 :
709 39443 : return true;
710 : }
711 :
712 : /*
713 : * add_partial_path
714 : * Like add_path, our goal here is to consider whether a path is worthy
715 : * of being kept around, but the considerations here are a bit different.
716 : * A partial path is one which can be executed in any number of workers in
717 : * parallel such that each worker will generate a subset of the path's
718 : * overall result.
719 : *
720 : * As in add_path, the partial_pathlist is kept sorted with the cheapest
721 : * total path in front. This is depended on by multiple places, which
722 : * just take the front entry as the cheapest path without searching.
723 : *
724 : * We don't generate parameterized partial paths for several reasons. Most
725 : * importantly, they're not safe to execute, because there's nothing to
726 : * make sure that a parallel scan within the parameterized portion of the
727 : * plan is running with the same value in every worker at the same time.
728 : * Fortunately, it seems unlikely to be worthwhile anyway, because having
729 : * each worker scan the entire outer relation and a subset of the inner
730 : * relation will generally be a terrible plan. The inner (parameterized)
731 : * side of the plan will be small anyway. There could be rare cases where
732 : * this wins big - e.g. if join order constraints put a 1-row relation on
733 : * the outer side of the topmost join with a parameterized plan on the inner
734 : * side - but we'll have to be content not to handle such cases until
735 : * somebody builds an executor infrastructure that can cope with them.
736 : *
737 : * Because we don't consider parameterized paths here, we also don't
738 : * need to consider the row counts as a measure of quality: every path will
739 : * produce the same number of rows. Neither do we need to consider startup
740 : * costs: parallelism is only used for plans that will be run to completion.
741 : * Therefore, this routine is much simpler than add_path: it needs to
742 : * consider only pathkeys and total cost.
743 : *
744 : * As with add_path, we pfree paths that are found to be dominated by
745 : * another partial path; this requires that there be no other references to
746 : * such paths yet. Hence, GatherPaths must not be created for a rel until
747 : * we're done creating all partial paths for it. Unlike add_path, we don't
748 : * take an exception for IndexPaths as partial index paths won't be
749 : * referenced by partial BitmapHeapPaths.
750 : */
751 : void
752 1354 : add_partial_path(RelOptInfo *parent_rel, Path *new_path)
753 : {
754 1354 : bool accept_new = true; /* unless we find a superior old path */
755 1354 : ListCell *insert_after = NULL; /* where to insert new item */
756 : ListCell *p1;
757 : ListCell *p1_prev;
758 : ListCell *p1_next;
759 :
760 : /* Check for query cancel. */
761 1354 : CHECK_FOR_INTERRUPTS();
762 :
763 : /*
764 : * As in add_path, throw out any paths which are dominated by the new
765 : * path, but throw out the new path if some existing path dominates it.
766 : */
767 1354 : p1_prev = NULL;
768 2895 : for (p1 = list_head(parent_rel->partial_pathlist); p1 != NULL;
769 187 : p1 = p1_next)
770 : {
771 439 : Path *old_path = (Path *) lfirst(p1);
772 439 : bool remove_old = false; /* unless new proves superior */
773 : PathKeysComparison keyscmp;
774 :
775 439 : p1_next = lnext(p1);
776 :
777 : /* Compare pathkeys. */
778 439 : keyscmp = compare_pathkeys(new_path->pathkeys, old_path->pathkeys);
779 :
780 : /* Unless pathkeys are incompable, keep just one of the two paths. */
781 439 : if (keyscmp != PATHKEYS_DIFFERENT)
782 : {
783 439 : if (new_path->total_cost > old_path->total_cost * STD_FUZZ_FACTOR)
784 : {
785 : /* New path costs more; keep it only if pathkeys are better. */
786 328 : if (keyscmp != PATHKEYS_BETTER1)
787 239 : accept_new = false;
788 : }
789 111 : else if (old_path->total_cost > new_path->total_cost
790 : * STD_FUZZ_FACTOR)
791 : {
792 : /* Old path costs more; keep it only if pathkeys are better. */
793 96 : if (keyscmp != PATHKEYS_BETTER2)
794 81 : remove_old = true;
795 : }
796 15 : else if (keyscmp == PATHKEYS_BETTER1)
797 : {
798 : /* Costs are about the same, new path has better pathkeys. */
799 0 : remove_old = true;
800 : }
801 15 : else if (keyscmp == PATHKEYS_BETTER2)
802 : {
803 : /* Costs are about the same, old path has better pathkeys. */
804 4 : accept_new = false;
805 : }
806 11 : else if (old_path->total_cost > new_path->total_cost * 1.0000000001)
807 : {
808 : /* Pathkeys are the same, and the old path costs more. */
809 2 : remove_old = true;
810 : }
811 : else
812 : {
813 : /*
814 : * Pathkeys are the same, and new path isn't materially
815 : * cheaper.
816 : */
817 9 : accept_new = false;
818 : }
819 : }
820 :
821 : /*
822 : * Remove current element from partial_pathlist if dominated by new.
823 : */
824 439 : if (remove_old)
825 : {
826 83 : parent_rel->partial_pathlist =
827 83 : list_delete_cell(parent_rel->partial_pathlist, p1, p1_prev);
828 83 : pfree(old_path);
829 : /* p1_prev does not advance */
830 : }
831 : else
832 : {
833 : /* new belongs after this old path if it has cost >= old's */
834 356 : if (new_path->total_cost >= old_path->total_cost)
835 337 : insert_after = p1;
836 : /* p1_prev advances */
837 356 : p1_prev = p1;
838 : }
839 :
840 : /*
841 : * If we found an old path that dominates new_path, we can quit
842 : * scanning the partial_pathlist; we will not add new_path, and we
843 : * assume new_path cannot dominate any later path.
844 : */
845 439 : if (!accept_new)
846 252 : break;
847 : }
848 :
849 1354 : if (accept_new)
850 : {
851 : /* Accept the new path: insert it at proper place */
852 1102 : if (insert_after)
853 87 : lappend_cell(parent_rel->partial_pathlist, insert_after, new_path);
854 : else
855 1015 : parent_rel->partial_pathlist =
856 1015 : lcons(new_path, parent_rel->partial_pathlist);
857 : }
858 : else
859 : {
860 : /* Reject and recycle the new path */
861 252 : pfree(new_path);
862 : }
863 1354 : }
864 :
865 : /*
866 : * add_partial_path_precheck
867 : * Check whether a proposed new partial path could possibly get accepted.
868 : *
869 : * Unlike add_path_precheck, we can ignore startup cost and parameterization,
870 : * since they don't matter for partial paths (see add_partial_path). But
871 : * we do want to make sure we don't add a partial path if there's already
872 : * a complete path that dominates it, since in that case the proposed path
873 : * is surely a loser.
874 : */
875 : bool
876 95 : add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost,
877 : List *pathkeys)
878 : {
879 : ListCell *p1;
880 :
881 : /*
882 : * Our goal here is twofold. First, we want to find out whether this path
883 : * is clearly inferior to some existing partial path. If so, we want to
884 : * reject it immediately. Second, we want to find out whether this path
885 : * is clearly superior to some existing partial path -- at least, modulo
886 : * final cost computations. If so, we definitely want to consider it.
887 : *
888 : * Unlike add_path(), we always compare pathkeys here. This is because we
889 : * expect partial_pathlist to be very short, and getting a definitive
890 : * answer at this stage avoids the need to call add_path_precheck.
891 : */
892 99 : foreach(p1, parent_rel->partial_pathlist)
893 : {
894 73 : Path *old_path = (Path *) lfirst(p1);
895 : PathKeysComparison keyscmp;
896 :
897 73 : keyscmp = compare_pathkeys(pathkeys, old_path->pathkeys);
898 73 : if (keyscmp != PATHKEYS_DIFFERENT)
899 : {
900 73 : if (total_cost > old_path->total_cost * STD_FUZZ_FACTOR &&
901 : keyscmp != PATHKEYS_BETTER1)
902 23 : return false;
903 50 : if (old_path->total_cost > total_cost * STD_FUZZ_FACTOR &&
904 : keyscmp != PATHKEYS_BETTER2)
905 46 : return true;
906 : }
907 : }
908 :
909 : /*
910 : * This path is neither clearly inferior to an existing partial path nor
911 : * clearly good enough that it might replace one. Compare it to
912 : * non-parallel plans. If it loses even before accounting for the cost of
913 : * the Gather node, we should definitely reject it.
914 : *
915 : * Note that we pass the total_cost to add_path_precheck twice. This is
916 : * because it's never advantageous to consider the startup cost of a
917 : * partial path; the resulting plans, if run in parallel, will be run to
918 : * completion.
919 : */
920 26 : if (!add_path_precheck(parent_rel, total_cost, total_cost, pathkeys,
921 : NULL))
922 2 : return false;
923 :
924 24 : return true;
925 : }
926 :
927 :
928 : /*****************************************************************************
929 : * PATH NODE CREATION ROUTINES
930 : *****************************************************************************/
931 :
932 : /*
933 : * create_seqscan_path
934 : * Creates a path corresponding to a sequential scan, returning the
935 : * pathnode.
936 : */
937 : Path *
938 16159 : create_seqscan_path(PlannerInfo *root, RelOptInfo *rel,
939 : Relids required_outer, int parallel_workers)
940 : {
941 16159 : Path *pathnode = makeNode(Path);
942 :
943 16159 : pathnode->pathtype = T_SeqScan;
944 16159 : pathnode->parent = rel;
945 16159 : pathnode->pathtarget = rel->reltarget;
946 16159 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
947 : required_outer);
948 16159 : pathnode->parallel_aware = parallel_workers > 0 ? true : false;
949 16159 : pathnode->parallel_safe = rel->consider_parallel;
950 16159 : pathnode->parallel_workers = parallel_workers;
951 16159 : pathnode->pathkeys = NIL; /* seqscan has unordered result */
952 :
953 16159 : cost_seqscan(pathnode, root, rel, pathnode->param_info);
954 :
955 16159 : return pathnode;
956 : }
957 :
958 : /*
959 : * create_samplescan_path
960 : * Creates a path node for a sampled table scan.
961 : */
962 : Path *
963 36 : create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
964 : {
965 36 : Path *pathnode = makeNode(Path);
966 :
967 36 : pathnode->pathtype = T_SampleScan;
968 36 : pathnode->parent = rel;
969 36 : pathnode->pathtarget = rel->reltarget;
970 36 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
971 : required_outer);
972 36 : pathnode->parallel_aware = false;
973 36 : pathnode->parallel_safe = rel->consider_parallel;
974 36 : pathnode->parallel_workers = 0;
975 36 : pathnode->pathkeys = NIL; /* samplescan has unordered result */
976 :
977 36 : cost_samplescan(pathnode, root, rel, pathnode->param_info);
978 :
979 36 : return pathnode;
980 : }
981 :
982 : /*
983 : * create_index_path
984 : * Creates a path node for an index scan.
985 : *
986 : * 'index' is a usable index.
987 : * 'indexclauses' is a list of RestrictInfo nodes representing clauses
988 : * to be used as index qual conditions in the scan.
989 : * 'indexclausecols' is an integer list of index column numbers (zero based)
990 : * the indexclauses can be used with.
991 : * 'indexorderbys' is a list of bare expressions (no RestrictInfos)
992 : * to be used as index ordering operators in the scan.
993 : * 'indexorderbycols' is an integer list of index column numbers (zero based)
994 : * the ordering operators can be used with.
995 : * 'pathkeys' describes the ordering of the path.
996 : * 'indexscandir' is ForwardScanDirection or BackwardScanDirection
997 : * for an ordered index, or NoMovementScanDirection for
998 : * an unordered index.
999 : * 'indexonly' is true if an index-only scan is wanted.
1000 : * 'required_outer' is the set of outer relids for a parameterized path.
1001 : * 'loop_count' is the number of repetitions of the indexscan to factor into
1002 : * estimates of caching behavior.
1003 : * 'partial_path' is true if constructing a parallel index scan path.
1004 : *
1005 : * Returns the new path node.
1006 : */
1007 : IndexPath *
1008 21949 : create_index_path(PlannerInfo *root,
1009 : IndexOptInfo *index,
1010 : List *indexclauses,
1011 : List *indexclausecols,
1012 : List *indexorderbys,
1013 : List *indexorderbycols,
1014 : List *pathkeys,
1015 : ScanDirection indexscandir,
1016 : bool indexonly,
1017 : Relids required_outer,
1018 : double loop_count,
1019 : bool partial_path)
1020 : {
1021 21949 : IndexPath *pathnode = makeNode(IndexPath);
1022 21949 : RelOptInfo *rel = index->rel;
1023 : List *indexquals,
1024 : *indexqualcols;
1025 :
1026 21949 : pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
1027 21949 : pathnode->path.parent = rel;
1028 21949 : pathnode->path.pathtarget = rel->reltarget;
1029 21949 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1030 : required_outer);
1031 21949 : pathnode->path.parallel_aware = false;
1032 21949 : pathnode->path.parallel_safe = rel->consider_parallel;
1033 21949 : pathnode->path.parallel_workers = 0;
1034 21949 : pathnode->path.pathkeys = pathkeys;
1035 :
1036 : /* Convert clauses to indexquals the executor can handle */
1037 21949 : expand_indexqual_conditions(index, indexclauses, indexclausecols,
1038 : &indexquals, &indexqualcols);
1039 :
1040 : /* Fill in the pathnode */
1041 21949 : pathnode->indexinfo = index;
1042 21949 : pathnode->indexclauses = indexclauses;
1043 21949 : pathnode->indexquals = indexquals;
1044 21949 : pathnode->indexqualcols = indexqualcols;
1045 21949 : pathnode->indexorderbys = indexorderbys;
1046 21949 : pathnode->indexorderbycols = indexorderbycols;
1047 21949 : pathnode->indexscandir = indexscandir;
1048 :
1049 21949 : cost_index(pathnode, root, loop_count, partial_path);
1050 :
1051 21949 : return pathnode;
1052 : }
1053 :
1054 : /*
1055 : * create_bitmap_heap_path
1056 : * Creates a path node for a bitmap scan.
1057 : *
1058 : * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
1059 : * 'required_outer' is the set of outer relids for a parameterized path.
1060 : * 'loop_count' is the number of repetitions of the indexscan to factor into
1061 : * estimates of caching behavior.
1062 : *
1063 : * loop_count should match the value used when creating the component
1064 : * IndexPaths.
1065 : */
1066 : BitmapHeapPath *
1067 10906 : create_bitmap_heap_path(PlannerInfo *root,
1068 : RelOptInfo *rel,
1069 : Path *bitmapqual,
1070 : Relids required_outer,
1071 : double loop_count,
1072 : int parallel_degree)
1073 : {
1074 10906 : BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
1075 :
1076 10906 : pathnode->path.pathtype = T_BitmapHeapScan;
1077 10906 : pathnode->path.parent = rel;
1078 10906 : pathnode->path.pathtarget = rel->reltarget;
1079 10906 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1080 : required_outer);
1081 10906 : pathnode->path.parallel_aware = parallel_degree > 0 ? true : false;
1082 10906 : pathnode->path.parallel_safe = rel->consider_parallel;
1083 10906 : pathnode->path.parallel_workers = parallel_degree;
1084 10906 : pathnode->path.pathkeys = NIL; /* always unordered */
1085 :
1086 10906 : pathnode->bitmapqual = bitmapqual;
1087 :
1088 10906 : cost_bitmap_heap_scan(&pathnode->path, root, rel,
1089 : pathnode->path.param_info,
1090 : bitmapqual, loop_count);
1091 :
1092 10906 : return pathnode;
1093 : }
1094 :
1095 : /*
1096 : * create_bitmap_and_path
1097 : * Creates a path node representing a BitmapAnd.
1098 : */
1099 : BitmapAndPath *
1100 3 : create_bitmap_and_path(PlannerInfo *root,
1101 : RelOptInfo *rel,
1102 : List *bitmapquals)
1103 : {
1104 3 : BitmapAndPath *pathnode = makeNode(BitmapAndPath);
1105 :
1106 3 : pathnode->path.pathtype = T_BitmapAnd;
1107 3 : pathnode->path.parent = rel;
1108 3 : pathnode->path.pathtarget = rel->reltarget;
1109 3 : pathnode->path.param_info = NULL; /* not used in bitmap trees */
1110 :
1111 : /*
1112 : * Currently, a BitmapHeapPath, BitmapAndPath, or BitmapOrPath will be
1113 : * parallel-safe if and only if rel->consider_parallel is set. So, we can
1114 : * set the flag for this path based only on the relation-level flag,
1115 : * without actually iterating over the list of children.
1116 : */
1117 3 : pathnode->path.parallel_aware = false;
1118 3 : pathnode->path.parallel_safe = rel->consider_parallel;
1119 3 : pathnode->path.parallel_workers = 0;
1120 :
1121 3 : pathnode->path.pathkeys = NIL; /* always unordered */
1122 :
1123 3 : pathnode->bitmapquals = bitmapquals;
1124 :
1125 : /* this sets bitmapselectivity as well as the regular cost fields: */
1126 3 : cost_bitmap_and_node(pathnode, root);
1127 :
1128 3 : return pathnode;
1129 : }
1130 :
1131 : /*
1132 : * create_bitmap_or_path
1133 : * Creates a path node representing a BitmapOr.
1134 : */
1135 : BitmapOrPath *
1136 45 : create_bitmap_or_path(PlannerInfo *root,
1137 : RelOptInfo *rel,
1138 : List *bitmapquals)
1139 : {
1140 45 : BitmapOrPath *pathnode = makeNode(BitmapOrPath);
1141 :
1142 45 : pathnode->path.pathtype = T_BitmapOr;
1143 45 : pathnode->path.parent = rel;
1144 45 : pathnode->path.pathtarget = rel->reltarget;
1145 45 : pathnode->path.param_info = NULL; /* not used in bitmap trees */
1146 :
1147 : /*
1148 : * Currently, a BitmapHeapPath, BitmapAndPath, or BitmapOrPath will be
1149 : * parallel-safe if and only if rel->consider_parallel is set. So, we can
1150 : * set the flag for this path based only on the relation-level flag,
1151 : * without actually iterating over the list of children.
1152 : */
1153 45 : pathnode->path.parallel_aware = false;
1154 45 : pathnode->path.parallel_safe = rel->consider_parallel;
1155 45 : pathnode->path.parallel_workers = 0;
1156 :
1157 45 : pathnode->path.pathkeys = NIL; /* always unordered */
1158 :
1159 45 : pathnode->bitmapquals = bitmapquals;
1160 :
1161 : /* this sets bitmapselectivity as well as the regular cost fields: */
1162 45 : cost_bitmap_or_node(pathnode, root);
1163 :
1164 45 : return pathnode;
1165 : }
1166 :
1167 : /*
1168 : * create_tidscan_path
1169 : * Creates a path corresponding to a scan by TID, returning the pathnode.
1170 : */
1171 : TidPath *
1172 66 : create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
1173 : Relids required_outer)
1174 : {
1175 66 : TidPath *pathnode = makeNode(TidPath);
1176 :
1177 66 : pathnode->path.pathtype = T_TidScan;
1178 66 : pathnode->path.parent = rel;
1179 66 : pathnode->path.pathtarget = rel->reltarget;
1180 66 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1181 : required_outer);
1182 66 : pathnode->path.parallel_aware = false;
1183 66 : pathnode->path.parallel_safe = rel->consider_parallel;
1184 66 : pathnode->path.parallel_workers = 0;
1185 66 : pathnode->path.pathkeys = NIL; /* always unordered */
1186 :
1187 66 : pathnode->tidquals = tidquals;
1188 :
1189 66 : cost_tidscan(&pathnode->path, root, rel, tidquals,
1190 : pathnode->path.param_info);
1191 :
1192 66 : return pathnode;
1193 : }
1194 :
1195 : /*
1196 : * create_append_path
1197 : * Creates a path corresponding to an Append plan, returning the
1198 : * pathnode.
1199 : *
1200 : * Note that we must handle subpaths = NIL, representing a dummy access path.
1201 : */
1202 : AppendPath *
1203 1069 : create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
1204 : int parallel_workers, List *partitioned_rels)
1205 : {
1206 1069 : AppendPath *pathnode = makeNode(AppendPath);
1207 : ListCell *l;
1208 :
1209 1069 : pathnode->path.pathtype = T_Append;
1210 1069 : pathnode->path.parent = rel;
1211 1069 : pathnode->path.pathtarget = rel->reltarget;
1212 1069 : pathnode->path.param_info = get_appendrel_parampathinfo(rel,
1213 : required_outer);
1214 1069 : pathnode->path.parallel_aware = false;
1215 1069 : pathnode->path.parallel_safe = rel->consider_parallel;
1216 1069 : pathnode->path.parallel_workers = parallel_workers;
1217 1069 : pathnode->path.pathkeys = NIL; /* result is always considered unsorted */
1218 1069 : pathnode->partitioned_rels = list_copy(partitioned_rels);
1219 1069 : pathnode->subpaths = subpaths;
1220 :
1221 : /*
1222 : * We don't bother with inventing a cost_append(), but just do it here.
1223 : *
1224 : * Compute rows and costs as sums of subplan rows and costs. We charge
1225 : * nothing extra for the Append itself, which perhaps is too optimistic,
1226 : * but since it doesn't do any selection or projection, it is a pretty
1227 : * cheap node.
1228 : */
1229 1069 : pathnode->path.rows = 0;
1230 1069 : pathnode->path.startup_cost = 0;
1231 1069 : pathnode->path.total_cost = 0;
1232 3495 : foreach(l, subpaths)
1233 : {
1234 2426 : Path *subpath = (Path *) lfirst(l);
1235 :
1236 2426 : pathnode->path.rows += subpath->rows;
1237 :
1238 2426 : if (l == list_head(subpaths)) /* first node? */
1239 930 : pathnode->path.startup_cost = subpath->startup_cost;
1240 2426 : pathnode->path.total_cost += subpath->total_cost;
1241 4092 : pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
1242 1666 : subpath->parallel_safe;
1243 :
1244 : /* All child paths must have same parameterization */
1245 2426 : Assert(bms_equal(PATH_REQ_OUTER(subpath), required_outer));
1246 : }
1247 :
1248 1069 : return pathnode;
1249 : }
1250 :
1251 : /*
1252 : * create_merge_append_path
1253 : * Creates a path corresponding to a MergeAppend plan, returning the
1254 : * pathnode.
1255 : */
1256 : MergeAppendPath *
1257 81 : create_merge_append_path(PlannerInfo *root,
1258 : RelOptInfo *rel,
1259 : List *subpaths,
1260 : List *pathkeys,
1261 : Relids required_outer,
1262 : List *partitioned_rels)
1263 : {
1264 81 : MergeAppendPath *pathnode = makeNode(MergeAppendPath);
1265 : Cost input_startup_cost;
1266 : Cost input_total_cost;
1267 : ListCell *l;
1268 :
1269 81 : pathnode->path.pathtype = T_MergeAppend;
1270 81 : pathnode->path.parent = rel;
1271 81 : pathnode->path.pathtarget = rel->reltarget;
1272 81 : pathnode->path.param_info = get_appendrel_parampathinfo(rel,
1273 : required_outer);
1274 81 : pathnode->path.parallel_aware = false;
1275 81 : pathnode->path.parallel_safe = rel->consider_parallel;
1276 81 : pathnode->path.parallel_workers = 0;
1277 81 : pathnode->path.pathkeys = pathkeys;
1278 81 : pathnode->partitioned_rels = list_copy(partitioned_rels);
1279 81 : pathnode->subpaths = subpaths;
1280 :
1281 : /*
1282 : * Apply query-wide LIMIT if known and path is for sole base relation.
1283 : * (Handling this at this low level is a bit klugy.)
1284 : */
1285 81 : if (bms_equal(rel->relids, root->all_baserels))
1286 36 : pathnode->limit_tuples = root->limit_tuples;
1287 : else
1288 45 : pathnode->limit_tuples = -1.0;
1289 :
1290 : /*
1291 : * Add up the sizes and costs of the input paths.
1292 : */
1293 81 : pathnode->path.rows = 0;
1294 81 : input_startup_cost = 0;
1295 81 : input_total_cost = 0;
1296 293 : foreach(l, subpaths)
1297 : {
1298 212 : Path *subpath = (Path *) lfirst(l);
1299 :
1300 212 : pathnode->path.rows += subpath->rows;
1301 355 : pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
1302 143 : subpath->parallel_safe;
1303 :
1304 212 : if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
1305 : {
1306 : /* Subpath is adequately ordered, we won't need to sort it */
1307 173 : input_startup_cost += subpath->startup_cost;
1308 173 : input_total_cost += subpath->total_cost;
1309 : }
1310 : else
1311 : {
1312 : /* We'll need to insert a Sort node, so include cost for that */
1313 : Path sort_path; /* dummy for result of cost_sort */
1314 :
1315 117 : cost_sort(&sort_path,
1316 : root,
1317 : pathkeys,
1318 : subpath->total_cost,
1319 39 : subpath->parent->tuples,
1320 39 : subpath->pathtarget->width,
1321 : 0.0,
1322 : work_mem,
1323 : pathnode->limit_tuples);
1324 39 : input_startup_cost += sort_path.startup_cost;
1325 39 : input_total_cost += sort_path.total_cost;
1326 : }
1327 :
1328 : /* All child paths must have same parameterization */
1329 212 : Assert(bms_equal(PATH_REQ_OUTER(subpath), required_outer));
1330 : }
1331 :
1332 : /* Now we can compute total costs of the MergeAppend */
1333 81 : cost_merge_append(&pathnode->path, root,
1334 : pathkeys, list_length(subpaths),
1335 : input_startup_cost, input_total_cost,
1336 : pathnode->path.rows);
1337 :
1338 81 : return pathnode;
1339 : }
1340 :
1341 : /*
1342 : * create_result_path
1343 : * Creates a path representing a Result-and-nothing-else plan.
1344 : *
1345 : * This is only used for degenerate cases, such as a query with an empty
1346 : * jointree.
1347 : */
1348 : ResultPath *
1349 11432 : create_result_path(PlannerInfo *root, RelOptInfo *rel,
1350 : PathTarget *target, List *resconstantqual)
1351 : {
1352 11432 : ResultPath *pathnode = makeNode(ResultPath);
1353 :
1354 11432 : pathnode->path.pathtype = T_Result;
1355 11432 : pathnode->path.parent = rel;
1356 11432 : pathnode->path.pathtarget = target;
1357 11432 : pathnode->path.param_info = NULL; /* there are no other rels... */
1358 11432 : pathnode->path.parallel_aware = false;
1359 11432 : pathnode->path.parallel_safe = rel->consider_parallel;
1360 11432 : pathnode->path.parallel_workers = 0;
1361 11432 : pathnode->path.pathkeys = NIL;
1362 11432 : pathnode->quals = resconstantqual;
1363 :
1364 : /* Hardly worth defining a cost_result() function ... just do it */
1365 11432 : pathnode->path.rows = 1;
1366 11432 : pathnode->path.startup_cost = target->cost.startup;
1367 22864 : pathnode->path.total_cost = target->cost.startup +
1368 11432 : cpu_tuple_cost + target->cost.per_tuple;
1369 11432 : if (resconstantqual)
1370 : {
1371 : QualCost qual_cost;
1372 :
1373 63 : cost_qual_eval(&qual_cost, resconstantqual, root);
1374 : /* resconstantqual is evaluated once at startup */
1375 63 : pathnode->path.startup_cost += qual_cost.startup + qual_cost.per_tuple;
1376 63 : pathnode->path.total_cost += qual_cost.startup + qual_cost.per_tuple;
1377 : }
1378 :
1379 11432 : return pathnode;
1380 : }
1381 :
1382 : /*
1383 : * create_material_path
1384 : * Creates a path corresponding to a Material plan, returning the
1385 : * pathnode.
1386 : */
1387 : MaterialPath *
1388 12691 : create_material_path(RelOptInfo *rel, Path *subpath)
1389 : {
1390 12691 : MaterialPath *pathnode = makeNode(MaterialPath);
1391 :
1392 12691 : Assert(subpath->parent == rel);
1393 :
1394 12691 : pathnode->path.pathtype = T_Material;
1395 12691 : pathnode->path.parent = rel;
1396 12691 : pathnode->path.pathtarget = rel->reltarget;
1397 12691 : pathnode->path.param_info = subpath->param_info;
1398 12691 : pathnode->path.parallel_aware = false;
1399 21856 : pathnode->path.parallel_safe = rel->consider_parallel &&
1400 9165 : subpath->parallel_safe;
1401 12691 : pathnode->path.parallel_workers = subpath->parallel_workers;
1402 12691 : pathnode->path.pathkeys = subpath->pathkeys;
1403 :
1404 12691 : pathnode->subpath = subpath;
1405 :
1406 12691 : cost_material(&pathnode->path,
1407 : subpath->startup_cost,
1408 : subpath->total_cost,
1409 : subpath->rows,
1410 12691 : subpath->pathtarget->width);
1411 :
1412 12691 : return pathnode;
1413 : }
1414 :
1415 : /*
1416 : * create_unique_path
1417 : * Creates a path representing elimination of distinct rows from the
1418 : * input data. Distinct-ness is defined according to the needs of the
1419 : * semijoin represented by sjinfo. If it is not possible to identify
1420 : * how to make the data unique, NULL is returned.
1421 : *
1422 : * If used at all, this is likely to be called repeatedly on the same rel;
1423 : * and the input subpath should always be the same (the cheapest_total path
1424 : * for the rel). So we cache the result.
1425 : */
1426 : UniquePath *
1427 1781 : create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1428 : SpecialJoinInfo *sjinfo)
1429 : {
1430 : UniquePath *pathnode;
1431 : Path sort_path; /* dummy for result of cost_sort */
1432 : Path agg_path; /* dummy for result of cost_agg */
1433 : MemoryContext oldcontext;
1434 : int numCols;
1435 :
1436 : /* Caller made a mistake if subpath isn't cheapest_total ... */
1437 1781 : Assert(subpath == rel->cheapest_total_path);
1438 1781 : Assert(subpath->parent == rel);
1439 : /* ... or if SpecialJoinInfo is the wrong one */
1440 1781 : Assert(sjinfo->jointype == JOIN_SEMI);
1441 1781 : Assert(bms_equal(rel->relids, sjinfo->syn_righthand));
1442 :
1443 : /* If result already cached, return it */
1444 1781 : if (rel->cheapest_unique_path)
1445 1467 : return (UniquePath *) rel->cheapest_unique_path;
1446 :
1447 : /* If it's not possible to unique-ify, return NULL */
1448 314 : if (!(sjinfo->semi_can_btree || sjinfo->semi_can_hash))
1449 8 : return NULL;
1450 :
1451 : /*
1452 : * We must ensure path struct and subsidiary data are allocated in main
1453 : * planning context; otherwise GEQO memory management causes trouble.
1454 : */
1455 306 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
1456 :
1457 306 : pathnode = makeNode(UniquePath);
1458 :
1459 306 : pathnode->path.pathtype = T_Unique;
1460 306 : pathnode->path.parent = rel;
1461 306 : pathnode->path.pathtarget = rel->reltarget;
1462 306 : pathnode->path.param_info = subpath->param_info;
1463 306 : pathnode->path.parallel_aware = false;
1464 597 : pathnode->path.parallel_safe = rel->consider_parallel &&
1465 291 : subpath->parallel_safe;
1466 306 : pathnode->path.parallel_workers = subpath->parallel_workers;
1467 :
1468 : /*
1469 : * Assume the output is unsorted, since we don't necessarily have pathkeys
1470 : * to represent it. (This might get overridden below.)
1471 : */
1472 306 : pathnode->path.pathkeys = NIL;
1473 :
1474 306 : pathnode->subpath = subpath;
1475 306 : pathnode->in_operators = sjinfo->semi_operators;
1476 306 : pathnode->uniq_exprs = sjinfo->semi_rhs_exprs;
1477 :
1478 : /*
1479 : * If the input is a relation and it has a unique index that proves the
1480 : * semi_rhs_exprs are unique, then we don't need to do anything. Note
1481 : * that relation_has_unique_index_for automatically considers restriction
1482 : * clauses for the rel, as well.
1483 : */
1484 338 : if (rel->rtekind == RTE_RELATION && sjinfo->semi_can_btree &&
1485 32 : relation_has_unique_index_for(root, rel, NIL,
1486 : sjinfo->semi_rhs_exprs,
1487 : sjinfo->semi_operators))
1488 : {
1489 0 : pathnode->umethod = UNIQUE_PATH_NOOP;
1490 0 : pathnode->path.rows = rel->rows;
1491 0 : pathnode->path.startup_cost = subpath->startup_cost;
1492 0 : pathnode->path.total_cost = subpath->total_cost;
1493 0 : pathnode->path.pathkeys = subpath->pathkeys;
1494 :
1495 0 : rel->cheapest_unique_path = (Path *) pathnode;
1496 :
1497 0 : MemoryContextSwitchTo(oldcontext);
1498 :
1499 0 : return pathnode;
1500 : }
1501 :
1502 : /*
1503 : * If the input is a subquery whose output must be unique already, then we
1504 : * don't need to do anything. The test for uniqueness has to consider
1505 : * exactly which columns we are extracting; for example "SELECT DISTINCT
1506 : * x,y" doesn't guarantee that x alone is distinct. So we cannot check for
1507 : * this optimization unless semi_rhs_exprs consists only of simple Vars
1508 : * referencing subquery outputs. (Possibly we could do something with
1509 : * expressions in the subquery outputs, too, but for now keep it simple.)
1510 : */
1511 306 : if (rel->rtekind == RTE_SUBQUERY)
1512 : {
1513 8 : RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
1514 :
1515 8 : if (query_supports_distinctness(rte->subquery))
1516 : {
1517 : List *sub_tlist_colnos;
1518 :
1519 3 : sub_tlist_colnos = translate_sub_tlist(sjinfo->semi_rhs_exprs,
1520 3 : rel->relid);
1521 :
1522 6 : if (sub_tlist_colnos &&
1523 3 : query_is_distinct_for(rte->subquery,
1524 : sub_tlist_colnos,
1525 : sjinfo->semi_operators))
1526 : {
1527 0 : pathnode->umethod = UNIQUE_PATH_NOOP;
1528 0 : pathnode->path.rows = rel->rows;
1529 0 : pathnode->path.startup_cost = subpath->startup_cost;
1530 0 : pathnode->path.total_cost = subpath->total_cost;
1531 0 : pathnode->path.pathkeys = subpath->pathkeys;
1532 :
1533 0 : rel->cheapest_unique_path = (Path *) pathnode;
1534 :
1535 0 : MemoryContextSwitchTo(oldcontext);
1536 :
1537 0 : return pathnode;
1538 : }
1539 : }
1540 : }
1541 :
1542 : /* Estimate number of output rows */
1543 306 : pathnode->path.rows = estimate_num_groups(root,
1544 : sjinfo->semi_rhs_exprs,
1545 : rel->rows,
1546 : NULL);
1547 306 : numCols = list_length(sjinfo->semi_rhs_exprs);
1548 :
1549 306 : if (sjinfo->semi_can_btree)
1550 : {
1551 : /*
1552 : * Estimate cost for sort+unique implementation
1553 : */
1554 612 : cost_sort(&sort_path, root, NIL,
1555 : subpath->total_cost,
1556 : rel->rows,
1557 306 : subpath->pathtarget->width,
1558 : 0.0,
1559 : work_mem,
1560 : -1.0);
1561 :
1562 : /*
1563 : * Charge one cpu_operator_cost per comparison per input tuple. We
1564 : * assume all columns get compared at most of the tuples. (XXX
1565 : * probably this is an overestimate.) This should agree with
1566 : * create_upper_unique_path.
1567 : */
1568 306 : sort_path.total_cost += cpu_operator_cost * rel->rows * numCols;
1569 : }
1570 :
1571 306 : if (sjinfo->semi_can_hash)
1572 : {
1573 : /*
1574 : * Estimate the overhead per hashtable entry at 64 bytes (same as in
1575 : * planner.c).
1576 : */
1577 301 : int hashentrysize = subpath->pathtarget->width + 64;
1578 :
1579 301 : if (hashentrysize * pathnode->path.rows > work_mem * 1024L)
1580 : {
1581 : /*
1582 : * We should not try to hash. Hack the SpecialJoinInfo to
1583 : * remember this, in case we come through here again.
1584 : */
1585 0 : sjinfo->semi_can_hash = false;
1586 : }
1587 : else
1588 301 : cost_agg(&agg_path, root,
1589 : AGG_HASHED, NULL,
1590 : numCols, pathnode->path.rows,
1591 : subpath->startup_cost,
1592 : subpath->total_cost,
1593 : rel->rows);
1594 : }
1595 :
1596 306 : if (sjinfo->semi_can_btree && sjinfo->semi_can_hash)
1597 : {
1598 602 : if (agg_path.total_cost < sort_path.total_cost)
1599 299 : pathnode->umethod = UNIQUE_PATH_HASH;
1600 : else
1601 2 : pathnode->umethod = UNIQUE_PATH_SORT;
1602 : }
1603 5 : else if (sjinfo->semi_can_btree)
1604 5 : pathnode->umethod = UNIQUE_PATH_SORT;
1605 0 : else if (sjinfo->semi_can_hash)
1606 0 : pathnode->umethod = UNIQUE_PATH_HASH;
1607 : else
1608 : {
1609 : /* we can get here only if we abandoned hashing above */
1610 0 : MemoryContextSwitchTo(oldcontext);
1611 0 : return NULL;
1612 : }
1613 :
1614 306 : if (pathnode->umethod == UNIQUE_PATH_HASH)
1615 : {
1616 299 : pathnode->path.startup_cost = agg_path.startup_cost;
1617 299 : pathnode->path.total_cost = agg_path.total_cost;
1618 : }
1619 : else
1620 : {
1621 7 : pathnode->path.startup_cost = sort_path.startup_cost;
1622 7 : pathnode->path.total_cost = sort_path.total_cost;
1623 : }
1624 :
1625 306 : rel->cheapest_unique_path = (Path *) pathnode;
1626 :
1627 306 : MemoryContextSwitchTo(oldcontext);
1628 :
1629 306 : return pathnode;
1630 : }
1631 :
1632 : /*
1633 : * create_gather_merge_path
1634 : *
1635 : * Creates a path corresponding to a gather merge scan, returning
1636 : * the pathnode.
1637 : */
1638 : GatherMergePath *
1639 46 : create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1640 : PathTarget *target, List *pathkeys,
1641 : Relids required_outer, double *rows)
1642 : {
1643 46 : GatherMergePath *pathnode = makeNode(GatherMergePath);
1644 46 : Cost input_startup_cost = 0;
1645 46 : Cost input_total_cost = 0;
1646 :
1647 46 : Assert(subpath->parallel_safe);
1648 46 : Assert(pathkeys);
1649 :
1650 46 : pathnode->path.pathtype = T_GatherMerge;
1651 46 : pathnode->path.parent = rel;
1652 46 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1653 : required_outer);
1654 46 : pathnode->path.parallel_aware = false;
1655 :
1656 46 : pathnode->subpath = subpath;
1657 46 : pathnode->num_workers = subpath->parallel_workers;
1658 46 : pathnode->path.pathkeys = pathkeys;
1659 46 : pathnode->path.pathtarget = target ? target : rel->reltarget;
1660 46 : pathnode->path.rows += subpath->rows;
1661 :
1662 46 : if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
1663 : {
1664 : /* Subpath is adequately ordered, we won't need to sort it */
1665 46 : input_startup_cost += subpath->startup_cost;
1666 46 : input_total_cost += subpath->total_cost;
1667 : }
1668 : else
1669 : {
1670 : /* We'll need to insert a Sort node, so include cost for that */
1671 : Path sort_path; /* dummy for result of cost_sort */
1672 :
1673 0 : cost_sort(&sort_path,
1674 : root,
1675 : pathkeys,
1676 : subpath->total_cost,
1677 : subpath->rows,
1678 0 : subpath->pathtarget->width,
1679 : 0.0,
1680 : work_mem,
1681 : -1);
1682 0 : input_startup_cost += sort_path.startup_cost;
1683 0 : input_total_cost += sort_path.total_cost;
1684 : }
1685 :
1686 46 : cost_gather_merge(pathnode, root, rel, pathnode->path.param_info,
1687 : input_startup_cost, input_total_cost, rows);
1688 :
1689 46 : return pathnode;
1690 : }
1691 :
1692 : /*
1693 : * translate_sub_tlist - get subquery column numbers represented by tlist
1694 : *
1695 : * The given targetlist usually contains only Vars referencing the given relid.
1696 : * Extract their varattnos (ie, the column numbers of the subquery) and return
1697 : * as an integer List.
1698 : *
1699 : * If any of the tlist items is not a simple Var, we cannot determine whether
1700 : * the subquery's uniqueness condition (if any) matches ours, so punt and
1701 : * return NIL.
1702 : */
1703 : static List *
1704 3 : translate_sub_tlist(List *tlist, int relid)
1705 : {
1706 3 : List *result = NIL;
1707 : ListCell *l;
1708 :
1709 6 : foreach(l, tlist)
1710 : {
1711 3 : Var *var = (Var *) lfirst(l);
1712 :
1713 6 : if (!var || !IsA(var, Var) ||
1714 3 : var->varno != relid)
1715 0 : return NIL; /* punt */
1716 :
1717 3 : result = lappend_int(result, var->varattno);
1718 : }
1719 3 : return result;
1720 : }
1721 :
1722 : /*
1723 : * create_gather_path
1724 : * Creates a path corresponding to a gather scan, returning the
1725 : * pathnode.
1726 : *
1727 : * 'rows' may optionally be set to override row estimates from other sources.
1728 : */
1729 : GatherPath *
1730 314 : create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1731 : PathTarget *target, Relids required_outer, double *rows)
1732 : {
1733 314 : GatherPath *pathnode = makeNode(GatherPath);
1734 :
1735 314 : Assert(subpath->parallel_safe);
1736 :
1737 314 : pathnode->path.pathtype = T_Gather;
1738 314 : pathnode->path.parent = rel;
1739 314 : pathnode->path.pathtarget = target;
1740 314 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1741 : required_outer);
1742 314 : pathnode->path.parallel_aware = false;
1743 314 : pathnode->path.parallel_safe = false;
1744 314 : pathnode->path.parallel_workers = 0;
1745 314 : pathnode->path.pathkeys = NIL; /* Gather has unordered result */
1746 :
1747 314 : pathnode->subpath = subpath;
1748 314 : pathnode->num_workers = subpath->parallel_workers;
1749 314 : pathnode->single_copy = false;
1750 :
1751 314 : if (pathnode->num_workers == 0)
1752 : {
1753 0 : pathnode->path.pathkeys = subpath->pathkeys;
1754 0 : pathnode->num_workers = 1;
1755 0 : pathnode->single_copy = true;
1756 : }
1757 :
1758 314 : cost_gather(pathnode, root, rel, pathnode->path.param_info, rows);
1759 :
1760 314 : return pathnode;
1761 : }
1762 :
1763 : /*
1764 : * create_subqueryscan_path
1765 : * Creates a path corresponding to a scan of a subquery,
1766 : * returning the pathnode.
1767 : */
1768 : SubqueryScanPath *
1769 1111 : create_subqueryscan_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1770 : List *pathkeys, Relids required_outer)
1771 : {
1772 1111 : SubqueryScanPath *pathnode = makeNode(SubqueryScanPath);
1773 :
1774 1111 : pathnode->path.pathtype = T_SubqueryScan;
1775 1111 : pathnode->path.parent = rel;
1776 1111 : pathnode->path.pathtarget = rel->reltarget;
1777 1111 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1778 : required_outer);
1779 1111 : pathnode->path.parallel_aware = false;
1780 1761 : pathnode->path.parallel_safe = rel->consider_parallel &&
1781 650 : subpath->parallel_safe;
1782 1111 : pathnode->path.parallel_workers = subpath->parallel_workers;
1783 1111 : pathnode->path.pathkeys = pathkeys;
1784 1111 : pathnode->subpath = subpath;
1785 :
1786 1111 : cost_subqueryscan(pathnode, root, rel, pathnode->path.param_info);
1787 :
1788 1111 : return pathnode;
1789 : }
1790 :
1791 : /*
1792 : * create_functionscan_path
1793 : * Creates a path corresponding to a sequential scan of a function,
1794 : * returning the pathnode.
1795 : */
1796 : Path *
1797 1328 : create_functionscan_path(PlannerInfo *root, RelOptInfo *rel,
1798 : List *pathkeys, Relids required_outer)
1799 : {
1800 1328 : Path *pathnode = makeNode(Path);
1801 :
1802 1328 : pathnode->pathtype = T_FunctionScan;
1803 1328 : pathnode->parent = rel;
1804 1328 : pathnode->pathtarget = rel->reltarget;
1805 1328 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1806 : required_outer);
1807 1328 : pathnode->parallel_aware = false;
1808 1328 : pathnode->parallel_safe = rel->consider_parallel;
1809 1328 : pathnode->parallel_workers = 0;
1810 1328 : pathnode->pathkeys = pathkeys;
1811 :
1812 1328 : cost_functionscan(pathnode, root, rel, pathnode->param_info);
1813 :
1814 1328 : return pathnode;
1815 : }
1816 :
1817 : /*
1818 : * create_tablefuncscan_path
1819 : * Creates a path corresponding to a sequential scan of a table function,
1820 : * returning the pathnode.
1821 : */
1822 : Path *
1823 22 : create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel,
1824 : Relids required_outer)
1825 : {
1826 22 : Path *pathnode = makeNode(Path);
1827 :
1828 22 : pathnode->pathtype = T_TableFuncScan;
1829 22 : pathnode->parent = rel;
1830 22 : pathnode->pathtarget = rel->reltarget;
1831 22 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1832 : required_outer);
1833 22 : pathnode->parallel_aware = false;
1834 22 : pathnode->parallel_safe = rel->consider_parallel;
1835 22 : pathnode->parallel_workers = 0;
1836 22 : pathnode->pathkeys = NIL; /* result is always unordered */
1837 :
1838 22 : cost_tablefuncscan(pathnode, root, rel, pathnode->param_info);
1839 :
1840 22 : return pathnode;
1841 : }
1842 :
1843 : /*
1844 : * create_valuesscan_path
1845 : * Creates a path corresponding to a scan of a VALUES list,
1846 : * returning the pathnode.
1847 : */
1848 : Path *
1849 461 : create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
1850 : Relids required_outer)
1851 : {
1852 461 : Path *pathnode = makeNode(Path);
1853 :
1854 461 : pathnode->pathtype = T_ValuesScan;
1855 461 : pathnode->parent = rel;
1856 461 : pathnode->pathtarget = rel->reltarget;
1857 461 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1858 : required_outer);
1859 461 : pathnode->parallel_aware = false;
1860 461 : pathnode->parallel_safe = rel->consider_parallel;
1861 461 : pathnode->parallel_workers = 0;
1862 461 : pathnode->pathkeys = NIL; /* result is always unordered */
1863 :
1864 461 : cost_valuesscan(pathnode, root, rel, pathnode->param_info);
1865 :
1866 461 : return pathnode;
1867 : }
1868 :
1869 : /*
1870 : * create_ctescan_path
1871 : * Creates a path corresponding to a scan of a non-self-reference CTE,
1872 : * returning the pathnode.
1873 : */
1874 : Path *
1875 162 : create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
1876 : {
1877 162 : Path *pathnode = makeNode(Path);
1878 :
1879 162 : pathnode->pathtype = T_CteScan;
1880 162 : pathnode->parent = rel;
1881 162 : pathnode->pathtarget = rel->reltarget;
1882 162 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1883 : required_outer);
1884 162 : pathnode->parallel_aware = false;
1885 162 : pathnode->parallel_safe = rel->consider_parallel;
1886 162 : pathnode->parallel_workers = 0;
1887 162 : pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */
1888 :
1889 162 : cost_ctescan(pathnode, root, rel, pathnode->param_info);
1890 :
1891 162 : return pathnode;
1892 : }
1893 :
1894 : /*
1895 : * create_namedtuplestorescan_path
1896 : * Creates a path corresponding to a scan of a named tuplestore, returning
1897 : * the pathnode.
1898 : */
1899 : Path *
1900 41 : create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel,
1901 : Relids required_outer)
1902 : {
1903 41 : Path *pathnode = makeNode(Path);
1904 :
1905 41 : pathnode->pathtype = T_NamedTuplestoreScan;
1906 41 : pathnode->parent = rel;
1907 41 : pathnode->pathtarget = rel->reltarget;
1908 41 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1909 : required_outer);
1910 41 : pathnode->parallel_aware = false;
1911 41 : pathnode->parallel_safe = rel->consider_parallel;
1912 41 : pathnode->parallel_workers = 0;
1913 41 : pathnode->pathkeys = NIL; /* result is always unordered */
1914 :
1915 41 : cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info);
1916 :
1917 41 : return pathnode;
1918 : }
1919 :
1920 : /*
1921 : * create_worktablescan_path
1922 : * Creates a path corresponding to a scan of a self-reference CTE,
1923 : * returning the pathnode.
1924 : */
1925 : Path *
1926 40 : create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel,
1927 : Relids required_outer)
1928 : {
1929 40 : Path *pathnode = makeNode(Path);
1930 :
1931 40 : pathnode->pathtype = T_WorkTableScan;
1932 40 : pathnode->parent = rel;
1933 40 : pathnode->pathtarget = rel->reltarget;
1934 40 : pathnode->param_info = get_baserel_parampathinfo(root, rel,
1935 : required_outer);
1936 40 : pathnode->parallel_aware = false;
1937 40 : pathnode->parallel_safe = rel->consider_parallel;
1938 40 : pathnode->parallel_workers = 0;
1939 40 : pathnode->pathkeys = NIL; /* result is always unordered */
1940 :
1941 : /* Cost is the same as for a regular CTE scan */
1942 40 : cost_ctescan(pathnode, root, rel, pathnode->param_info);
1943 :
1944 40 : return pathnode;
1945 : }
1946 :
1947 : /*
1948 : * create_foreignscan_path
1949 : * Creates a path corresponding to a scan of a foreign table, foreign join,
1950 : * or foreign upper-relation processing, returning the pathnode.
1951 : *
1952 : * This function is never called from core Postgres; rather, it's expected
1953 : * to be called by the GetForeignPaths, GetForeignJoinPaths, or
1954 : * GetForeignUpperPaths function of a foreign data wrapper. We make the FDW
1955 : * supply all fields of the path, since we do not have any way to calculate
1956 : * them in core. However, there is a usually-sane default for the pathtarget
1957 : * (rel->reltarget), so we let a NULL for "target" select that.
1958 : */
1959 : ForeignPath *
1960 0 : create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel,
1961 : PathTarget *target,
1962 : double rows, Cost startup_cost, Cost total_cost,
1963 : List *pathkeys,
1964 : Relids required_outer,
1965 : Path *fdw_outerpath,
1966 : List *fdw_private)
1967 : {
1968 0 : ForeignPath *pathnode = makeNode(ForeignPath);
1969 :
1970 0 : pathnode->path.pathtype = T_ForeignScan;
1971 0 : pathnode->path.parent = rel;
1972 0 : pathnode->path.pathtarget = target ? target : rel->reltarget;
1973 0 : pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1974 : required_outer);
1975 0 : pathnode->path.parallel_aware = false;
1976 0 : pathnode->path.parallel_safe = rel->consider_parallel;
1977 0 : pathnode->path.parallel_workers = 0;
1978 0 : pathnode->path.rows = rows;
1979 0 : pathnode->path.startup_cost = startup_cost;
1980 0 : pathnode->path.total_cost = total_cost;
1981 0 : pathnode->path.pathkeys = pathkeys;
1982 :
1983 0 : pathnode->fdw_outerpath = fdw_outerpath;
1984 0 : pathnode->fdw_private = fdw_private;
1985 :
1986 0 : return pathnode;
1987 : }
1988 :
1989 : /*
1990 : * calc_nestloop_required_outer
1991 : * Compute the required_outer set for a nestloop join path
1992 : *
1993 : * Note: result must not share storage with either input
1994 : */
1995 : Relids
1996 53541 : calc_nestloop_required_outer(Relids outerrelids,
1997 : Relids outer_paramrels,
1998 : Relids innerrelids,
1999 : Relids inner_paramrels)
2000 : {
2001 : Relids required_outer;
2002 :
2003 : /* inner_path can require rels from outer path, but not vice versa */
2004 53541 : Assert(!bms_overlap(outer_paramrels, innerrelids));
2005 : /* easy case if inner path is not parameterized */
2006 53541 : if (!inner_paramrels)
2007 41970 : return bms_copy(outer_paramrels);
2008 : /* else, form the union ... */
2009 11571 : required_outer = bms_union(outer_paramrels, inner_paramrels);
2010 : /* ... and remove any mention of now-satisfied outer rels */
2011 11571 : required_outer = bms_del_members(required_outer,
2012 : outerrelids);
2013 : /* maintain invariant that required_outer is exactly NULL if empty */
2014 11571 : if (bms_is_empty(required_outer))
2015 : {
2016 9134 : bms_free(required_outer);
2017 9134 : required_outer = NULL;
2018 : }
2019 11571 : return required_outer;
2020 : }
2021 :
2022 : /*
2023 : * calc_non_nestloop_required_outer
2024 : * Compute the required_outer set for a merge or hash join path
2025 : *
2026 : * Note: result must not share storage with either input
2027 : */
2028 : Relids
2029 34149 : calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
2030 : {
2031 34149 : Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
2032 34149 : Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
2033 : Relids required_outer;
2034 :
2035 : /* neither path can require rels from the other */
2036 34149 : Assert(!bms_overlap(outer_paramrels, inner_path->parent->relids));
2037 34149 : Assert(!bms_overlap(inner_paramrels, outer_path->parent->relids));
2038 : /* form the union ... */
2039 34149 : required_outer = bms_union(outer_paramrels, inner_paramrels);
2040 : /* we do not need an explicit test for empty; bms_union gets it right */
2041 34149 : return required_outer;
2042 : }
2043 :
2044 : /*
2045 : * create_nestloop_path
2046 : * Creates a pathnode corresponding to a nestloop join between two
2047 : * relations.
2048 : *
2049 : * 'joinrel' is the join relation.
2050 : * 'jointype' is the type of join required
2051 : * 'workspace' is the result from initial_cost_nestloop
2052 : * 'extra' contains various information about the join
2053 : * 'outer_path' is the outer path
2054 : * 'inner_path' is the inner path
2055 : * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
2056 : * 'pathkeys' are the path keys of the new join path
2057 : * 'required_outer' is the set of required outer rels
2058 : *
2059 : * Returns the resulting path node.
2060 : */
2061 : NestPath *
2062 25865 : create_nestloop_path(PlannerInfo *root,
2063 : RelOptInfo *joinrel,
2064 : JoinType jointype,
2065 : JoinCostWorkspace *workspace,
2066 : JoinPathExtraData *extra,
2067 : Path *outer_path,
2068 : Path *inner_path,
2069 : List *restrict_clauses,
2070 : List *pathkeys,
2071 : Relids required_outer)
2072 : {
2073 25865 : NestPath *pathnode = makeNode(NestPath);
2074 25865 : Relids inner_req_outer = PATH_REQ_OUTER(inner_path);
2075 :
2076 : /*
2077 : * If the inner path is parameterized by the outer, we must drop any
2078 : * restrict_clauses that are due to be moved into the inner path. We have
2079 : * to do this now, rather than postpone the work till createplan time,
2080 : * because the restrict_clauses list can affect the size and cost
2081 : * estimates for this path.
2082 : */
2083 25865 : if (bms_overlap(inner_req_outer, outer_path->parent->relids))
2084 : {
2085 4931 : Relids inner_and_outer = bms_union(inner_path->parent->relids,
2086 : inner_req_outer);
2087 4931 : List *jclauses = NIL;
2088 : ListCell *lc;
2089 :
2090 10616 : foreach(lc, restrict_clauses)
2091 : {
2092 5685 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2093 :
2094 5685 : if (!join_clause_is_movable_into(rinfo,
2095 5685 : inner_path->parent->relids,
2096 : inner_and_outer))
2097 566 : jclauses = lappend(jclauses, rinfo);
2098 : }
2099 4931 : restrict_clauses = jclauses;
2100 : }
2101 :
2102 25865 : pathnode->path.pathtype = T_NestLoop;
2103 25865 : pathnode->path.parent = joinrel;
2104 25865 : pathnode->path.pathtarget = joinrel->reltarget;
2105 25865 : pathnode->path.param_info =
2106 25865 : get_joinrel_parampathinfo(root,
2107 : joinrel,
2108 : outer_path,
2109 : inner_path,
2110 : extra->sjinfo,
2111 : required_outer,
2112 : &restrict_clauses);
2113 25865 : pathnode->path.parallel_aware = false;
2114 69095 : pathnode->path.parallel_safe = joinrel->consider_parallel &&
2115 43178 : outer_path->parallel_safe && inner_path->parallel_safe;
2116 : /* This is a foolish way to estimate parallel_workers, but for now... */
2117 25865 : pathnode->path.parallel_workers = outer_path->parallel_workers;
2118 25865 : pathnode->path.pathkeys = pathkeys;
2119 25865 : pathnode->jointype = jointype;
2120 25865 : pathnode->inner_unique = extra->inner_unique;
2121 25865 : pathnode->outerjoinpath = outer_path;
2122 25865 : pathnode->innerjoinpath = inner_path;
2123 25865 : pathnode->joinrestrictinfo = restrict_clauses;
2124 :
2125 25865 : final_cost_nestloop(root, pathnode, workspace, extra);
2126 :
2127 25865 : return pathnode;
2128 : }
2129 :
2130 : /*
2131 : * create_mergejoin_path
2132 : * Creates a pathnode corresponding to a mergejoin join between
2133 : * two relations
2134 : *
2135 : * 'joinrel' is the join relation
2136 : * 'jointype' is the type of join required
2137 : * 'workspace' is the result from initial_cost_mergejoin
2138 : * 'extra' contains various information about the join
2139 : * 'outer_path' is the outer path
2140 : * 'inner_path' is the inner path
2141 : * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
2142 : * 'pathkeys' are the path keys of the new join path
2143 : * 'required_outer' is the set of required outer rels
2144 : * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
2145 : * (this should be a subset of the restrict_clauses list)
2146 : * 'outersortkeys' are the sort varkeys for the outer relation
2147 : * 'innersortkeys' are the sort varkeys for the inner relation
2148 : */
2149 : MergePath *
2150 6553 : create_mergejoin_path(PlannerInfo *root,
2151 : RelOptInfo *joinrel,
2152 : JoinType jointype,
2153 : JoinCostWorkspace *workspace,
2154 : JoinPathExtraData *extra,
2155 : Path *outer_path,
2156 : Path *inner_path,
2157 : List *restrict_clauses,
2158 : List *pathkeys,
2159 : Relids required_outer,
2160 : List *mergeclauses,
2161 : List *outersortkeys,
2162 : List *innersortkeys)
2163 : {
2164 6553 : MergePath *pathnode = makeNode(MergePath);
2165 :
2166 6553 : pathnode->jpath.path.pathtype = T_MergeJoin;
2167 6553 : pathnode->jpath.path.parent = joinrel;
2168 6553 : pathnode->jpath.path.pathtarget = joinrel->reltarget;
2169 6553 : pathnode->jpath.path.param_info =
2170 6553 : get_joinrel_parampathinfo(root,
2171 : joinrel,
2172 : outer_path,
2173 : inner_path,
2174 : extra->sjinfo,
2175 : required_outer,
2176 : &restrict_clauses);
2177 6553 : pathnode->jpath.path.parallel_aware = false;
2178 17351 : pathnode->jpath.path.parallel_safe = joinrel->consider_parallel &&
2179 10790 : outer_path->parallel_safe && inner_path->parallel_safe;
2180 : /* This is a foolish way to estimate parallel_workers, but for now... */
2181 6553 : pathnode->jpath.path.parallel_workers = outer_path->parallel_workers;
2182 6553 : pathnode->jpath.path.pathkeys = pathkeys;
2183 6553 : pathnode->jpath.jointype = jointype;
2184 6553 : pathnode->jpath.inner_unique = extra->inner_unique;
2185 6553 : pathnode->jpath.outerjoinpath = outer_path;
2186 6553 : pathnode->jpath.innerjoinpath = inner_path;
2187 6553 : pathnode->jpath.joinrestrictinfo = restrict_clauses;
2188 6553 : pathnode->path_mergeclauses = mergeclauses;
2189 6553 : pathnode->outersortkeys = outersortkeys;
2190 6553 : pathnode->innersortkeys = innersortkeys;
2191 : /* pathnode->skip_mark_restore will be set by final_cost_mergejoin */
2192 : /* pathnode->materialize_inner will be set by final_cost_mergejoin */
2193 :
2194 6553 : final_cost_mergejoin(root, pathnode, workspace, extra);
2195 :
2196 6553 : return pathnode;
2197 : }
2198 :
2199 : /*
2200 : * create_hashjoin_path
2201 : * Creates a pathnode corresponding to a hash join between two relations.
2202 : *
2203 : * 'joinrel' is the join relation
2204 : * 'jointype' is the type of join required
2205 : * 'workspace' is the result from initial_cost_hashjoin
2206 : * 'extra' contains various information about the join
2207 : * 'outer_path' is the cheapest outer path
2208 : * 'inner_path' is the cheapest inner path
2209 : * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
2210 : * 'required_outer' is the set of required outer rels
2211 : * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
2212 : * (this should be a subset of the restrict_clauses list)
2213 : */
2214 : HashPath *
2215 7071 : create_hashjoin_path(PlannerInfo *root,
2216 : RelOptInfo *joinrel,
2217 : JoinType jointype,
2218 : JoinCostWorkspace *workspace,
2219 : JoinPathExtraData *extra,
2220 : Path *outer_path,
2221 : Path *inner_path,
2222 : List *restrict_clauses,
2223 : Relids required_outer,
2224 : List *hashclauses)
2225 : {
2226 7071 : HashPath *pathnode = makeNode(HashPath);
2227 :
2228 7071 : pathnode->jpath.path.pathtype = T_HashJoin;
2229 7071 : pathnode->jpath.path.parent = joinrel;
2230 7071 : pathnode->jpath.path.pathtarget = joinrel->reltarget;
2231 7071 : pathnode->jpath.path.param_info =
2232 7071 : get_joinrel_parampathinfo(root,
2233 : joinrel,
2234 : outer_path,
2235 : inner_path,
2236 : extra->sjinfo,
2237 : required_outer,
2238 : &restrict_clauses);
2239 7071 : pathnode->jpath.path.parallel_aware = false;
2240 18894 : pathnode->jpath.path.parallel_safe = joinrel->consider_parallel &&
2241 11815 : outer_path->parallel_safe && inner_path->parallel_safe;
2242 : /* This is a foolish way to estimate parallel_workers, but for now... */
2243 7071 : pathnode->jpath.path.parallel_workers = outer_path->parallel_workers;
2244 :
2245 : /*
2246 : * A hashjoin never has pathkeys, since its output ordering is
2247 : * unpredictable due to possible batching. XXX If the inner relation is
2248 : * small enough, we could instruct the executor that it must not batch,
2249 : * and then we could assume that the output inherits the outer relation's
2250 : * ordering, which might save a sort step. However there is considerable
2251 : * downside if our estimate of the inner relation size is badly off. For
2252 : * the moment we don't risk it. (Note also that if we wanted to take this
2253 : * seriously, joinpath.c would have to consider many more paths for the
2254 : * outer rel than it does now.)
2255 : */
2256 7071 : pathnode->jpath.path.pathkeys = NIL;
2257 7071 : pathnode->jpath.jointype = jointype;
2258 7071 : pathnode->jpath.inner_unique = extra->inner_unique;
2259 7071 : pathnode->jpath.outerjoinpath = outer_path;
2260 7071 : pathnode->jpath.innerjoinpath = inner_path;
2261 7071 : pathnode->jpath.joinrestrictinfo = restrict_clauses;
2262 7071 : pathnode->path_hashclauses = hashclauses;
2263 : /* final_cost_hashjoin will fill in pathnode->num_batches */
2264 :
2265 7071 : final_cost_hashjoin(root, pathnode, workspace, extra);
2266 :
2267 7071 : return pathnode;
2268 : }
2269 :
2270 : /*
2271 : * create_projection_path
2272 : * Creates a pathnode that represents performing a projection.
2273 : *
2274 : * 'rel' is the parent relation associated with the result
2275 : * 'subpath' is the path representing the source of data
2276 : * 'target' is the PathTarget to be computed
2277 : */
2278 : ProjectionPath *
2279 801 : create_projection_path(PlannerInfo *root,
2280 : RelOptInfo *rel,
2281 : Path *subpath,
2282 : PathTarget *target)
2283 : {
2284 801 : ProjectionPath *pathnode = makeNode(ProjectionPath);
2285 801 : PathTarget *oldtarget = subpath->pathtarget;
2286 :
2287 801 : pathnode->path.pathtype = T_Result;
2288 801 : pathnode->path.parent = rel;
2289 801 : pathnode->path.pathtarget = target;
2290 : /* For now, assume we are above any joins, so no parameterization */
2291 801 : pathnode->path.param_info = NULL;
2292 801 : pathnode->path.parallel_aware = false;
2293 2243 : pathnode->path.parallel_safe = rel->consider_parallel &&
2294 1425 : subpath->parallel_safe &&
2295 624 : is_parallel_safe(root, (Node *) target->exprs);
2296 801 : pathnode->path.parallel_workers = subpath->parallel_workers;
2297 : /* Projection does not change the sort order */
2298 801 : pathnode->path.pathkeys = subpath->pathkeys;
2299 :
2300 801 : pathnode->subpath = subpath;
2301 :
2302 : /*
2303 : * We might not need a separate Result node. If the input plan node type
2304 : * can project, we can just tell it to project something else. Or, if it
2305 : * can't project but the desired target has the same expression list as
2306 : * what the input will produce anyway, we can still give it the desired
2307 : * tlist (possibly changing its ressortgroupref labels, but nothing else).
2308 : * Note: in the latter case, create_projection_plan has to recheck our
2309 : * conclusion; see comments therein.
2310 : */
2311 1529 : if (is_projection_capable_path(subpath) ||
2312 728 : equal(oldtarget->exprs, target->exprs))
2313 : {
2314 : /* No separate Result node needed */
2315 652 : pathnode->dummypp = true;
2316 :
2317 : /*
2318 : * Set cost of plan as subpath's cost, adjusted for tlist replacement.
2319 : */
2320 652 : pathnode->path.rows = subpath->rows;
2321 1956 : pathnode->path.startup_cost = subpath->startup_cost +
2322 1304 : (target->cost.startup - oldtarget->cost.startup);
2323 3912 : pathnode->path.total_cost = subpath->total_cost +
2324 1304 : (target->cost.startup - oldtarget->cost.startup) +
2325 1956 : (target->cost.per_tuple - oldtarget->cost.per_tuple) * subpath->rows;
2326 : }
2327 : else
2328 : {
2329 : /* We really do need the Result node */
2330 149 : pathnode->dummypp = false;
2331 :
2332 : /*
2333 : * The Result node's cost is cpu_tuple_cost per row, plus the cost of
2334 : * evaluating the tlist. There is no qual to worry about.
2335 : */
2336 149 : pathnode->path.rows = subpath->rows;
2337 298 : pathnode->path.startup_cost = subpath->startup_cost +
2338 149 : target->cost.startup;
2339 596 : pathnode->path.total_cost = subpath->total_cost +
2340 149 : target->cost.startup +
2341 298 : (cpu_tuple_cost + target->cost.per_tuple) * subpath->rows;
2342 : }
2343 :
2344 801 : return pathnode;
2345 : }
2346 :
2347 : /*
2348 : * apply_projection_to_path
2349 : * Add a projection step, or just apply the target directly to given path.
2350 : *
2351 : * This has the same net effect as create_projection_path(), except that if
2352 : * a separate Result plan node isn't needed, we just replace the given path's
2353 : * pathtarget with the desired one. This must be used only when the caller
2354 : * knows that the given path isn't referenced elsewhere and so can be modified
2355 : * in-place.
2356 : *
2357 : * If the input path is a GatherPath, we try to push the new target down to
2358 : * its input as well; this is a yet more invasive modification of the input
2359 : * path, which create_projection_path() can't do.
2360 : *
2361 : * Note that we mustn't change the source path's parent link; so when it is
2362 : * add_path'd to "rel" things will be a bit inconsistent. So far that has
2363 : * not caused any trouble.
2364 : *
2365 : * 'rel' is the parent relation associated with the result
2366 : * 'path' is the path representing the source of data
2367 : * 'target' is the PathTarget to be computed
2368 : */
2369 : Path *
2370 26917 : apply_projection_to_path(PlannerInfo *root,
2371 : RelOptInfo *rel,
2372 : Path *path,
2373 : PathTarget *target)
2374 : {
2375 : QualCost oldcost;
2376 :
2377 : /*
2378 : * If given path can't project, we might need a Result node, so make a
2379 : * separate ProjectionPath.
2380 : */
2381 26917 : if (!is_projection_capable_path(path))
2382 572 : return (Path *) create_projection_path(root, rel, path, target);
2383 :
2384 : /*
2385 : * We can just jam the desired tlist into the existing path, being sure to
2386 : * update its cost estimates appropriately.
2387 : */
2388 26345 : oldcost = path->pathtarget->cost;
2389 26345 : path->pathtarget = target;
2390 :
2391 26345 : path->startup_cost += target->cost.startup - oldcost.startup;
2392 105380 : path->total_cost += target->cost.startup - oldcost.startup +
2393 79035 : (target->cost.per_tuple - oldcost.per_tuple) * path->rows;
2394 :
2395 : /*
2396 : * If the path happens to be a Gather path, we'd like to arrange for the
2397 : * subpath to return the required target list so that workers can help
2398 : * project. But if there is something that is not parallel-safe in the
2399 : * target expressions, then we can't.
2400 : */
2401 26374 : if (IsA(path, GatherPath) &&
2402 29 : is_parallel_safe(root, (Node *) target->exprs))
2403 27 : {
2404 27 : GatherPath *gpath = (GatherPath *) path;
2405 :
2406 : /*
2407 : * We always use create_projection_path here, even if the subpath is
2408 : * projection-capable, so as to avoid modifying the subpath in place.
2409 : * It seems unlikely at present that there could be any other
2410 : * references to the subpath, but better safe than sorry.
2411 : *
2412 : * Note that we don't change the GatherPath's cost estimates; it might
2413 : * be appropriate to do so, to reflect the fact that the bulk of the
2414 : * target evaluation will happen in workers.
2415 : */
2416 27 : gpath->subpath = (Path *)
2417 54 : create_projection_path(root,
2418 27 : gpath->subpath->parent,
2419 : gpath->subpath,
2420 : target);
2421 : }
2422 39955 : else if (path->parallel_safe &&
2423 13637 : !is_parallel_safe(root, (Node *) target->exprs))
2424 : {
2425 : /*
2426 : * We're inserting a parallel-restricted target list into a path
2427 : * currently marked parallel-safe, so we have to mark it as no longer
2428 : * safe.
2429 : */
2430 2912 : path->parallel_safe = false;
2431 : }
2432 :
2433 26345 : return path;
2434 : }
2435 :
2436 : /*
2437 : * create_set_projection_path
2438 : * Creates a pathnode that represents performing a projection that
2439 : * includes set-returning functions.
2440 : *
2441 : * 'rel' is the parent relation associated with the result
2442 : * 'subpath' is the path representing the source of data
2443 : * 'target' is the PathTarget to be computed
2444 : */
2445 : ProjectSetPath *
2446 232 : create_set_projection_path(PlannerInfo *root,
2447 : RelOptInfo *rel,
2448 : Path *subpath,
2449 : PathTarget *target)
2450 : {
2451 232 : ProjectSetPath *pathnode = makeNode(ProjectSetPath);
2452 : double tlist_rows;
2453 : ListCell *lc;
2454 :
2455 232 : pathnode->path.pathtype = T_ProjectSet;
2456 232 : pathnode->path.parent = rel;
2457 232 : pathnode->path.pathtarget = target;
2458 : /* For now, assume we are above any joins, so no parameterization */
2459 232 : pathnode->path.param_info = NULL;
2460 232 : pathnode->path.parallel_aware = false;
2461 606 : pathnode->path.parallel_safe = rel->consider_parallel &&
2462 372 : subpath->parallel_safe &&
2463 140 : is_parallel_safe(root, (Node *) target->exprs);
2464 232 : pathnode->path.parallel_workers = subpath->parallel_workers;
2465 : /* Projection does not change the sort order XXX? */
2466 232 : pathnode->path.pathkeys = subpath->pathkeys;
2467 :
2468 232 : pathnode->subpath = subpath;
2469 :
2470 : /*
2471 : * Estimate number of rows produced by SRFs for each row of input; if
2472 : * there's more than one in this node, use the maximum.
2473 : */
2474 232 : tlist_rows = 1;
2475 655 : foreach(lc, target->exprs)
2476 : {
2477 423 : Node *node = (Node *) lfirst(lc);
2478 : double itemrows;
2479 :
2480 423 : itemrows = expression_returns_set_rows(node);
2481 423 : if (tlist_rows < itemrows)
2482 205 : tlist_rows = itemrows;
2483 : }
2484 :
2485 : /*
2486 : * In addition to the cost of evaluating the tlist, charge cpu_tuple_cost
2487 : * per input row, and half of cpu_tuple_cost for each added output row.
2488 : * This is slightly bizarre maybe, but it's what 9.6 did; we may revisit
2489 : * this estimate later.
2490 : */
2491 232 : pathnode->path.rows = subpath->rows * tlist_rows;
2492 464 : pathnode->path.startup_cost = subpath->startup_cost +
2493 232 : target->cost.startup;
2494 1392 : pathnode->path.total_cost = subpath->total_cost +
2495 232 : target->cost.startup +
2496 464 : (cpu_tuple_cost + target->cost.per_tuple) * subpath->rows +
2497 464 : (pathnode->path.rows - subpath->rows) * cpu_tuple_cost / 2;
2498 :
2499 232 : return pathnode;
2500 : }
2501 :
2502 : /*
2503 : * create_sort_path
2504 : * Creates a pathnode that represents performing an explicit sort.
2505 : *
2506 : * 'rel' is the parent relation associated with the result
2507 : * 'subpath' is the path representing the source of data
2508 : * 'pathkeys' represents the desired sort order
2509 : * 'limit_tuples' is the estimated bound on the number of output tuples,
2510 : * or -1 if no LIMIT or couldn't estimate
2511 : */
2512 : SortPath *
2513 2927 : create_sort_path(PlannerInfo *root,
2514 : RelOptInfo *rel,
2515 : Path *subpath,
2516 : List *pathkeys,
2517 : double limit_tuples)
2518 : {
2519 2927 : SortPath *pathnode = makeNode(SortPath);
2520 :
2521 2927 : pathnode->path.pathtype = T_Sort;
2522 2927 : pathnode->path.parent = rel;
2523 : /* Sort doesn't project, so use source path's pathtarget */
2524 2927 : pathnode->path.pathtarget = subpath->pathtarget;
2525 : /* For now, assume we are above any joins, so no parameterization */
2526 2927 : pathnode->path.param_info = NULL;
2527 2927 : pathnode->path.parallel_aware = false;
2528 4715 : pathnode->path.parallel_safe = rel->consider_parallel &&
2529 1788 : subpath->parallel_safe;
2530 2927 : pathnode->path.parallel_workers = subpath->parallel_workers;
2531 2927 : pathnode->path.pathkeys = pathkeys;
2532 :
2533 2927 : pathnode->subpath = subpath;
2534 :
2535 5854 : cost_sort(&pathnode->path, root, pathkeys,
2536 : subpath->total_cost,
2537 : subpath->rows,
2538 2927 : subpath->pathtarget->width,
2539 : 0.0, /* XXX comparison_cost shouldn't be 0? */
2540 : work_mem, limit_tuples);
2541 :
2542 2927 : return pathnode;
2543 : }
2544 :
2545 : /*
2546 : * create_group_path
2547 : * Creates a pathnode that represents performing grouping of presorted input
2548 : *
2549 : * 'rel' is the parent relation associated with the result
2550 : * 'subpath' is the path representing the source of data
2551 : * 'target' is the PathTarget to be computed
2552 : * 'groupClause' is a list of SortGroupClause's representing the grouping
2553 : * 'qual' is the HAVING quals if any
2554 : * 'numGroups' is the estimated number of groups
2555 : */
2556 : GroupPath *
2557 51 : create_group_path(PlannerInfo *root,
2558 : RelOptInfo *rel,
2559 : Path *subpath,
2560 : PathTarget *target,
2561 : List *groupClause,
2562 : List *qual,
2563 : double numGroups)
2564 : {
2565 51 : GroupPath *pathnode = makeNode(GroupPath);
2566 :
2567 51 : pathnode->path.pathtype = T_Group;
2568 51 : pathnode->path.parent = rel;
2569 51 : pathnode->path.pathtarget = target;
2570 : /* For now, assume we are above any joins, so no parameterization */
2571 51 : pathnode->path.param_info = NULL;
2572 51 : pathnode->path.parallel_aware = false;
2573 75 : pathnode->path.parallel_safe = rel->consider_parallel &&
2574 24 : subpath->parallel_safe;
2575 51 : pathnode->path.parallel_workers = subpath->parallel_workers;
2576 : /* Group doesn't change sort ordering */
2577 51 : pathnode->path.pathkeys = subpath->pathkeys;
2578 :
2579 51 : pathnode->subpath = subpath;
2580 :
2581 51 : pathnode->groupClause = groupClause;
2582 51 : pathnode->qual = qual;
2583 :
2584 51 : cost_group(&pathnode->path, root,
2585 : list_length(groupClause),
2586 : numGroups,
2587 : subpath->startup_cost, subpath->total_cost,
2588 : subpath->rows);
2589 :
2590 : /* add tlist eval cost for each output row */
2591 51 : pathnode->path.startup_cost += target->cost.startup;
2592 153 : pathnode->path.total_cost += target->cost.startup +
2593 102 : target->cost.per_tuple * pathnode->path.rows;
2594 :
2595 51 : return pathnode;
2596 : }
2597 :
2598 : /*
2599 : * create_upper_unique_path
2600 : * Creates a pathnode that represents performing an explicit Unique step
2601 : * on presorted input.
2602 : *
2603 : * This produces a Unique plan node, but the use-case is so different from
2604 : * create_unique_path that it doesn't seem worth trying to merge the two.
2605 : *
2606 : * 'rel' is the parent relation associated with the result
2607 : * 'subpath' is the path representing the source of data
2608 : * 'numCols' is the number of grouping columns
2609 : * 'numGroups' is the estimated number of groups
2610 : *
2611 : * The input path must be sorted on the grouping columns, plus possibly
2612 : * additional columns; so the first numCols pathkeys are the grouping columns
2613 : */
2614 : UpperUniquePath *
2615 83 : create_upper_unique_path(PlannerInfo *root,
2616 : RelOptInfo *rel,
2617 : Path *subpath,
2618 : int numCols,
2619 : double numGroups)
2620 : {
2621 83 : UpperUniquePath *pathnode = makeNode(UpperUniquePath);
2622 :
2623 83 : pathnode->path.pathtype = T_Unique;
2624 83 : pathnode->path.parent = rel;
2625 : /* Unique doesn't project, so use source path's pathtarget */
2626 83 : pathnode->path.pathtarget = subpath->pathtarget;
2627 : /* For now, assume we are above any joins, so no parameterization */
2628 83 : pathnode->path.param_info = NULL;
2629 83 : pathnode->path.parallel_aware = false;
2630 136 : pathnode->path.parallel_safe = rel->consider_parallel &&
2631 53 : subpath->parallel_safe;
2632 83 : pathnode->path.parallel_workers = subpath->parallel_workers;
2633 : /* Unique doesn't change the input ordering */
2634 83 : pathnode->path.pathkeys = subpath->pathkeys;
2635 :
2636 83 : pathnode->subpath = subpath;
2637 83 : pathnode->numkeys = numCols;
2638 :
2639 : /*
2640 : * Charge one cpu_operator_cost per comparison per input tuple. We assume
2641 : * all columns get compared at most of the tuples. (XXX probably this is
2642 : * an overestimate.)
2643 : */
2644 83 : pathnode->path.startup_cost = subpath->startup_cost;
2645 166 : pathnode->path.total_cost = subpath->total_cost +
2646 83 : cpu_operator_cost * subpath->rows * numCols;
2647 83 : pathnode->path.rows = numGroups;
2648 :
2649 83 : return pathnode;
2650 : }
2651 :
2652 : /*
2653 : * create_agg_path
2654 : * Creates a pathnode that represents performing aggregation/grouping
2655 : *
2656 : * 'rel' is the parent relation associated with the result
2657 : * 'subpath' is the path representing the source of data
2658 : * 'target' is the PathTarget to be computed
2659 : * 'aggstrategy' is the Agg node's basic implementation strategy
2660 : * 'aggsplit' is the Agg node's aggregate-splitting mode
2661 : * 'groupClause' is a list of SortGroupClause's representing the grouping
2662 : * 'qual' is the HAVING quals if any
2663 : * 'aggcosts' contains cost info about the aggregate functions to be computed
2664 : * 'numGroups' is the estimated number of groups (1 if not grouping)
2665 : */
2666 : AggPath *
2667 2710 : create_agg_path(PlannerInfo *root,
2668 : RelOptInfo *rel,
2669 : Path *subpath,
2670 : PathTarget *target,
2671 : AggStrategy aggstrategy,
2672 : AggSplit aggsplit,
2673 : List *groupClause,
2674 : List *qual,
2675 : const AggClauseCosts *aggcosts,
2676 : double numGroups)
2677 : {
2678 2710 : AggPath *pathnode = makeNode(AggPath);
2679 :
2680 2710 : pathnode->path.pathtype = T_Agg;
2681 2710 : pathnode->path.parent = rel;
2682 2710 : pathnode->path.pathtarget = target;
2683 : /* For now, assume we are above any joins, so no parameterization */
2684 2710 : pathnode->path.param_info = NULL;
2685 2710 : pathnode->path.parallel_aware = false;
2686 4802 : pathnode->path.parallel_safe = rel->consider_parallel &&
2687 2092 : subpath->parallel_safe;
2688 2710 : pathnode->path.parallel_workers = subpath->parallel_workers;
2689 2710 : if (aggstrategy == AGG_SORTED)
2690 232 : pathnode->path.pathkeys = subpath->pathkeys; /* preserves order */
2691 : else
2692 2478 : pathnode->path.pathkeys = NIL; /* output is unordered */
2693 2710 : pathnode->subpath = subpath;
2694 :
2695 2710 : pathnode->aggstrategy = aggstrategy;
2696 2710 : pathnode->aggsplit = aggsplit;
2697 2710 : pathnode->numGroups = numGroups;
2698 2710 : pathnode->groupClause = groupClause;
2699 2710 : pathnode->qual = qual;
2700 :
2701 2710 : cost_agg(&pathnode->path, root,
2702 : aggstrategy, aggcosts,
2703 : list_length(groupClause), numGroups,
2704 : subpath->startup_cost, subpath->total_cost,
2705 : subpath->rows);
2706 :
2707 : /* add tlist eval cost for each output row */
2708 2710 : pathnode->path.startup_cost += target->cost.startup;
2709 8130 : pathnode->path.total_cost += target->cost.startup +
2710 5420 : target->cost.per_tuple * pathnode->path.rows;
2711 :
2712 2710 : return pathnode;
2713 : }
2714 :
2715 : /*
2716 : * create_groupingsets_path
2717 : * Creates a pathnode that represents performing GROUPING SETS aggregation
2718 : *
2719 : * GroupingSetsPath represents sorted grouping with one or more grouping sets.
2720 : * The input path's result must be sorted to match the last entry in
2721 : * rollup_groupclauses.
2722 : *
2723 : * 'rel' is the parent relation associated with the result
2724 : * 'subpath' is the path representing the source of data
2725 : * 'target' is the PathTarget to be computed
2726 : * 'having_qual' is the HAVING quals if any
2727 : * 'rollups' is a list of RollupData nodes
2728 : * 'agg_costs' contains cost info about the aggregate functions to be computed
2729 : * 'numGroups' is the estimated total number of groups
2730 : */
2731 : GroupingSetsPath *
2732 199 : create_groupingsets_path(PlannerInfo *root,
2733 : RelOptInfo *rel,
2734 : Path *subpath,
2735 : PathTarget *target,
2736 : List *having_qual,
2737 : AggStrategy aggstrategy,
2738 : List *rollups,
2739 : const AggClauseCosts *agg_costs,
2740 : double numGroups)
2741 : {
2742 199 : GroupingSetsPath *pathnode = makeNode(GroupingSetsPath);
2743 : ListCell *lc;
2744 199 : bool is_first = true;
2745 199 : bool is_first_sort = true;
2746 :
2747 : /* The topmost generated Plan node will be an Agg */
2748 199 : pathnode->path.pathtype = T_Agg;
2749 199 : pathnode->path.parent = rel;
2750 199 : pathnode->path.pathtarget = target;
2751 199 : pathnode->path.param_info = subpath->param_info;
2752 199 : pathnode->path.parallel_aware = false;
2753 285 : pathnode->path.parallel_safe = rel->consider_parallel &&
2754 86 : subpath->parallel_safe;
2755 199 : pathnode->path.parallel_workers = subpath->parallel_workers;
2756 199 : pathnode->subpath = subpath;
2757 :
2758 : /*
2759 : * Simplify callers by downgrading AGG_SORTED to AGG_PLAIN, and AGG_MIXED
2760 : * to AGG_HASHED, here if possible.
2761 : */
2762 288 : if (aggstrategy == AGG_SORTED &&
2763 137 : list_length(rollups) == 1 &&
2764 48 : ((RollupData *) linitial(rollups))->groupClause == NIL)
2765 7 : aggstrategy = AGG_PLAIN;
2766 :
2767 287 : if (aggstrategy == AGG_MIXED &&
2768 88 : list_length(rollups) == 1)
2769 0 : aggstrategy = AGG_HASHED;
2770 :
2771 : /*
2772 : * Output will be in sorted order by group_pathkeys if, and only if, there
2773 : * is a single rollup operation on a non-empty list of grouping
2774 : * expressions.
2775 : */
2776 199 : if (aggstrategy == AGG_SORTED && list_length(rollups) == 1)
2777 41 : pathnode->path.pathkeys = root->group_pathkeys;
2778 : else
2779 158 : pathnode->path.pathkeys = NIL;
2780 :
2781 199 : pathnode->aggstrategy = aggstrategy;
2782 199 : pathnode->rollups = rollups;
2783 199 : pathnode->qual = having_qual;
2784 :
2785 199 : Assert(rollups != NIL);
2786 199 : Assert(aggstrategy != AGG_PLAIN || list_length(rollups) == 1);
2787 199 : Assert(aggstrategy != AGG_MIXED || list_length(rollups) > 1);
2788 :
2789 696 : foreach(lc, rollups)
2790 : {
2791 497 : RollupData *rollup = lfirst(lc);
2792 497 : List *gsets = rollup->gsets;
2793 497 : int numGroupCols = list_length(linitial(gsets));
2794 :
2795 : /*
2796 : * In AGG_SORTED or AGG_PLAIN mode, the first rollup takes the
2797 : * (already-sorted) input, and following ones do their own sort.
2798 : *
2799 : * In AGG_HASHED mode, there is one rollup for each grouping set.
2800 : *
2801 : * In AGG_MIXED mode, the first rollups are hashed, the first
2802 : * non-hashed one takes the (already-sorted) input, and following ones
2803 : * do their own sort.
2804 : */
2805 497 : if (is_first)
2806 : {
2807 199 : cost_agg(&pathnode->path, root,
2808 : aggstrategy,
2809 : agg_costs,
2810 : numGroupCols,
2811 : rollup->numGroups,
2812 : subpath->startup_cost,
2813 : subpath->total_cost,
2814 : subpath->rows);
2815 199 : is_first = false;
2816 199 : if (!rollup->is_hashed)
2817 89 : is_first_sort = false;
2818 : }
2819 : else
2820 : {
2821 : Path sort_path; /* dummy for result of cost_sort */
2822 : Path agg_path; /* dummy for result of cost_agg */
2823 :
2824 298 : if (rollup->is_hashed || is_first_sort)
2825 : {
2826 : /*
2827 : * Account for cost of aggregation, but don't charge input
2828 : * cost again
2829 : */
2830 438 : cost_agg(&agg_path, root,
2831 219 : rollup->is_hashed ? AGG_HASHED : AGG_SORTED,
2832 : agg_costs,
2833 : numGroupCols,
2834 : rollup->numGroups,
2835 : 0.0, 0.0,
2836 : subpath->rows);
2837 438 : if (!rollup->is_hashed)
2838 88 : is_first_sort = false;
2839 : }
2840 : else
2841 : {
2842 : /* Account for cost of sort, but don't charge input cost again */
2843 158 : cost_sort(&sort_path, root, NIL,
2844 : 0.0,
2845 : subpath->rows,
2846 79 : subpath->pathtarget->width,
2847 : 0.0,
2848 : work_mem,
2849 : -1.0);
2850 :
2851 : /* Account for cost of aggregation */
2852 :
2853 79 : cost_agg(&agg_path, root,
2854 : AGG_SORTED,
2855 : agg_costs,
2856 : numGroupCols,
2857 : rollup->numGroups,
2858 : sort_path.startup_cost,
2859 : sort_path.total_cost,
2860 : sort_path.rows);
2861 : }
2862 :
2863 298 : pathnode->path.total_cost += agg_path.total_cost;
2864 298 : pathnode->path.rows += agg_path.rows;
2865 : }
2866 : }
2867 :
2868 : /* add tlist eval cost for each output row */
2869 199 : pathnode->path.startup_cost += target->cost.startup;
2870 597 : pathnode->path.total_cost += target->cost.startup +
2871 398 : target->cost.per_tuple * pathnode->path.rows;
2872 :
2873 199 : return pathnode;
2874 : }
2875 :
2876 : /*
2877 : * create_minmaxagg_path
2878 : * Creates a pathnode that represents computation of MIN/MAX aggregates
2879 : *
2880 : * 'rel' is the parent relation associated with the result
2881 : * 'target' is the PathTarget to be computed
2882 : * 'mmaggregates' is a list of MinMaxAggInfo structs
2883 : * 'quals' is the HAVING quals if any
2884 : */
2885 : MinMaxAggPath *
2886 86 : create_minmaxagg_path(PlannerInfo *root,
2887 : RelOptInfo *rel,
2888 : PathTarget *target,
2889 : List *mmaggregates,
2890 : List *quals)
2891 : {
2892 86 : MinMaxAggPath *pathnode = makeNode(MinMaxAggPath);
2893 : Cost initplan_cost;
2894 : ListCell *lc;
2895 :
2896 : /* The topmost generated Plan node will be a Result */
2897 86 : pathnode->path.pathtype = T_Result;
2898 86 : pathnode->path.parent = rel;
2899 86 : pathnode->path.pathtarget = target;
2900 : /* For now, assume we are above any joins, so no parameterization */
2901 86 : pathnode->path.param_info = NULL;
2902 86 : pathnode->path.parallel_aware = false;
2903 : /* A MinMaxAggPath implies use of subplans, so cannot be parallel-safe */
2904 86 : pathnode->path.parallel_safe = false;
2905 86 : pathnode->path.parallel_workers = 0;
2906 : /* Result is one unordered row */
2907 86 : pathnode->path.rows = 1;
2908 86 : pathnode->path.pathkeys = NIL;
2909 :
2910 86 : pathnode->mmaggregates = mmaggregates;
2911 86 : pathnode->quals = quals;
2912 :
2913 : /* Calculate cost of all the initplans ... */
2914 86 : initplan_cost = 0;
2915 178 : foreach(lc, mmaggregates)
2916 : {
2917 92 : MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);
2918 :
2919 92 : initplan_cost += mminfo->pathcost;
2920 : }
2921 :
2922 : /* add tlist eval cost for each output row, plus cpu_tuple_cost */
2923 86 : pathnode->path.startup_cost = initplan_cost + target->cost.startup;
2924 172 : pathnode->path.total_cost = initplan_cost + target->cost.startup +
2925 86 : target->cost.per_tuple + cpu_tuple_cost;
2926 :
2927 86 : return pathnode;
2928 : }
2929 :
2930 : /*
2931 : * create_windowagg_path
2932 : * Creates a pathnode that represents computation of window functions
2933 : *
2934 : * 'rel' is the parent relation associated with the result
2935 : * 'subpath' is the path representing the source of data
2936 : * 'target' is the PathTarget to be computed
2937 : * 'windowFuncs' is a list of WindowFunc structs
2938 : * 'winclause' is a WindowClause that is common to all the WindowFuncs
2939 : * 'winpathkeys' is the pathkeys for the PARTITION keys + ORDER keys
2940 : *
2941 : * The actual sort order of the input must match winpathkeys, but might
2942 : * have additional keys after those.
2943 : */
2944 : WindowAggPath *
2945 147 : create_windowagg_path(PlannerInfo *root,
2946 : RelOptInfo *rel,
2947 : Path *subpath,
2948 : PathTarget *target,
2949 : List *windowFuncs,
2950 : WindowClause *winclause,
2951 : List *winpathkeys)
2952 : {
2953 147 : WindowAggPath *pathnode = makeNode(WindowAggPath);
2954 :
2955 147 : pathnode->path.pathtype = T_WindowAgg;
2956 147 : pathnode->path.parent = rel;
2957 147 : pathnode->path.pathtarget = target;
2958 : /* For now, assume we are above any joins, so no parameterization */
2959 147 : pathnode->path.param_info = NULL;
2960 147 : pathnode->path.parallel_aware = false;
2961 254 : pathnode->path.parallel_safe = rel->consider_parallel &&
2962 107 : subpath->parallel_safe;
2963 147 : pathnode->path.parallel_workers = subpath->parallel_workers;
2964 : /* WindowAgg preserves the input sort order */
2965 147 : pathnode->path.pathkeys = subpath->pathkeys;
2966 :
2967 147 : pathnode->subpath = subpath;
2968 147 : pathnode->winclause = winclause;
2969 147 : pathnode->winpathkeys = winpathkeys;
2970 :
2971 : /*
2972 : * For costing purposes, assume that there are no redundant partitioning
2973 : * or ordering columns; it's not worth the trouble to deal with that
2974 : * corner case here. So we just pass the unmodified list lengths to
2975 : * cost_windowagg.
2976 : */
2977 441 : cost_windowagg(&pathnode->path, root,
2978 : windowFuncs,
2979 147 : list_length(winclause->partitionClause),
2980 147 : list_length(winclause->orderClause),
2981 : subpath->startup_cost,
2982 : subpath->total_cost,
2983 : subpath->rows);
2984 :
2985 : /* add tlist eval cost for each output row */
2986 147 : pathnode->path.startup_cost += target->cost.startup;
2987 441 : pathnode->path.total_cost += target->cost.startup +
2988 294 : target->cost.per_tuple * pathnode->path.rows;
2989 :
2990 147 : return pathnode;
2991 : }
2992 :
2993 : /*
2994 : * create_setop_path
2995 : * Creates a pathnode that represents computation of INTERSECT or EXCEPT
2996 : *
2997 : * 'rel' is the parent relation associated with the result
2998 : * 'subpath' is the path representing the source of data
2999 : * 'cmd' is the specific semantics (INTERSECT or EXCEPT, with/without ALL)
3000 : * 'strategy' is the implementation strategy (sorted or hashed)
3001 : * 'distinctList' is a list of SortGroupClause's representing the grouping
3002 : * 'flagColIdx' is the column number where the flag column will be, if any
3003 : * 'firstFlag' is the flag value for the first input relation when hashing;
3004 : * or -1 when sorting
3005 : * 'numGroups' is the estimated number of distinct groups
3006 : * 'outputRows' is the estimated number of output rows
3007 : */
3008 : SetOpPath *
3009 37 : create_setop_path(PlannerInfo *root,
3010 : RelOptInfo *rel,
3011 : Path *subpath,
3012 : SetOpCmd cmd,
3013 : SetOpStrategy strategy,
3014 : List *distinctList,
3015 : AttrNumber flagColIdx,
3016 : int firstFlag,
3017 : double numGroups,
3018 : double outputRows)
3019 : {
3020 37 : SetOpPath *pathnode = makeNode(SetOpPath);
3021 :
3022 37 : pathnode->path.pathtype = T_SetOp;
3023 37 : pathnode->path.parent = rel;
3024 : /* SetOp doesn't project, so use source path's pathtarget */
3025 37 : pathnode->path.pathtarget = subpath->pathtarget;
3026 : /* For now, assume we are above any joins, so no parameterization */
3027 37 : pathnode->path.param_info = NULL;
3028 37 : pathnode->path.parallel_aware = false;
3029 37 : pathnode->path.parallel_safe = rel->consider_parallel &&
3030 0 : subpath->parallel_safe;
3031 37 : pathnode->path.parallel_workers = subpath->parallel_workers;
3032 : /* SetOp preserves the input sort order if in sort mode */
3033 37 : pathnode->path.pathkeys =
3034 37 : (strategy == SETOP_SORTED) ? subpath->pathkeys : NIL;
3035 :
3036 37 : pathnode->subpath = subpath;
3037 37 : pathnode->cmd = cmd;
3038 37 : pathnode->strategy = strategy;
3039 37 : pathnode->distinctList = distinctList;
3040 37 : pathnode->flagColIdx = flagColIdx;
3041 37 : pathnode->firstFlag = firstFlag;
3042 37 : pathnode->numGroups = numGroups;
3043 :
3044 : /*
3045 : * Charge one cpu_operator_cost per comparison per input tuple. We assume
3046 : * all columns get compared at most of the tuples.
3047 : */
3048 37 : pathnode->path.startup_cost = subpath->startup_cost;
3049 111 : pathnode->path.total_cost = subpath->total_cost +
3050 74 : cpu_operator_cost * subpath->rows * list_length(distinctList);
3051 37 : pathnode->path.rows = outputRows;
3052 :
3053 37 : return pathnode;
3054 : }
3055 :
3056 : /*
3057 : * create_recursiveunion_path
3058 : * Creates a pathnode that represents a recursive UNION node
3059 : *
3060 : * 'rel' is the parent relation associated with the result
3061 : * 'leftpath' is the source of data for the non-recursive term
3062 : * 'rightpath' is the source of data for the recursive term
3063 : * 'target' is the PathTarget to be computed
3064 : * 'distinctList' is a list of SortGroupClause's representing the grouping
3065 : * 'wtParam' is the ID of Param representing work table
3066 : * 'numGroups' is the estimated number of groups
3067 : *
3068 : * For recursive UNION ALL, distinctList is empty and numGroups is zero
3069 : */
3070 : RecursiveUnionPath *
3071 40 : create_recursiveunion_path(PlannerInfo *root,
3072 : RelOptInfo *rel,
3073 : Path *leftpath,
3074 : Path *rightpath,
3075 : PathTarget *target,
3076 : List *distinctList,
3077 : int wtParam,
3078 : double numGroups)
3079 : {
3080 40 : RecursiveUnionPath *pathnode = makeNode(RecursiveUnionPath);
3081 :
3082 40 : pathnode->path.pathtype = T_RecursiveUnion;
3083 40 : pathnode->path.parent = rel;
3084 40 : pathnode->path.pathtarget = target;
3085 : /* For now, assume we are above any joins, so no parameterization */
3086 40 : pathnode->path.param_info = NULL;
3087 40 : pathnode->path.parallel_aware = false;
3088 80 : pathnode->path.parallel_safe = rel->consider_parallel &&
3089 40 : leftpath->parallel_safe && rightpath->parallel_safe;
3090 : /* Foolish, but we'll do it like joins for now: */
3091 40 : pathnode->path.parallel_workers = leftpath->parallel_workers;
3092 : /* RecursiveUnion result is always unsorted */
3093 40 : pathnode->path.pathkeys = NIL;
3094 :
3095 40 : pathnode->leftpath = leftpath;
3096 40 : pathnode->rightpath = rightpath;
3097 40 : pathnode->distinctList = distinctList;
3098 40 : pathnode->wtParam = wtParam;
3099 40 : pathnode->numGroups = numGroups;
3100 :
3101 40 : cost_recursive_union(&pathnode->path, leftpath, rightpath);
3102 :
3103 40 : return pathnode;
3104 : }
3105 :
3106 : /*
3107 : * create_lockrows_path
3108 : * Creates a pathnode that represents acquiring row locks
3109 : *
3110 : * 'rel' is the parent relation associated with the result
3111 : * 'subpath' is the path representing the source of data
3112 : * 'rowMarks' is a list of PlanRowMark's
3113 : * 'epqParam' is the ID of Param for EvalPlanQual re-eval
3114 : */
3115 : LockRowsPath *
3116 313 : create_lockrows_path(PlannerInfo *root, RelOptInfo *rel,
3117 : Path *subpath, List *rowMarks, int epqParam)
3118 : {
3119 313 : LockRowsPath *pathnode = makeNode(LockRowsPath);
3120 :
3121 313 : pathnode->path.pathtype = T_LockRows;
3122 313 : pathnode->path.parent = rel;
3123 : /* LockRows doesn't project, so use source path's pathtarget */
3124 313 : pathnode->path.pathtarget = subpath->pathtarget;
3125 : /* For now, assume we are above any joins, so no parameterization */
3126 313 : pathnode->path.param_info = NULL;
3127 313 : pathnode->path.parallel_aware = false;
3128 313 : pathnode->path.parallel_safe = false;
3129 313 : pathnode->path.parallel_workers = 0;
3130 313 : pathnode->path.rows = subpath->rows;
3131 :
3132 : /*
3133 : * The result cannot be assumed sorted, since locking might cause the sort
3134 : * key columns to be replaced with new values.
3135 : */
3136 313 : pathnode->path.pathkeys = NIL;
3137 :
3138 313 : pathnode->subpath = subpath;
3139 313 : pathnode->rowMarks = rowMarks;
3140 313 : pathnode->epqParam = epqParam;
3141 :
3142 : /*
3143 : * We should charge something extra for the costs of row locking and
3144 : * possible refetches, but it's hard to say how much. For now, use
3145 : * cpu_tuple_cost per row.
3146 : */
3147 313 : pathnode->path.startup_cost = subpath->startup_cost;
3148 626 : pathnode->path.total_cost = subpath->total_cost +
3149 313 : cpu_tuple_cost * subpath->rows;
3150 :
3151 313 : return pathnode;
3152 : }
3153 :
3154 : /*
3155 : * create_modifytable_path
3156 : * Creates a pathnode that represents performing INSERT/UPDATE/DELETE mods
3157 : *
3158 : * 'rel' is the parent relation associated with the result
3159 : * 'operation' is the operation type
3160 : * 'canSetTag' is true if we set the command tag/es_processed
3161 : * 'nominalRelation' is the parent RT index for use of EXPLAIN
3162 : * 'partitioned_rels' is an integer list of RT indexes of non-leaf tables in
3163 : * the partition tree, if this is an UPDATE/DELETE to a partitioned table.
3164 : * Otherwise NIL.
3165 : * 'resultRelations' is an integer list of actual RT indexes of target rel(s)
3166 : * 'subpaths' is a list of Path(s) producing source data (one per rel)
3167 : * 'subroots' is a list of PlannerInfo structs (one per rel)
3168 : * 'withCheckOptionLists' is a list of WCO lists (one per rel)
3169 : * 'returningLists' is a list of RETURNING tlists (one per rel)
3170 : * 'rowMarks' is a list of PlanRowMarks (non-locking only)
3171 : * 'onconflict' is the ON CONFLICT clause, or NULL
3172 : * 'epqParam' is the ID of Param for EvalPlanQual re-eval
3173 : */
3174 : ModifyTablePath *
3175 4339 : create_modifytable_path(PlannerInfo *root, RelOptInfo *rel,
3176 : CmdType operation, bool canSetTag,
3177 : Index nominalRelation, List *partitioned_rels,
3178 : List *resultRelations, List *subpaths,
3179 : List *subroots,
3180 : List *withCheckOptionLists, List *returningLists,
3181 : List *rowMarks, OnConflictExpr *onconflict,
3182 : int epqParam)
3183 : {
3184 4339 : ModifyTablePath *pathnode = makeNode(ModifyTablePath);
3185 : double total_size;
3186 : ListCell *lc;
3187 :
3188 4339 : Assert(list_length(resultRelations) == list_length(subpaths));
3189 4339 : Assert(list_length(resultRelations) == list_length(subroots));
3190 4339 : Assert(withCheckOptionLists == NIL ||
3191 : list_length(resultRelations) == list_length(withCheckOptionLists));
3192 4339 : Assert(returningLists == NIL ||
3193 : list_length(resultRelations) == list_length(returningLists));
3194 :
3195 4339 : pathnode->path.pathtype = T_ModifyTable;
3196 4339 : pathnode->path.parent = rel;
3197 : /* pathtarget is not interesting, just make it minimally valid */
3198 4339 : pathnode->path.pathtarget = rel->reltarget;
3199 : /* For now, assume we are above any joins, so no parameterization */
3200 4339 : pathnode->path.param_info = NULL;
3201 4339 : pathnode->path.parallel_aware = false;
3202 4339 : pathnode->path.parallel_safe = false;
3203 4339 : pathnode->path.parallel_workers = 0;
3204 4339 : pathnode->path.pathkeys = NIL;
3205 :
3206 : /*
3207 : * Compute cost & rowcount as sum of subpath costs & rowcounts.
3208 : *
3209 : * Currently, we don't charge anything extra for the actual table
3210 : * modification work, nor for the WITH CHECK OPTIONS or RETURNING
3211 : * expressions if any. It would only be window dressing, since
3212 : * ModifyTable is always a top-level node and there is no way for the
3213 : * costs to change any higher-level planning choices. But we might want
3214 : * to make it look better sometime.
3215 : */
3216 4339 : pathnode->path.startup_cost = 0;
3217 4339 : pathnode->path.total_cost = 0;
3218 4339 : pathnode->path.rows = 0;
3219 4339 : total_size = 0;
3220 8794 : foreach(lc, subpaths)
3221 : {
3222 4455 : Path *subpath = (Path *) lfirst(lc);
3223 :
3224 4455 : if (lc == list_head(subpaths)) /* first node? */
3225 4339 : pathnode->path.startup_cost = subpath->startup_cost;
3226 4455 : pathnode->path.total_cost += subpath->total_cost;
3227 4455 : pathnode->path.rows += subpath->rows;
3228 4455 : total_size += subpath->pathtarget->width * subpath->rows;
3229 : }
3230 :
3231 : /*
3232 : * Set width to the average width of the subpath outputs. XXX this is
3233 : * totally wrong: we should report zero if no RETURNING, else an average
3234 : * of the RETURNING tlist widths. But it's what happened historically,
3235 : * and improving it is a task for another day.
3236 : */
3237 4339 : if (pathnode->path.rows > 0)
3238 4333 : total_size /= pathnode->path.rows;
3239 4339 : pathnode->path.pathtarget->width = rint(total_size);
3240 :
3241 4339 : pathnode->operation = operation;
3242 4339 : pathnode->canSetTag = canSetTag;
3243 4339 : pathnode->nominalRelation = nominalRelation;
3244 4339 : pathnode->partitioned_rels = list_copy(partitioned_rels);
3245 4339 : pathnode->resultRelations = resultRelations;
3246 4339 : pathnode->subpaths = subpaths;
3247 4339 : pathnode->subroots = subroots;
3248 4339 : pathnode->withCheckOptionLists = withCheckOptionLists;
3249 4339 : pathnode->returningLists = returningLists;
3250 4339 : pathnode->rowMarks = rowMarks;
3251 4339 : pathnode->onconflict = onconflict;
3252 4339 : pathnode->epqParam = epqParam;
3253 :
3254 4339 : return pathnode;
3255 : }
3256 :
3257 : /*
3258 : * create_limit_path
3259 : * Creates a pathnode that represents performing LIMIT/OFFSET
3260 : *
3261 : * In addition to providing the actual OFFSET and LIMIT expressions,
3262 : * the caller must provide estimates of their values for costing purposes.
3263 : * The estimates are as computed by preprocess_limit(), ie, 0 represents
3264 : * the clause not being present, and -1 means it's present but we could
3265 : * not estimate its value.
3266 : *
3267 : * 'rel' is the parent relation associated with the result
3268 : * 'subpath' is the path representing the source of data
3269 : * 'limitOffset' is the actual OFFSET expression, or NULL
3270 : * 'limitCount' is the actual LIMIT expression, or NULL
3271 : * 'offset_est' is the estimated value of the OFFSET expression
3272 : * 'count_est' is the estimated value of the LIMIT expression
3273 : */
3274 : LimitPath *
3275 205 : create_limit_path(PlannerInfo *root, RelOptInfo *rel,
3276 : Path *subpath,
3277 : Node *limitOffset, Node *limitCount,
3278 : int64 offset_est, int64 count_est)
3279 : {
3280 205 : LimitPath *pathnode = makeNode(LimitPath);
3281 :
3282 205 : pathnode->path.pathtype = T_Limit;
3283 205 : pathnode->path.parent = rel;
3284 : /* Limit doesn't project, so use source path's pathtarget */
3285 205 : pathnode->path.pathtarget = subpath->pathtarget;
3286 : /* For now, assume we are above any joins, so no parameterization */
3287 205 : pathnode->path.param_info = NULL;
3288 205 : pathnode->path.parallel_aware = false;
3289 286 : pathnode->path.parallel_safe = rel->consider_parallel &&
3290 81 : subpath->parallel_safe;
3291 205 : pathnode->path.parallel_workers = subpath->parallel_workers;
3292 205 : pathnode->path.rows = subpath->rows;
3293 205 : pathnode->path.startup_cost = subpath->startup_cost;
3294 205 : pathnode->path.total_cost = subpath->total_cost;
3295 205 : pathnode->path.pathkeys = subpath->pathkeys;
3296 205 : pathnode->subpath = subpath;
3297 205 : pathnode->limitOffset = limitOffset;
3298 205 : pathnode->limitCount = limitCount;
3299 :
3300 : /*
3301 : * Adjust the output rows count and costs according to the offset/limit.
3302 : * This is only a cosmetic issue if we are at top level, but if we are
3303 : * building a subquery then it's important to report correct info to the
3304 : * outer planner.
3305 : *
3306 : * When the offset or count couldn't be estimated, use 10% of the
3307 : * estimated number of rows emitted from the subpath.
3308 : *
3309 : * XXX we don't bother to add eval costs of the offset/limit expressions
3310 : * themselves to the path costs. In theory we should, but in most cases
3311 : * those expressions are trivial and it's just not worth the trouble.
3312 : */
3313 205 : if (offset_est != 0)
3314 : {
3315 : double offset_rows;
3316 :
3317 19 : if (offset_est > 0)
3318 15 : offset_rows = (double) offset_est;
3319 : else
3320 4 : offset_rows = clamp_row_est(subpath->rows * 0.10);
3321 19 : if (offset_rows > pathnode->path.rows)
3322 1 : offset_rows = pathnode->path.rows;
3323 19 : if (subpath->rows > 0)
3324 76 : pathnode->path.startup_cost +=
3325 38 : (subpath->total_cost - subpath->startup_cost)
3326 19 : * offset_rows / subpath->rows;
3327 19 : pathnode->path.rows -= offset_rows;
3328 19 : if (pathnode->path.rows < 1)
3329 1 : pathnode->path.rows = 1;
3330 : }
3331 :
3332 205 : if (count_est != 0)
3333 : {
3334 : double count_rows;
3335 :
3336 201 : if (count_est > 0)
3337 200 : count_rows = (double) count_est;
3338 : else
3339 1 : count_rows = clamp_row_est(subpath->rows * 0.10);
3340 201 : if (count_rows > pathnode->path.rows)
3341 4 : count_rows = pathnode->path.rows;
3342 201 : if (subpath->rows > 0)
3343 804 : pathnode->path.total_cost = pathnode->path.startup_cost +
3344 402 : (subpath->total_cost - subpath->startup_cost)
3345 201 : * count_rows / subpath->rows;
3346 201 : pathnode->path.rows = count_rows;
3347 201 : if (pathnode->path.rows < 1)
3348 0 : pathnode->path.rows = 1;
3349 : }
3350 :
3351 205 : return pathnode;
3352 : }
3353 :
3354 :
3355 : /*
3356 : * reparameterize_path
3357 : * Attempt to modify a Path to have greater parameterization
3358 : *
3359 : * We use this to attempt to bring all child paths of an appendrel to the
3360 : * same parameterization level, ensuring that they all enforce the same set
3361 : * of join quals (and thus that that parameterization can be attributed to
3362 : * an append path built from such paths). Currently, only a few path types
3363 : * are supported here, though more could be added at need. We return NULL
3364 : * if we can't reparameterize the given path.
3365 : *
3366 : * Note: we intentionally do not pass created paths to add_path(); it would
3367 : * possibly try to delete them on the grounds of being cost-inferior to the
3368 : * paths they were made from, and we don't want that. Paths made here are
3369 : * not necessarily of general-purpose usefulness, but they can be useful
3370 : * as members of an append path.
3371 : */
3372 : Path *
3373 40 : reparameterize_path(PlannerInfo *root, Path *path,
3374 : Relids required_outer,
3375 : double loop_count)
3376 : {
3377 40 : RelOptInfo *rel = path->parent;
3378 :
3379 : /* Can only increase, not decrease, path's parameterization */
3380 40 : if (!bms_is_subset(PATH_REQ_OUTER(path), required_outer))
3381 0 : return NULL;
3382 40 : switch (path->pathtype)
3383 : {
3384 : case T_SeqScan:
3385 24 : return create_seqscan_path(root, rel, required_outer, 0);
3386 : case T_SampleScan:
3387 0 : return (Path *) create_samplescan_path(root, rel, required_outer);
3388 : case T_IndexScan:
3389 : case T_IndexOnlyScan:
3390 : {
3391 0 : IndexPath *ipath = (IndexPath *) path;
3392 0 : IndexPath *newpath = makeNode(IndexPath);
3393 :
3394 : /*
3395 : * We can't use create_index_path directly, and would not want
3396 : * to because it would re-compute the indexqual conditions
3397 : * which is wasted effort. Instead we hack things a bit:
3398 : * flat-copy the path node, revise its param_info, and redo
3399 : * the cost estimate.
3400 : */
3401 0 : memcpy(newpath, ipath, sizeof(IndexPath));
3402 0 : newpath->path.param_info =
3403 0 : get_baserel_parampathinfo(root, rel, required_outer);
3404 0 : cost_index(newpath, root, loop_count, false);
3405 0 : return (Path *) newpath;
3406 : }
3407 : case T_BitmapHeapScan:
3408 : {
3409 0 : BitmapHeapPath *bpath = (BitmapHeapPath *) path;
3410 :
3411 0 : return (Path *) create_bitmap_heap_path(root,
3412 : rel,
3413 : bpath->bitmapqual,
3414 : required_outer,
3415 : loop_count, 0);
3416 : }
3417 : case T_SubqueryScan:
3418 : {
3419 16 : SubqueryScanPath *spath = (SubqueryScanPath *) path;
3420 :
3421 16 : return (Path *) create_subqueryscan_path(root,
3422 : rel,
3423 : spath->subpath,
3424 : spath->path.pathkeys,
3425 : required_outer);
3426 : }
3427 : default:
3428 0 : break;
3429 : }
3430 0 : return NULL;
3431 : }
|
