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