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