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