PostgreSQL Source Code  git master
joinpath.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * joinpath.c
4  * Routines to find all possible paths for processing a set of joins
5  *
6  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/path/joinpath.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include <math.h>
18 
19 #include "executor/executor.h"
20 #include "foreign/fdwapi.h"
21 #include "nodes/nodeFuncs.h"
22 #include "optimizer/cost.h"
23 #include "optimizer/optimizer.h"
24 #include "optimizer/pathnode.h"
25 #include "optimizer/paths.h"
26 #include "optimizer/planmain.h"
27 #include "utils/typcache.h"
28 
29 /* Hook for plugins to get control in add_paths_to_joinrel() */
30 set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
31 
32 /*
33  * Paths parameterized by the parent can be considered to be parameterized by
34  * any of its child.
35  */
36 #define PATH_PARAM_BY_PARENT(path, rel) \
37  ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \
38  (rel)->top_parent_relids))
39 #define PATH_PARAM_BY_REL_SELF(path, rel) \
40  ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
41 
42 #define PATH_PARAM_BY_REL(path, rel) \
43  (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))
44 
45 static void try_partial_mergejoin_path(PlannerInfo *root,
46  RelOptInfo *joinrel,
47  Path *outer_path,
48  Path *inner_path,
49  List *pathkeys,
50  List *mergeclauses,
51  List *outersortkeys,
52  List *innersortkeys,
53  JoinType jointype,
54  JoinPathExtraData *extra);
55 static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
56  RelOptInfo *outerrel, RelOptInfo *innerrel,
57  JoinType jointype, JoinPathExtraData *extra);
58 static inline bool clause_sides_match_join(RestrictInfo *rinfo,
59  RelOptInfo *outerrel,
60  RelOptInfo *innerrel);
61 static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,
62  RelOptInfo *outerrel, RelOptInfo *innerrel,
63  JoinType jointype, JoinPathExtraData *extra);
64 static void consider_parallel_nestloop(PlannerInfo *root,
65  RelOptInfo *joinrel,
66  RelOptInfo *outerrel,
67  RelOptInfo *innerrel,
68  JoinType jointype,
69  JoinPathExtraData *extra);
70 static void consider_parallel_mergejoin(PlannerInfo *root,
71  RelOptInfo *joinrel,
72  RelOptInfo *outerrel,
73  RelOptInfo *innerrel,
74  JoinType jointype,
75  JoinPathExtraData *extra,
76  Path *inner_cheapest_total);
77 static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
78  RelOptInfo *outerrel, RelOptInfo *innerrel,
79  JoinType jointype, JoinPathExtraData *extra);
80 static List *select_mergejoin_clauses(PlannerInfo *root,
81  RelOptInfo *joinrel,
82  RelOptInfo *outerrel,
83  RelOptInfo *innerrel,
84  List *restrictlist,
85  JoinType jointype,
86  bool *mergejoin_allowed);
87 static void generate_mergejoin_paths(PlannerInfo *root,
88  RelOptInfo *joinrel,
89  RelOptInfo *innerrel,
90  Path *outerpath,
91  JoinType jointype,
92  JoinPathExtraData *extra,
93  bool useallclauses,
94  Path *inner_cheapest_total,
95  List *merge_pathkeys,
96  bool is_partial);
97 
98 
99 /*
100  * add_paths_to_joinrel
101  * Given a join relation and two component rels from which it can be made,
102  * consider all possible paths that use the two component rels as outer
103  * and inner rel respectively. Add these paths to the join rel's pathlist
104  * if they survive comparison with other paths (and remove any existing
105  * paths that are dominated by these paths).
106  *
107  * Modifies the pathlist field of the joinrel node to contain the best
108  * paths found so far.
109  *
110  * jointype is not necessarily the same as sjinfo->jointype; it might be
111  * "flipped around" if we are considering joining the rels in the opposite
112  * direction from what's indicated in sjinfo.
113  *
114  * Also, this routine and others in this module accept the special JoinTypes
115  * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should
116  * unique-ify the outer or inner relation and then apply a regular inner
117  * join. These values are not allowed to propagate outside this module,
118  * however. Path cost estimation code may need to recognize that it's
119  * dealing with such a case --- the combination of nominal jointype INNER
120  * with sjinfo->jointype == JOIN_SEMI indicates that.
121  */
122 void
123 add_paths_to_joinrel(PlannerInfo *root,
124  RelOptInfo *joinrel,
125  RelOptInfo *outerrel,
126  RelOptInfo *innerrel,
127  JoinType jointype,
128  SpecialJoinInfo *sjinfo,
129  List *restrictlist)
130 {
131  JoinPathExtraData extra;
132  bool mergejoin_allowed = true;
133  ListCell *lc;
134  Relids joinrelids;
135 
136  /*
137  * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
138  * between child relations, even if there is a SpecialJoinInfo node for
139  * the join between the topmost parents. So, while calculating Relids set
140  * representing the restriction, consider relids of topmost parent of
141  * partitions.
142  */
143  if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
144  joinrelids = joinrel->top_parent_relids;
145  else
146  joinrelids = joinrel->relids;
147 
148  extra.restrictlist = restrictlist;
149  extra.mergeclause_list = NIL;
150  extra.sjinfo = sjinfo;
151  extra.param_source_rels = NULL;
152 
153  /*
154  * See if the inner relation is provably unique for this outer rel.
155  *
156  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
157  * matter since the executor can make the equivalent optimization anyway;
158  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
159  * must be considering a semijoin whose inner side is not provably unique
160  * (else reduce_unique_semijoins would've simplified it), so there's no
161  * point in calling innerrel_is_unique. However, if the LHS covers all of
162  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
163  * because the path produced by create_unique_path will be unique relative
164  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
165  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
166  * letting that value escape this module.
167  */
168  switch (jointype)
169  {
170  case JOIN_SEMI:
171  case JOIN_ANTI:
172 
173  /*
174  * XXX it may be worth proving this to allow a Memoize to be
175  * considered for Nested Loop Semi/Anti Joins.
176  */
177  extra.inner_unique = false; /* well, unproven */
178  break;
179  case JOIN_UNIQUE_INNER:
180  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
181  outerrel->relids);
182  break;
183  case JOIN_UNIQUE_OUTER:
184  extra.inner_unique = innerrel_is_unique(root,
185  joinrel->relids,
186  outerrel->relids,
187  innerrel,
188  JOIN_INNER,
189  restrictlist,
190  false);
191  break;
192  default:
193  extra.inner_unique = innerrel_is_unique(root,
194  joinrel->relids,
195  outerrel->relids,
196  innerrel,
197  jointype,
198  restrictlist,
199  false);
200  break;
201  }
202 
203  /*
204  * Find potential mergejoin clauses. We can skip this if we are not
205  * interested in doing a mergejoin. However, mergejoin may be our only
206  * way of implementing a full outer join, so override enable_mergejoin if
207  * it's a full join.
208  */
209  if (enable_mergejoin || jointype == JOIN_FULL)
210  extra.mergeclause_list = select_mergejoin_clauses(root,
211  joinrel,
212  outerrel,
213  innerrel,
214  restrictlist,
215  jointype,
216  &mergejoin_allowed);
217 
218  /*
219  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
220  * for cost estimation. These will be the same for all paths.
221  */
222  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
223  compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
224  jointype, sjinfo, restrictlist,
225  &extra.semifactors);
226 
227  /*
228  * Decide whether it's sensible to generate parameterized paths for this
229  * joinrel, and if so, which relations such paths should require. There
230  * is usually no need to create a parameterized result path unless there
231  * is a join order restriction that prevents joining one of our input rels
232  * directly to the parameter source rel instead of joining to the other
233  * input rel. (But see allow_star_schema_join().) This restriction
234  * reduces the number of parameterized paths we have to deal with at
235  * higher join levels, without compromising the quality of the resulting
236  * plan. We express the restriction as a Relids set that must overlap the
237  * parameterization of any proposed join path. Note: param_source_rels
238  * should contain only baserels, not OJ relids, so starting from
239  * all_baserels not all_query_rels is correct.
240  */
241  foreach(lc, root->join_info_list)
242  {
243  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
244 
245  /*
246  * SJ is relevant to this join if we have some part of its RHS
247  * (possibly not all of it), and haven't yet joined to its LHS. (This
248  * test is pretty simplistic, but should be sufficient considering the
249  * join has already been proven legal.) If the SJ is relevant, it
250  * presents constraints for joining to anything not in its RHS.
251  */
252  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
253  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
254  extra.param_source_rels = bms_join(extra.param_source_rels,
255  bms_difference(root->all_baserels,
256  sjinfo2->min_righthand));
257 
258  /* full joins constrain both sides symmetrically */
259  if (sjinfo2->jointype == JOIN_FULL &&
260  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
261  !bms_overlap(joinrelids, sjinfo2->min_righthand))
262  extra.param_source_rels = bms_join(extra.param_source_rels,
263  bms_difference(root->all_baserels,
264  sjinfo2->min_lefthand));
265  }
266 
267  /*
268  * However, when a LATERAL subquery is involved, there will simply not be
269  * any paths for the joinrel that aren't parameterized by whatever the
270  * subquery is parameterized by, unless its parameterization is resolved
271  * within the joinrel. So we might as well allow additional dependencies
272  * on whatever residual lateral dependencies the joinrel will have.
273  */
274  extra.param_source_rels = bms_add_members(extra.param_source_rels,
275  joinrel->lateral_relids);
276 
277  /*
278  * 1. Consider mergejoin paths where both relations must be explicitly
279  * sorted. Skip this if we can't mergejoin.
280  */
281  if (mergejoin_allowed)
282  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
283  jointype, &extra);
284 
285  /*
286  * 2. Consider paths where the outer relation need not be explicitly
287  * sorted. This includes both nestloops and mergejoins where the outer
288  * path is already ordered. Again, skip this if we can't mergejoin.
289  * (That's okay because we know that nestloop can't handle right/full
290  * joins at all, so it wouldn't work in the prohibited cases either.)
291  */
292  if (mergejoin_allowed)
293  match_unsorted_outer(root, joinrel, outerrel, innerrel,
294  jointype, &extra);
295 
296 #ifdef NOT_USED
297 
298  /*
299  * 3. Consider paths where the inner relation need not be explicitly
300  * sorted. This includes mergejoins only (nestloops were already built in
301  * match_unsorted_outer).
302  *
303  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
304  * significant difference between the inner and outer side of a mergejoin,
305  * so match_unsorted_inner creates no paths that aren't equivalent to
306  * those made by match_unsorted_outer when add_paths_to_joinrel() is
307  * invoked with the two rels given in the other order.
308  */
309  if (mergejoin_allowed)
310  match_unsorted_inner(root, joinrel, outerrel, innerrel,
311  jointype, &extra);
312 #endif
313 
314  /*
315  * 4. Consider paths where both outer and inner relations must be hashed
316  * before being joined. As above, disregard enable_hashjoin for full
317  * joins, because there may be no other alternative.
318  */
319  if (enable_hashjoin || jointype == JOIN_FULL)
320  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
321  jointype, &extra);
322 
323  /*
324  * 5. If inner and outer relations are foreign tables (or joins) belonging
325  * to the same server and assigned to the same user to check access
326  * permissions as, give the FDW a chance to push down joins.
327  */
328  if (joinrel->fdwroutine &&
329  joinrel->fdwroutine->GetForeignJoinPaths)
330  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
331  outerrel, innerrel,
332  jointype, &extra);
333 
334  /*
335  * 6. Finally, give extensions a chance to manipulate the path list.
336  */
337  if (set_join_pathlist_hook)
338  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
339  jointype, &extra);
340 }
341 
342 /*
343  * We override the param_source_rels heuristic to accept nestloop paths in
344  * which the outer rel satisfies some but not all of the inner path's
345  * parameterization. This is necessary to get good plans for star-schema
346  * scenarios, in which a parameterized path for a large table may require
347  * parameters from multiple small tables that will not get joined directly to
348  * each other. We can handle that by stacking nestloops that have the small
349  * tables on the outside; but this breaks the rule the param_source_rels
350  * heuristic is based on, namely that parameters should not be passed down
351  * across joins unless there's a join-order-constraint-based reason to do so.
352  * So we ignore the param_source_rels restriction when this case applies.
353  *
354  * allow_star_schema_join() returns true if the param_source_rels restriction
355  * should be overridden, ie, it's okay to perform this join.
356  */
357 static inline bool
358 allow_star_schema_join(PlannerInfo *root,
359  Relids outerrelids,
360  Relids inner_paramrels)
361 {
362  /*
363  * It's a star-schema case if the outer rel provides some but not all of
364  * the inner rel's parameterization.
365  */
366  return (bms_overlap(inner_paramrels, outerrelids) &&
367  bms_nonempty_difference(inner_paramrels, outerrelids));
368 }
369 
370 /*
371  * If the parameterization is only partly satisfied by the outer rel,
372  * the unsatisfied part can't include any outer-join relids that could
373  * null rels of the satisfied part. That would imply that we're trying
374  * to use a clause involving a Var with nonempty varnullingrels at
375  * a join level where that value isn't yet computable.
376  *
377  * In practice, this test never finds a problem because earlier join order
378  * restrictions prevent us from attempting a join that would cause a problem.
379  * (That's unsurprising, because the code worked before we ever added
380  * outer-join relids to expression relids.) It still seems worth checking
381  * as a backstop, but we only do so in assert-enabled builds.
382  */
383 #ifdef USE_ASSERT_CHECKING
384 static inline bool
385 have_unsafe_outer_join_ref(PlannerInfo *root,
386  Relids outerrelids,
387  Relids inner_paramrels)
388 {
389  bool result = false;
390  Relids unsatisfied = bms_difference(inner_paramrels, outerrelids);
391  Relids satisfied = bms_intersect(inner_paramrels, outerrelids);
392 
393  if (bms_overlap(unsatisfied, root->outer_join_rels))
394  {
395  ListCell *lc;
396 
397  foreach(lc, root->join_info_list)
398  {
399  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
400 
401  if (!bms_is_member(sjinfo->ojrelid, unsatisfied))
402  continue; /* not relevant */
403  if (bms_overlap(satisfied, sjinfo->min_righthand) ||
404  (sjinfo->jointype == JOIN_FULL &&
405  bms_overlap(satisfied, sjinfo->min_lefthand)))
406  {
407  result = true; /* doesn't work */
408  break;
409  }
410  }
411  }
412 
413  /* Waste no memory when we reject a path here */
414  bms_free(unsatisfied);
415  bms_free(satisfied);
416 
417  return result;
418 }
419 #endif /* USE_ASSERT_CHECKING */
420 
421 /*
422  * paraminfo_get_equal_hashops
423  * Determine if param_info and innerrel's lateral_vars can be hashed.
424  * Returns true the hashing is possible, otherwise return false.
425  *
426  * Additionally we also collect the outer exprs and the hash operators for
427  * each parameter to innerrel. These set in 'param_exprs', 'operators' and
428  * 'binary_mode' when we return true.
429  */
430 static bool
431 paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info,
432  RelOptInfo *outerrel, RelOptInfo *innerrel,
433  List **param_exprs, List **operators,
434  bool *binary_mode)
435 
436 {
437  ListCell *lc;
438 
439  *param_exprs = NIL;
440  *operators = NIL;
441  *binary_mode = false;
442 
443  if (param_info != NULL)
444  {
445  List *clauses = param_info->ppi_clauses;
446 
447  foreach(lc, clauses)
448  {
449  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
450  OpExpr *opexpr;
451  Node *expr;
452  Oid hasheqoperator;
453 
454  opexpr = (OpExpr *) rinfo->clause;
455 
456  /*
457  * Bail if the rinfo is not compatible. We need a join OpExpr
458  * with 2 args.
459  */
460  if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
461  !clause_sides_match_join(rinfo, outerrel, innerrel))
462  {
463  list_free(*operators);
464  list_free(*param_exprs);
465  return false;
466  }
467 
468  if (rinfo->outer_is_left)
469  {
470  expr = (Node *) linitial(opexpr->args);
471  hasheqoperator = rinfo->left_hasheqoperator;
472  }
473  else
474  {
475  expr = (Node *) lsecond(opexpr->args);
476  hasheqoperator = rinfo->right_hasheqoperator;
477  }
478 
479  /* can't do memoize if we can't hash the outer type */
480  if (!OidIsValid(hasheqoperator))
481  {
482  list_free(*operators);
483  list_free(*param_exprs);
484  return false;
485  }
486 
487  *operators = lappend_oid(*operators, hasheqoperator);
488  *param_exprs = lappend(*param_exprs, expr);
489 
490  /*
491  * When the join operator is not hashable then it's possible that
492  * the operator will be able to distinguish something that the
493  * hash equality operator could not. For example with floating
494  * point types -0.0 and +0.0 are classed as equal by the hash
495  * function and equality function, but some other operator may be
496  * able to tell those values apart. This means that we must put
497  * memoize into binary comparison mode so that it does bit-by-bit
498  * comparisons rather than a "logical" comparison as it would
499  * using the hash equality operator.
500  */
501  if (!OidIsValid(rinfo->hashjoinoperator))
502  *binary_mode = true;
503  }
504  }
505 
506  /* Now add any lateral vars to the cache key too */
507  foreach(lc, innerrel->lateral_vars)
508  {
509  Node *expr = (Node *) lfirst(lc);
510  TypeCacheEntry *typentry;
511 
512  /* Reject if there are any volatile functions */
513  if (contain_volatile_functions(expr))
514  {
515  list_free(*operators);
516  list_free(*param_exprs);
517  return false;
518  }
519 
520  typentry = lookup_type_cache(exprType(expr),
521  TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR);
522 
523  /* can't use a memoize node without a valid hash equals operator */
524  if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
525  {
526  list_free(*operators);
527  list_free(*param_exprs);
528  return false;
529  }
530 
531  *operators = lappend_oid(*operators, typentry->eq_opr);
532  *param_exprs = lappend(*param_exprs, expr);
533 
534  /*
535  * We must go into binary mode as we don't have too much of an idea of
536  * how these lateral Vars are being used. See comment above when we
537  * set *binary_mode for the non-lateral Var case. This could be
538  * relaxed a bit if we had the RestrictInfos and knew the operators
539  * being used, however for cases like Vars that are arguments to
540  * functions we must operate in binary mode as we don't have
541  * visibility into what the function is doing with the Vars.
542  */
543  *binary_mode = true;
544  }
545 
546  /* We're okay to use memoize */
547  return true;
548 }
549 
550 /*
551  * get_memoize_path
552  * If possible, make and return a Memoize path atop of 'inner_path'.
553  * Otherwise return NULL.
554  */
555 static Path *
556 get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
557  RelOptInfo *outerrel, Path *inner_path,
558  Path *outer_path, JoinType jointype,
559  JoinPathExtraData *extra)
560 {
561  List *param_exprs;
562  List *hash_operators;
563  ListCell *lc;
564  bool binary_mode;
565 
566  /* Obviously not if it's disabled */
567  if (!enable_memoize)
568  return NULL;
569 
570  /*
571  * We can safely not bother with all this unless we expect to perform more
572  * than one inner scan. The first scan is always going to be a cache
573  * miss. This would likely fail later anyway based on costs, so this is
574  * really just to save some wasted effort.
575  */
576  if (outer_path->parent->rows < 2)
577  return NULL;
578 
579  /*
580  * We can only have a memoize node when there's some kind of cache key,
581  * either parameterized path clauses or lateral Vars. No cache key sounds
582  * more like something a Materialize node might be more useful for.
583  */
584  if ((inner_path->param_info == NULL ||
585  inner_path->param_info->ppi_clauses == NIL) &&
586  innerrel->lateral_vars == NIL)
587  return NULL;
588 
589  /*
590  * Currently we don't do this for SEMI and ANTI joins unless they're
591  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
592  * don't scan the inner node to completion, which will mean memoize cannot
593  * mark the cache entry as complete.
594  *
595  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
596  * = true. Should we? See add_paths_to_joinrel()
597  */
598  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
599  jointype == JOIN_ANTI))
600  return NULL;
601 
602  /*
603  * Memoize normally marks cache entries as complete when it runs out of
604  * tuples to read from its subplan. However, with unique joins, Nested
605  * Loop will skip to the next outer tuple after finding the first matching
606  * inner tuple. This means that we may not read the inner side of the
607  * join to completion which leaves no opportunity to mark the cache entry
608  * as complete. To work around that, when the join is unique we
609  * automatically mark cache entries as complete after fetching the first
610  * tuple. This works when the entire join condition is parameterized.
611  * Otherwise, when the parameterization is only a subset of the join
612  * condition, we can't be sure which part of it causes the join to be
613  * unique. This means there are no guarantees that only 1 tuple will be
614  * read. We cannot mark the cache entry as complete after reading the
615  * first tuple without that guarantee. This means the scope of Memoize
616  * node's usefulness is limited to only outer rows that have no join
617  * partner as this is the only case where Nested Loop would exhaust the
618  * inner scan of a unique join. Since the scope is limited to that, we
619  * just don't bother making a memoize path in this case.
620  *
621  * Lateral vars needn't be considered here as they're not considered when
622  * determining if the join is unique.
623  *
624  * XXX this could be enabled if the remaining join quals were made part of
625  * the inner scan's filter instead of the join filter. Maybe it's worth
626  * considering doing that?
627  */
628  if (extra->inner_unique &&
629  (inner_path->param_info == NULL ||
630  list_length(inner_path->param_info->ppi_clauses) <
631  list_length(extra->restrictlist)))
632  return NULL;
633 
634  /*
635  * We can't use a memoize node if there are volatile functions in the
636  * inner rel's target list or restrict list. A cache hit could reduce the
637  * number of calls to these functions.
638  */
639  if (contain_volatile_functions((Node *) innerrel->reltarget))
640  return NULL;
641 
642  foreach(lc, innerrel->baserestrictinfo)
643  {
644  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
645 
646  if (contain_volatile_functions((Node *) rinfo))
647  return NULL;
648  }
649 
650  /* Check if we have hash ops for each parameter to the path */
651  if (paraminfo_get_equal_hashops(root,
652  inner_path->param_info,
653  outerrel->top_parent ?
654  outerrel->top_parent : outerrel,
655  innerrel,
656  &param_exprs,
657  &hash_operators,
658  &binary_mode))
659  {
660  return (Path *) create_memoize_path(root,
661  innerrel,
662  inner_path,
663  param_exprs,
664  hash_operators,
665  extra->inner_unique,
666  binary_mode,
667  outer_path->rows);
668  }
669 
670  return NULL;
671 }
672 
673 /*
674  * try_nestloop_path
675  * Consider a nestloop join path; if it appears useful, push it into
676  * the joinrel's pathlist via add_path().
677  */
678 static void
679 try_nestloop_path(PlannerInfo *root,
680  RelOptInfo *joinrel,
681  Path *outer_path,
682  Path *inner_path,
683  List *pathkeys,
684  JoinType jointype,
685  JoinPathExtraData *extra)
686 {
687  Relids required_outer;
688  JoinCostWorkspace workspace;
689  RelOptInfo *innerrel = inner_path->parent;
690  RelOptInfo *outerrel = outer_path->parent;
691  Relids innerrelids;
692  Relids outerrelids;
693  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
694  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
695 
696  /*
697  * Paths are parameterized by top-level parents, so run parameterization
698  * tests on the parent relids.
699  */
700  if (innerrel->top_parent_relids)
701  innerrelids = innerrel->top_parent_relids;
702  else
703  innerrelids = innerrel->relids;
704 
705  if (outerrel->top_parent_relids)
706  outerrelids = outerrel->top_parent_relids;
707  else
708  outerrelids = outerrel->relids;
709 
710  /*
711  * Check to see if proposed path is still parameterized, and reject if the
712  * parameterization wouldn't be sensible --- unless allow_star_schema_join
713  * says to allow it anyway. Also, we must reject if have_dangerous_phv
714  * doesn't like the look of it, which could only happen if the nestloop is
715  * still parameterized.
716  */
717  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
718  innerrelids, inner_paramrels);
719  if (required_outer &&
720  ((!bms_overlap(required_outer, extra->param_source_rels) &&
721  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
722  have_dangerous_phv(root, outerrelids, inner_paramrels)))
723  {
724  /* Waste no memory when we reject a path here */
725  bms_free(required_outer);
726  return;
727  }
728 
729  /* If we got past that, we shouldn't have any unsafe outer-join refs */
730  Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
731 
732  /*
733  * Do a precheck to quickly eliminate obviously-inferior paths. We
734  * calculate a cheap lower bound on the path's cost and then use
735  * add_path_precheck() to see if the path is clearly going to be dominated
736  * by some existing path for the joinrel. If not, do the full pushup with
737  * creating a fully valid path structure and submitting it to add_path().
738  * The latter two steps are expensive enough to make this two-phase
739  * methodology worthwhile.
740  */
741  initial_cost_nestloop(root, &workspace, jointype,
742  outer_path, inner_path, extra);
743 
744  if (add_path_precheck(joinrel,
745  workspace.startup_cost, workspace.total_cost,
746  pathkeys, required_outer))
747  {
748  /*
749  * If the inner path is parameterized, it is parameterized by the
750  * topmost parent of the outer rel, not the outer rel itself. Fix
751  * that.
752  */
753  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
754  {
755  inner_path = reparameterize_path_by_child(root, inner_path,
756  outer_path->parent);
757 
758  /*
759  * If we could not translate the path, we can't create nest loop
760  * path.
761  */
762  if (!inner_path)
763  {
764  bms_free(required_outer);
765  return;
766  }
767  }
768 
769  add_path(joinrel, (Path *)
770  create_nestloop_path(root,
771  joinrel,
772  jointype,
773  &workspace,
774  extra,
775  outer_path,
776  inner_path,
777  extra->restrictlist,
778  pathkeys,
779  required_outer));
780  }
781  else
782  {
783  /* Waste no memory when we reject a path here */
784  bms_free(required_outer);
785  }
786 }
787 
788 /*
789  * try_partial_nestloop_path
790  * Consider a partial nestloop join path; if it appears useful, push it into
791  * the joinrel's partial_pathlist via add_partial_path().
792  */
793 static void
794 try_partial_nestloop_path(PlannerInfo *root,
795  RelOptInfo *joinrel,
796  Path *outer_path,
797  Path *inner_path,
798  List *pathkeys,
799  JoinType jointype,
800  JoinPathExtraData *extra)
801 {
802  JoinCostWorkspace workspace;
803 
804  /*
805  * If the inner path is parameterized, the parameterization must be fully
806  * satisfied by the proposed outer path. Parameterized partial paths are
807  * not supported. The caller should already have verified that no lateral
808  * rels are required here.
809  */
810  Assert(bms_is_empty(joinrel->lateral_relids));
811  if (inner_path->param_info != NULL)
812  {
813  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
814  RelOptInfo *outerrel = outer_path->parent;
815  Relids outerrelids;
816 
817  /*
818  * The inner and outer paths are parameterized, if at all, by the top
819  * level parents, not the child relations, so we must use those relids
820  * for our parameterization tests.
821  */
822  if (outerrel->top_parent_relids)
823  outerrelids = outerrel->top_parent_relids;
824  else
825  outerrelids = outerrel->relids;
826 
827  if (!bms_is_subset(inner_paramrels, outerrelids))
828  return;
829  }
830 
831  /*
832  * Before creating a path, get a quick lower bound on what it is likely to
833  * cost. Bail out right away if it looks terrible.
834  */
835  initial_cost_nestloop(root, &workspace, jointype,
836  outer_path, inner_path, extra);
837  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
838  return;
839 
840  /*
841  * If the inner path is parameterized, it is parameterized by the topmost
842  * parent of the outer rel, not the outer rel itself. Fix that.
843  */
844  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
845  {
846  inner_path = reparameterize_path_by_child(root, inner_path,
847  outer_path->parent);
848 
849  /*
850  * If we could not translate the path, we can't create nest loop path.
851  */
852  if (!inner_path)
853  return;
854  }
855 
856  /* Might be good enough to be worth trying, so let's try it. */
857  add_partial_path(joinrel, (Path *)
858  create_nestloop_path(root,
859  joinrel,
860  jointype,
861  &workspace,
862  extra,
863  outer_path,
864  inner_path,
865  extra->restrictlist,
866  pathkeys,
867  NULL));
868 }
869 
870 /*
871  * try_mergejoin_path
872  * Consider a merge join path; if it appears useful, push it into
873  * the joinrel's pathlist via add_path().
874  */
875 static void
876 try_mergejoin_path(PlannerInfo *root,
877  RelOptInfo *joinrel,
878  Path *outer_path,
879  Path *inner_path,
880  List *pathkeys,
881  List *mergeclauses,
882  List *outersortkeys,
883  List *innersortkeys,
884  JoinType jointype,
885  JoinPathExtraData *extra,
886  bool is_partial)
887 {
888  Relids required_outer;
889  JoinCostWorkspace workspace;
890 
891  if (is_partial)
892  {
893  try_partial_mergejoin_path(root,
894  joinrel,
895  outer_path,
896  inner_path,
897  pathkeys,
898  mergeclauses,
899  outersortkeys,
900  innersortkeys,
901  jointype,
902  extra);
903  return;
904  }
905 
906  /*
907  * Check to see if proposed path is still parameterized, and reject if the
908  * parameterization wouldn't be sensible.
909  */
910  required_outer = calc_non_nestloop_required_outer(outer_path,
911  inner_path);
912  if (required_outer &&
913  !bms_overlap(required_outer, extra->param_source_rels))
914  {
915  /* Waste no memory when we reject a path here */
916  bms_free(required_outer);
917  return;
918  }
919 
920  /*
921  * If the given paths are already well enough ordered, we can skip doing
922  * an explicit sort.
923  */
924  if (outersortkeys &&
925  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
926  outersortkeys = NIL;
927  if (innersortkeys &&
928  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
929  innersortkeys = NIL;
930 
931  /*
932  * See comments in try_nestloop_path().
933  */
934  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
935  outer_path, inner_path,
936  outersortkeys, innersortkeys,
937  extra);
938 
939  if (add_path_precheck(joinrel,
940  workspace.startup_cost, workspace.total_cost,
941  pathkeys, required_outer))
942  {
943  add_path(joinrel, (Path *)
944  create_mergejoin_path(root,
945  joinrel,
946  jointype,
947  &workspace,
948  extra,
949  outer_path,
950  inner_path,
951  extra->restrictlist,
952  pathkeys,
953  required_outer,
954  mergeclauses,
955  outersortkeys,
956  innersortkeys));
957  }
958  else
959  {
960  /* Waste no memory when we reject a path here */
961  bms_free(required_outer);
962  }
963 }
964 
965 /*
966  * try_partial_mergejoin_path
967  * Consider a partial merge join path; if it appears useful, push it into
968  * the joinrel's pathlist via add_partial_path().
969  */
970 static void
971 try_partial_mergejoin_path(PlannerInfo *root,
972  RelOptInfo *joinrel,
973  Path *outer_path,
974  Path *inner_path,
975  List *pathkeys,
976  List *mergeclauses,
977  List *outersortkeys,
978  List *innersortkeys,
979  JoinType jointype,
980  JoinPathExtraData *extra)
981 {
982  JoinCostWorkspace workspace;
983 
984  /*
985  * See comments in try_partial_hashjoin_path().
986  */
987  Assert(bms_is_empty(joinrel->lateral_relids));
988  if (inner_path->param_info != NULL)
989  {
990  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
991 
992  if (!bms_is_empty(inner_paramrels))
993  return;
994  }
995 
996  /*
997  * If the given paths are already well enough ordered, we can skip doing
998  * an explicit sort.
999  */
1000  if (outersortkeys &&
1001  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1002  outersortkeys = NIL;
1003  if (innersortkeys &&
1004  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1005  innersortkeys = NIL;
1006 
1007  /*
1008  * See comments in try_partial_nestloop_path().
1009  */
1010  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1011  outer_path, inner_path,
1012  outersortkeys, innersortkeys,
1013  extra);
1014 
1015  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
1016  return;
1017 
1018  /* Might be good enough to be worth trying, so let's try it. */
1019  add_partial_path(joinrel, (Path *)
1020  create_mergejoin_path(root,
1021  joinrel,
1022  jointype,
1023  &workspace,
1024  extra,
1025  outer_path,
1026  inner_path,
1027  extra->restrictlist,
1028  pathkeys,
1029  NULL,
1030  mergeclauses,
1031  outersortkeys,
1032  innersortkeys));
1033 }
1034 
1035 /*
1036  * try_hashjoin_path
1037  * Consider a hash join path; if it appears useful, push it into
1038  * the joinrel's pathlist via add_path().
1039  */
1040 static void
1041 try_hashjoin_path(PlannerInfo *root,
1042  RelOptInfo *joinrel,
1043  Path *outer_path,
1044  Path *inner_path,
1045  List *hashclauses,
1046  JoinType jointype,
1047  JoinPathExtraData *extra)
1048 {
1049  Relids required_outer;
1050  JoinCostWorkspace workspace;
1051 
1052  /*
1053  * Check to see if proposed path is still parameterized, and reject if the
1054  * parameterization wouldn't be sensible.
1055  */
1056  required_outer = calc_non_nestloop_required_outer(outer_path,
1057  inner_path);
1058  if (required_outer &&
1059  !bms_overlap(required_outer, extra->param_source_rels))
1060  {
1061  /* Waste no memory when we reject a path here */
1062  bms_free(required_outer);
1063  return;
1064  }
1065 
1066  /*
1067  * See comments in try_nestloop_path(). Also note that hashjoin paths
1068  * never have any output pathkeys, per comments in create_hashjoin_path.
1069  */
1070  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1071  outer_path, inner_path, extra, false);
1072 
1073  if (add_path_precheck(joinrel,
1074  workspace.startup_cost, workspace.total_cost,
1075  NIL, required_outer))
1076  {
1077  add_path(joinrel, (Path *)
1078  create_hashjoin_path(root,
1079  joinrel,
1080  jointype,
1081  &workspace,
1082  extra,
1083  outer_path,
1084  inner_path,
1085  false, /* parallel_hash */
1086  extra->restrictlist,
1087  required_outer,
1088  hashclauses));
1089  }
1090  else
1091  {
1092  /* Waste no memory when we reject a path here */
1093  bms_free(required_outer);
1094  }
1095 }
1096 
1097 /*
1098  * try_partial_hashjoin_path
1099  * Consider a partial hashjoin join path; if it appears useful, push it into
1100  * the joinrel's partial_pathlist via add_partial_path().
1101  * The outer side is partial. If parallel_hash is true, then the inner path
1102  * must be partial and will be run in parallel to create one or more shared
1103  * hash tables; otherwise the inner path must be complete and a copy of it
1104  * is run in every process to create separate identical private hash tables.
1105  */
1106 static void
1107 try_partial_hashjoin_path(PlannerInfo *root,
1108  RelOptInfo *joinrel,
1109  Path *outer_path,
1110  Path *inner_path,
1111  List *hashclauses,
1112  JoinType jointype,
1113  JoinPathExtraData *extra,
1114  bool parallel_hash)
1115 {
1116  JoinCostWorkspace workspace;
1117 
1118  /*
1119  * If the inner path is parameterized, the parameterization must be fully
1120  * satisfied by the proposed outer path. Parameterized partial paths are
1121  * not supported. The caller should already have verified that no lateral
1122  * rels are required here.
1123  */
1124  Assert(bms_is_empty(joinrel->lateral_relids));
1125  if (inner_path->param_info != NULL)
1126  {
1127  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1128 
1129  if (!bms_is_empty(inner_paramrels))
1130  return;
1131  }
1132 
1133  /*
1134  * Before creating a path, get a quick lower bound on what it is likely to
1135  * cost. Bail out right away if it looks terrible.
1136  */
1137  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1138  outer_path, inner_path, extra, parallel_hash);
1139  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
1140  return;
1141 
1142  /* Might be good enough to be worth trying, so let's try it. */
1143  add_partial_path(joinrel, (Path *)
1144  create_hashjoin_path(root,
1145  joinrel,
1146  jointype,
1147  &workspace,
1148  extra,
1149  outer_path,
1150  inner_path,
1151  parallel_hash,
1152  extra->restrictlist,
1153  NULL,
1154  hashclauses));
1155 }
1156 
1157 /*
1158  * clause_sides_match_join
1159  * Determine whether a join clause is of the right form to use in this join.
1160  *
1161  * We already know that the clause is a binary opclause referencing only the
1162  * rels in the current join. The point here is to check whether it has the
1163  * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
1164  * rather than mixing outer and inner vars on either side. If it matches,
1165  * we set the transient flag outer_is_left to identify which side is which.
1166  */
1167 static inline bool
1168 clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel,
1169  RelOptInfo *innerrel)
1170 {
1171  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
1172  bms_is_subset(rinfo->right_relids, innerrel->relids))
1173  {
1174  /* lefthand side is outer */
1175  rinfo->outer_is_left = true;
1176  return true;
1177  }
1178  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
1179  bms_is_subset(rinfo->right_relids, outerrel->relids))
1180  {
1181  /* righthand side is outer */
1182  rinfo->outer_is_left = false;
1183  return true;
1184  }
1185  return false; /* no good for these input relations */
1186 }
1187 
1188 /*
1189  * sort_inner_and_outer
1190  * Create mergejoin join paths by explicitly sorting both the outer and
1191  * inner join relations on each available merge ordering.
1192  *
1193  * 'joinrel' is the join relation
1194  * 'outerrel' is the outer join relation
1195  * 'innerrel' is the inner join relation
1196  * 'jointype' is the type of join to do
1197  * 'extra' contains additional input values
1198  */
1199 static void
1200 sort_inner_and_outer(PlannerInfo *root,
1201  RelOptInfo *joinrel,
1202  RelOptInfo *outerrel,
1203  RelOptInfo *innerrel,
1204  JoinType jointype,
1205  JoinPathExtraData *extra)
1206 {
1207  JoinType save_jointype = jointype;
1208  Path *outer_path;
1209  Path *inner_path;
1210  Path *cheapest_partial_outer = NULL;
1211  Path *cheapest_safe_inner = NULL;
1212  List *all_pathkeys;
1213  ListCell *l;
1214 
1215  /*
1216  * We only consider the cheapest-total-cost input paths, since we are
1217  * assuming here that a sort is required. We will consider
1218  * cheapest-startup-cost input paths later, and only if they don't need a
1219  * sort.
1220  *
1221  * This function intentionally does not consider parameterized input
1222  * paths, except when the cheapest-total is parameterized. If we did so,
1223  * we'd have a combinatorial explosion of mergejoin paths of dubious
1224  * value. This interacts with decisions elsewhere that also discriminate
1225  * against mergejoins with parameterized inputs; see comments in
1226  * src/backend/optimizer/README.
1227  */
1228  outer_path = outerrel->cheapest_total_path;
1229  inner_path = innerrel->cheapest_total_path;
1230 
1231  /*
1232  * If either cheapest-total path is parameterized by the other rel, we
1233  * can't use a mergejoin. (There's no use looking for alternative input
1234  * paths, since these should already be the least-parameterized available
1235  * paths.)
1236  */
1237  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1238  PATH_PARAM_BY_REL(inner_path, outerrel))
1239  return;
1240 
1241  /*
1242  * If unique-ification is requested, do it and then handle as a plain
1243  * inner join.
1244  */
1245  if (jointype == JOIN_UNIQUE_OUTER)
1246  {
1247  outer_path = (Path *) create_unique_path(root, outerrel,
1248  outer_path, extra->sjinfo);
1249  Assert(outer_path);
1250  jointype = JOIN_INNER;
1251  }
1252  else if (jointype == JOIN_UNIQUE_INNER)
1253  {
1254  inner_path = (Path *) create_unique_path(root, innerrel,
1255  inner_path, extra->sjinfo);
1256  Assert(inner_path);
1257  jointype = JOIN_INNER;
1258  }
1259 
1260  /*
1261  * If the joinrel is parallel-safe, we may be able to consider a partial
1262  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1263  * outer path will be partial, and therefore we won't be able to properly
1264  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
1265  * JOIN_RIGHT, because they can produce false null extended rows. Also,
1266  * the resulting path must not be parameterized.
1267  */
1268  if (joinrel->consider_parallel &&
1269  save_jointype != JOIN_UNIQUE_OUTER &&
1270  save_jointype != JOIN_FULL &&
1271  save_jointype != JOIN_RIGHT &&
1272  outerrel->partial_pathlist != NIL &&
1273  bms_is_empty(joinrel->lateral_relids))
1274  {
1275  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1276 
1277  if (inner_path->parallel_safe)
1278  cheapest_safe_inner = inner_path;
1279  else if (save_jointype != JOIN_UNIQUE_INNER)
1280  cheapest_safe_inner =
1281  get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1282  }
1283 
1284  /*
1285  * Each possible ordering of the available mergejoin clauses will generate
1286  * a differently-sorted result path at essentially the same cost. We have
1287  * no basis for choosing one over another at this level of joining, but
1288  * some sort orders may be more useful than others for higher-level
1289  * mergejoins, so it's worth considering multiple orderings.
1290  *
1291  * Actually, it's not quite true that every mergeclause ordering will
1292  * generate a different path order, because some of the clauses may be
1293  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1294  * what we do is convert the mergeclause list to a list of canonical
1295  * pathkeys, and then consider different orderings of the pathkeys.
1296  *
1297  * Generating a path for *every* permutation of the pathkeys doesn't seem
1298  * like a winning strategy; the cost in planning time is too high. For
1299  * now, we generate one path for each pathkey, listing that pathkey first
1300  * and the rest in random order. This should allow at least a one-clause
1301  * mergejoin without re-sorting against any other possible mergejoin
1302  * partner path. But if we've not guessed the right ordering of secondary
1303  * keys, we may end up evaluating clauses as qpquals when they could have
1304  * been done as mergeclauses. (In practice, it's rare that there's more
1305  * than two or three mergeclauses, so expending a huge amount of thought
1306  * on that is probably not worth it.)
1307  *
1308  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1309  * some heuristics behind it (see that function), so be sure to try it
1310  * exactly as-is as well as making variants.
1311  */
1312  all_pathkeys = select_outer_pathkeys_for_merge(root,
1313  extra->mergeclause_list,
1314  joinrel);
1315 
1316  foreach(l, all_pathkeys)
1317  {
1318  PathKey *front_pathkey = (PathKey *) lfirst(l);
1319  List *cur_mergeclauses;
1320  List *outerkeys;
1321  List *innerkeys;
1322  List *merge_pathkeys;
1323 
1324  /* Make a pathkey list with this guy first */
1325  if (l != list_head(all_pathkeys))
1326  outerkeys = lcons(front_pathkey,
1327  list_delete_nth_cell(list_copy(all_pathkeys),
1328  foreach_current_index(l)));
1329  else
1330  outerkeys = all_pathkeys; /* no work at first one... */
1331 
1332  /* Sort the mergeclauses into the corresponding ordering */
1333  cur_mergeclauses =
1334  find_mergeclauses_for_outer_pathkeys(root,
1335  outerkeys,
1336  extra->mergeclause_list);
1337 
1338  /* Should have used them all... */
1339  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1340 
1341  /* Build sort pathkeys for the inner side */
1342  innerkeys = make_inner_pathkeys_for_merge(root,
1343  cur_mergeclauses,
1344  outerkeys);
1345 
1346  /* Build pathkeys representing output sort order */
1347  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1348  outerkeys);
1349 
1350  /*
1351  * And now we can make the path.
1352  *
1353  * Note: it's possible that the cheapest paths will already be sorted
1354  * properly. try_mergejoin_path will detect that case and suppress an
1355  * explicit sort step, so we needn't do so here.
1356  */
1357  try_mergejoin_path(root,
1358  joinrel,
1359  outer_path,
1360  inner_path,
1361  merge_pathkeys,
1362  cur_mergeclauses,
1363  outerkeys,
1364  innerkeys,
1365  jointype,
1366  extra,
1367  false);
1368 
1369  /*
1370  * If we have partial outer and parallel safe inner path then try
1371  * partial mergejoin path.
1372  */
1373  if (cheapest_partial_outer && cheapest_safe_inner)
1374  try_partial_mergejoin_path(root,
1375  joinrel,
1376  cheapest_partial_outer,
1377  cheapest_safe_inner,
1378  merge_pathkeys,
1379  cur_mergeclauses,
1380  outerkeys,
1381  innerkeys,
1382  jointype,
1383  extra);
1384  }
1385 }
1386 
1387 /*
1388  * generate_mergejoin_paths
1389  * Creates possible mergejoin paths for input outerpath.
1390  *
1391  * We generate mergejoins if mergejoin clauses are available. We have
1392  * two ways to generate the inner path for a mergejoin: sort the cheapest
1393  * inner path, or use an inner path that is already suitably ordered for the
1394  * merge. If we have several mergeclauses, it could be that there is no inner
1395  * path (or only a very expensive one) for the full list of mergeclauses, but
1396  * better paths exist if we truncate the mergeclause list (thereby discarding
1397  * some sort key requirements). So, we consider truncations of the
1398  * mergeclause list as well as the full list. (Ideally we'd consider all
1399  * subsets of the mergeclause list, but that seems way too expensive.)
1400  */
1401 static void
1402 generate_mergejoin_paths(PlannerInfo *root,
1403  RelOptInfo *joinrel,
1404  RelOptInfo *innerrel,
1405  Path *outerpath,
1406  JoinType jointype,
1407  JoinPathExtraData *extra,
1408  bool useallclauses,
1409  Path *inner_cheapest_total,
1410  List *merge_pathkeys,
1411  bool is_partial)
1412 {
1413  List *mergeclauses;
1414  List *innersortkeys;
1415  List *trialsortkeys;
1416  Path *cheapest_startup_inner;
1417  Path *cheapest_total_inner;
1418  JoinType save_jointype = jointype;
1419  int num_sortkeys;
1420  int sortkeycnt;
1421 
1422  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1423  jointype = JOIN_INNER;
1424 
1425  /* Look for useful mergeclauses (if any) */
1426  mergeclauses =
1427  find_mergeclauses_for_outer_pathkeys(root,
1428  outerpath->pathkeys,
1429  extra->mergeclause_list);
1430 
1431  /*
1432  * Done with this outer path if no chance for a mergejoin.
1433  *
1434  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1435  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1436  * but since mergejoin is our only join type that supports FULL JOIN
1437  * without any join clauses, it's necessary to generate a clauseless
1438  * mergejoin path instead.
1439  */
1440  if (mergeclauses == NIL)
1441  {
1442  if (jointype == JOIN_FULL)
1443  /* okay to try for mergejoin */ ;
1444  else
1445  return;
1446  }
1447  if (useallclauses &&
1448  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1449  return;
1450 
1451  /* Compute the required ordering of the inner path */
1452  innersortkeys = make_inner_pathkeys_for_merge(root,
1453  mergeclauses,
1454  outerpath->pathkeys);
1455 
1456  /*
1457  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1458  * a sort will be needed, only cheapest total cost matters. (But
1459  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1460  * already correctly sorted.)
1461  */
1462  try_mergejoin_path(root,
1463  joinrel,
1464  outerpath,
1465  inner_cheapest_total,
1466  merge_pathkeys,
1467  mergeclauses,
1468  NIL,
1469  innersortkeys,
1470  jointype,
1471  extra,
1472  is_partial);
1473 
1474  /* Can't do anything else if inner path needs to be unique'd */
1475  if (save_jointype == JOIN_UNIQUE_INNER)
1476  return;
1477 
1478  /*
1479  * Look for presorted inner paths that satisfy the innersortkey list ---
1480  * or any truncation thereof, if we are allowed to build a mergejoin using
1481  * a subset of the merge clauses. Here, we consider both cheap startup
1482  * cost and cheap total cost.
1483  *
1484  * Currently we do not consider parameterized inner paths here. This
1485  * interacts with decisions elsewhere that also discriminate against
1486  * mergejoins with parameterized inputs; see comments in
1487  * src/backend/optimizer/README.
1488  *
1489  * As we shorten the sortkey list, we should consider only paths that are
1490  * strictly cheaper than (in particular, not the same as) any path found
1491  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1492  * merge keys than a given path allows (treating the rest as plain
1493  * joinquals), which is unlikely to be a good idea. Also, eliminating
1494  * paths here on the basis of compare_path_costs is a lot cheaper than
1495  * building the mergejoin path only to throw it away.
1496  *
1497  * If inner_cheapest_total is well enough sorted to have not required a
1498  * sort in the path made above, we shouldn't make a duplicate path with
1499  * it, either. We handle that case with the same logic that handles the
1500  * previous consideration, by initializing the variables that track
1501  * cheapest-so-far properly. Note that we do NOT reject
1502  * inner_cheapest_total if we find it matches some shorter set of
1503  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1504  * sorting inner_cheapest_total, whereas we did sort it above, so the
1505  * plans being considered are different.
1506  */
1507  if (pathkeys_contained_in(innersortkeys,
1508  inner_cheapest_total->pathkeys))
1509  {
1510  /* inner_cheapest_total didn't require a sort */
1511  cheapest_startup_inner = inner_cheapest_total;
1512  cheapest_total_inner = inner_cheapest_total;
1513  }
1514  else
1515  {
1516  /* it did require a sort, at least for the full set of keys */
1517  cheapest_startup_inner = NULL;
1518  cheapest_total_inner = NULL;
1519  }
1520  num_sortkeys = list_length(innersortkeys);
1521  if (num_sortkeys > 1 && !useallclauses)
1522  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1523  else
1524  trialsortkeys = innersortkeys; /* won't really truncate */
1525 
1526  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1527  {
1528  Path *innerpath;
1529  List *newclauses = NIL;
1530 
1531  /*
1532  * Look for an inner path ordered well enough for the first
1533  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1534  * destructively, which is why we made a copy...
1535  */
1536  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1537  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1538  trialsortkeys,
1539  NULL,
1540  TOTAL_COST,
1541  is_partial);
1542  if (innerpath != NULL &&
1543  (cheapest_total_inner == NULL ||
1544  compare_path_costs(innerpath, cheapest_total_inner,
1545  TOTAL_COST) < 0))
1546  {
1547  /* Found a cheap (or even-cheaper) sorted path */
1548  /* Select the right mergeclauses, if we didn't already */
1549  if (sortkeycnt < num_sortkeys)
1550  {
1551  newclauses =
1552  trim_mergeclauses_for_inner_pathkeys(root,
1553  mergeclauses,
1554  trialsortkeys);
1555  Assert(newclauses != NIL);
1556  }
1557  else
1558  newclauses = mergeclauses;
1559  try_mergejoin_path(root,
1560  joinrel,
1561  outerpath,
1562  innerpath,
1563  merge_pathkeys,
1564  newclauses,
1565  NIL,
1566  NIL,
1567  jointype,
1568  extra,
1569  is_partial);
1570  cheapest_total_inner = innerpath;
1571  }
1572  /* Same on the basis of cheapest startup cost ... */
1573  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1574  trialsortkeys,
1575  NULL,
1576  STARTUP_COST,
1577  is_partial);
1578  if (innerpath != NULL &&
1579  (cheapest_startup_inner == NULL ||
1580  compare_path_costs(innerpath, cheapest_startup_inner,
1581  STARTUP_COST) < 0))
1582  {
1583  /* Found a cheap (or even-cheaper) sorted path */
1584  if (innerpath != cheapest_total_inner)
1585  {
1586  /*
1587  * Avoid rebuilding clause list if we already made one; saves
1588  * memory in big join trees...
1589  */
1590  if (newclauses == NIL)
1591  {
1592  if (sortkeycnt < num_sortkeys)
1593  {
1594  newclauses =
1595  trim_mergeclauses_for_inner_pathkeys(root,
1596  mergeclauses,
1597  trialsortkeys);
1598  Assert(newclauses != NIL);
1599  }
1600  else
1601  newclauses = mergeclauses;
1602  }
1603  try_mergejoin_path(root,
1604  joinrel,
1605  outerpath,
1606  innerpath,
1607  merge_pathkeys,
1608  newclauses,
1609  NIL,
1610  NIL,
1611  jointype,
1612  extra,
1613  is_partial);
1614  }
1615  cheapest_startup_inner = innerpath;
1616  }
1617 
1618  /*
1619  * Don't consider truncated sortkeys if we need all clauses.
1620  */
1621  if (useallclauses)
1622  break;
1623  }
1624 }
1625 
1626 /*
1627  * match_unsorted_outer
1628  * Creates possible join paths for processing a single join relation
1629  * 'joinrel' by employing either iterative substitution or
1630  * mergejoining on each of its possible outer paths (considering
1631  * only outer paths that are already ordered well enough for merging).
1632  *
1633  * We always generate a nestloop path for each available outer path.
1634  * In fact we may generate as many as five: one on the cheapest-total-cost
1635  * inner path, one on the same with materialization, one on the
1636  * cheapest-startup-cost inner path (if different), one on the
1637  * cheapest-total inner-indexscan path (if any), and one on the
1638  * cheapest-startup inner-indexscan path (if different).
1639  *
1640  * We also consider mergejoins if mergejoin clauses are available. See
1641  * detailed comments in generate_mergejoin_paths.
1642  *
1643  * 'joinrel' is the join relation
1644  * 'outerrel' is the outer join relation
1645  * 'innerrel' is the inner join relation
1646  * 'jointype' is the type of join to do
1647  * 'extra' contains additional input values
1648  */
1649 static void
1650 match_unsorted_outer(PlannerInfo *root,
1651  RelOptInfo *joinrel,
1652  RelOptInfo *outerrel,
1653  RelOptInfo *innerrel,
1654  JoinType jointype,
1655  JoinPathExtraData *extra)
1656 {
1657  JoinType save_jointype = jointype;
1658  bool nestjoinOK;
1659  bool useallclauses;
1660  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1661  Path *matpath = NULL;
1662  ListCell *lc1;
1663 
1664  /*
1665  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1666  * are doing a right or full mergejoin, we must use *all* the mergeclauses
1667  * as join clauses, else we will not have a valid plan. (Although these
1668  * two flags are currently inverses, keep them separate for clarity and
1669  * possible future changes.)
1670  */
1671  switch (jointype)
1672  {
1673  case JOIN_INNER:
1674  case JOIN_LEFT:
1675  case JOIN_SEMI:
1676  case JOIN_ANTI:
1677  nestjoinOK = true;
1678  useallclauses = false;
1679  break;
1680  case JOIN_RIGHT:
1681  case JOIN_FULL:
1682  nestjoinOK = false;
1683  useallclauses = true;
1684  break;
1685  case JOIN_UNIQUE_OUTER:
1686  case JOIN_UNIQUE_INNER:
1687  jointype = JOIN_INNER;
1688  nestjoinOK = true;
1689  useallclauses = false;
1690  break;
1691  default:
1692  elog(ERROR, "unrecognized join type: %d",
1693  (int) jointype);
1694  nestjoinOK = false; /* keep compiler quiet */
1695  useallclauses = false;
1696  break;
1697  }
1698 
1699  /*
1700  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1701  * we will consider it below as a member of cheapest_parameterized_paths,
1702  * but the other possibilities considered in this routine aren't usable.
1703  */
1704  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1705  inner_cheapest_total = NULL;
1706 
1707  /*
1708  * If we need to unique-ify the inner path, we will consider only the
1709  * cheapest-total inner.
1710  */
1711  if (save_jointype == JOIN_UNIQUE_INNER)
1712  {
1713  /* No way to do this with an inner path parameterized by outer rel */
1714  if (inner_cheapest_total == NULL)
1715  return;
1716  inner_cheapest_total = (Path *)
1717  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1718  Assert(inner_cheapest_total);
1719  }
1720  else if (nestjoinOK)
1721  {
1722  /*
1723  * Consider materializing the cheapest inner path, unless
1724  * enable_material is off or the path in question materializes its
1725  * output anyway.
1726  */
1727  if (enable_material && inner_cheapest_total != NULL &&
1728  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1729  matpath = (Path *)
1730  create_material_path(innerrel, inner_cheapest_total);
1731  }
1732 
1733  foreach(lc1, outerrel->pathlist)
1734  {
1735  Path *outerpath = (Path *) lfirst(lc1);
1736  List *merge_pathkeys;
1737 
1738  /*
1739  * We cannot use an outer path that is parameterized by the inner rel.
1740  */
1741  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1742  continue;
1743 
1744  /*
1745  * If we need to unique-ify the outer path, it's pointless to consider
1746  * any but the cheapest outer. (XXX we don't consider parameterized
1747  * outers, nor inners, for unique-ified cases. Should we?)
1748  */
1749  if (save_jointype == JOIN_UNIQUE_OUTER)
1750  {
1751  if (outerpath != outerrel->cheapest_total_path)
1752  continue;
1753  outerpath = (Path *) create_unique_path(root, outerrel,
1754  outerpath, extra->sjinfo);
1755  Assert(outerpath);
1756  }
1757 
1758  /*
1759  * The result will have this sort order (even if it is implemented as
1760  * a nestloop, and even if some of the mergeclauses are implemented by
1761  * qpquals rather than as true mergeclauses):
1762  */
1763  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1764  outerpath->pathkeys);
1765 
1766  if (save_jointype == JOIN_UNIQUE_INNER)
1767  {
1768  /*
1769  * Consider nestloop join, but only with the unique-ified cheapest
1770  * inner path
1771  */
1772  try_nestloop_path(root,
1773  joinrel,
1774  outerpath,
1775  inner_cheapest_total,
1776  merge_pathkeys,
1777  jointype,
1778  extra);
1779  }
1780  else if (nestjoinOK)
1781  {
1782  /*
1783  * Consider nestloop joins using this outer path and various
1784  * available paths for the inner relation. We consider the
1785  * cheapest-total paths for each available parameterization of the
1786  * inner relation, including the unparameterized case.
1787  */
1788  ListCell *lc2;
1789 
1790  foreach(lc2, innerrel->cheapest_parameterized_paths)
1791  {
1792  Path *innerpath = (Path *) lfirst(lc2);
1793  Path *mpath;
1794 
1795  try_nestloop_path(root,
1796  joinrel,
1797  outerpath,
1798  innerpath,
1799  merge_pathkeys,
1800  jointype,
1801  extra);
1802 
1803  /*
1804  * Try generating a memoize path and see if that makes the
1805  * nested loop any cheaper.
1806  */
1807  mpath = get_memoize_path(root, innerrel, outerrel,
1808  innerpath, outerpath, jointype,
1809  extra);
1810  if (mpath != NULL)
1811  try_nestloop_path(root,
1812  joinrel,
1813  outerpath,
1814  mpath,
1815  merge_pathkeys,
1816  jointype,
1817  extra);
1818  }
1819 
1820  /* Also consider materialized form of the cheapest inner path */
1821  if (matpath != NULL)
1822  try_nestloop_path(root,
1823  joinrel,
1824  outerpath,
1825  matpath,
1826  merge_pathkeys,
1827  jointype,
1828  extra);
1829  }
1830 
1831  /* Can't do anything else if outer path needs to be unique'd */
1832  if (save_jointype == JOIN_UNIQUE_OUTER)
1833  continue;
1834 
1835  /* Can't do anything else if inner rel is parameterized by outer */
1836  if (inner_cheapest_total == NULL)
1837  continue;
1838 
1839  /* Generate merge join paths */
1840  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1841  save_jointype, extra, useallclauses,
1842  inner_cheapest_total, merge_pathkeys,
1843  false);
1844  }
1845 
1846  /*
1847  * Consider partial nestloop and mergejoin plan if outerrel has any
1848  * partial path and the joinrel is parallel-safe. However, we can't
1849  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1850  * therefore we won't be able to properly guarantee uniqueness. Nor can
1851  * we handle joins needing lateral rels, since partial paths must not be
1852  * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1853  * because they can produce false null extended rows.
1854  */
1855  if (joinrel->consider_parallel &&
1856  save_jointype != JOIN_UNIQUE_OUTER &&
1857  save_jointype != JOIN_FULL &&
1858  save_jointype != JOIN_RIGHT &&
1859  outerrel->partial_pathlist != NIL &&
1860  bms_is_empty(joinrel->lateral_relids))
1861  {
1862  if (nestjoinOK)
1863  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1864  save_jointype, extra);
1865 
1866  /*
1867  * If inner_cheapest_total is NULL or non parallel-safe then find the
1868  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1869  * can't use any alternative inner path.
1870  */
1871  if (inner_cheapest_total == NULL ||
1872  !inner_cheapest_total->parallel_safe)
1873  {
1874  if (save_jointype == JOIN_UNIQUE_INNER)
1875  return;
1876 
1877  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1878  }
1879 
1880  if (inner_cheapest_total)
1881  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1882  save_jointype, extra,
1883  inner_cheapest_total);
1884  }
1885 }
1886 
1887 /*
1888  * consider_parallel_mergejoin
1889  * Try to build partial paths for a joinrel by joining a partial path
1890  * for the outer relation to a complete path for the inner relation.
1891  *
1892  * 'joinrel' is the join relation
1893  * 'outerrel' is the outer join relation
1894  * 'innerrel' is the inner join relation
1895  * 'jointype' is the type of join to do
1896  * 'extra' contains additional input values
1897  * 'inner_cheapest_total' cheapest total path for innerrel
1898  */
1899 static void
1900 consider_parallel_mergejoin(PlannerInfo *root,
1901  RelOptInfo *joinrel,
1902  RelOptInfo *outerrel,
1903  RelOptInfo *innerrel,
1904  JoinType jointype,
1905  JoinPathExtraData *extra,
1906  Path *inner_cheapest_total)
1907 {
1908  ListCell *lc1;
1909 
1910  /* generate merge join path for each partial outer path */
1911  foreach(lc1, outerrel->partial_pathlist)
1912  {
1913  Path *outerpath = (Path *) lfirst(lc1);
1914  List *merge_pathkeys;
1915 
1916  /*
1917  * Figure out what useful ordering any paths we create will have.
1918  */
1919  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1920  outerpath->pathkeys);
1921 
1922  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1923  extra, false, inner_cheapest_total,
1924  merge_pathkeys, true);
1925  }
1926 }
1927 
1928 /*
1929  * consider_parallel_nestloop
1930  * Try to build partial paths for a joinrel by joining a partial path for the
1931  * outer relation to a complete path for the inner relation.
1932  *
1933  * 'joinrel' is the join relation
1934  * 'outerrel' is the outer join relation
1935  * 'innerrel' is the inner join relation
1936  * 'jointype' is the type of join to do
1937  * 'extra' contains additional input values
1938  */
1939 static void
1940 consider_parallel_nestloop(PlannerInfo *root,
1941  RelOptInfo *joinrel,
1942  RelOptInfo *outerrel,
1943  RelOptInfo *innerrel,
1944  JoinType jointype,
1945  JoinPathExtraData *extra)
1946 {
1947  JoinType save_jointype = jointype;
1948  ListCell *lc1;
1949 
1950  if (jointype == JOIN_UNIQUE_INNER)
1951  jointype = JOIN_INNER;
1952 
1953  foreach(lc1, outerrel->partial_pathlist)
1954  {
1955  Path *outerpath = (Path *) lfirst(lc1);
1956  List *pathkeys;
1957  ListCell *lc2;
1958 
1959  /* Figure out what useful ordering any paths we create will have. */
1960  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1961  outerpath->pathkeys);
1962 
1963  /*
1964  * Try the cheapest parameterized paths; only those which will produce
1965  * an unparameterized path when joined to this outerrel will survive
1966  * try_partial_nestloop_path. The cheapest unparameterized path is
1967  * also in this list.
1968  */
1969  foreach(lc2, innerrel->cheapest_parameterized_paths)
1970  {
1971  Path *innerpath = (Path *) lfirst(lc2);
1972  Path *mpath;
1973 
1974  /* Can't join to an inner path that is not parallel-safe */
1975  if (!innerpath->parallel_safe)
1976  continue;
1977 
1978  /*
1979  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1980  * cheapest_total_path, and we have to unique-ify it. (We might
1981  * be able to relax this to allow other safe, unparameterized
1982  * inner paths, but right now create_unique_path is not on board
1983  * with that.)
1984  */
1985  if (save_jointype == JOIN_UNIQUE_INNER)
1986  {
1987  if (innerpath != innerrel->cheapest_total_path)
1988  continue;
1989  innerpath = (Path *) create_unique_path(root, innerrel,
1990  innerpath,
1991  extra->sjinfo);
1992  Assert(innerpath);
1993  }
1994 
1995  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1996  pathkeys, jointype, extra);
1997 
1998  /*
1999  * Try generating a memoize path and see if that makes the nested
2000  * loop any cheaper.
2001  */
2002  mpath = get_memoize_path(root, innerrel, outerrel,
2003  innerpath, outerpath, jointype,
2004  extra);
2005  if (mpath != NULL)
2006  try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2007  pathkeys, jointype, extra);
2008  }
2009  }
2010 }
2011 
2012 /*
2013  * hash_inner_and_outer
2014  * Create hashjoin join paths by explicitly hashing both the outer and
2015  * inner keys of each available hash clause.
2016  *
2017  * 'joinrel' is the join relation
2018  * 'outerrel' is the outer join relation
2019  * 'innerrel' is the inner join relation
2020  * 'jointype' is the type of join to do
2021  * 'extra' contains additional input values
2022  */
2023 static void
2024 hash_inner_and_outer(PlannerInfo *root,
2025  RelOptInfo *joinrel,
2026  RelOptInfo *outerrel,
2027  RelOptInfo *innerrel,
2028  JoinType jointype,
2029  JoinPathExtraData *extra)
2030 {
2031  JoinType save_jointype = jointype;
2032  bool isouterjoin = IS_OUTER_JOIN(jointype);
2033  List *hashclauses;
2034  ListCell *l;
2035 
2036  /*
2037  * We need to build only one hashclauses list for any given pair of outer
2038  * and inner relations; all of the hashable clauses will be used as keys.
2039  *
2040  * Scan the join's restrictinfo list to find hashjoinable clauses that are
2041  * usable with this pair of sub-relations.
2042  */
2043  hashclauses = NIL;
2044  foreach(l, extra->restrictlist)
2045  {
2046  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2047 
2048  /*
2049  * If processing an outer join, only use its own join clauses for
2050  * hashing. For inner joins we need not be so picky.
2051  */
2052  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2053  continue;
2054 
2055  if (!restrictinfo->can_join ||
2056  restrictinfo->hashjoinoperator == InvalidOid)
2057  continue; /* not hashjoinable */
2058 
2059  /*
2060  * Check if clause has the form "outer op inner" or "inner op outer".
2061  */
2062  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2063  continue; /* no good for these input relations */
2064 
2065  hashclauses = lappend(hashclauses, restrictinfo);
2066  }
2067 
2068  /* If we found any usable hashclauses, make paths */
2069  if (hashclauses)
2070  {
2071  /*
2072  * We consider both the cheapest-total-cost and cheapest-startup-cost
2073  * outer paths. There's no need to consider any but the
2074  * cheapest-total-cost inner path, however.
2075  */
2076  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2077  Path *cheapest_total_outer = outerrel->cheapest_total_path;
2078  Path *cheapest_total_inner = innerrel->cheapest_total_path;
2079 
2080  /*
2081  * If either cheapest-total path is parameterized by the other rel, we
2082  * can't use a hashjoin. (There's no use looking for alternative
2083  * input paths, since these should already be the least-parameterized
2084  * available paths.)
2085  */
2086  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2087  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2088  return;
2089 
2090  /* Unique-ify if need be; we ignore parameterized possibilities */
2091  if (jointype == JOIN_UNIQUE_OUTER)
2092  {
2093  cheapest_total_outer = (Path *)
2094  create_unique_path(root, outerrel,
2095  cheapest_total_outer, extra->sjinfo);
2096  Assert(cheapest_total_outer);
2097  jointype = JOIN_INNER;
2098  try_hashjoin_path(root,
2099  joinrel,
2100  cheapest_total_outer,
2101  cheapest_total_inner,
2102  hashclauses,
2103  jointype,
2104  extra);
2105  /* no possibility of cheap startup here */
2106  }
2107  else if (jointype == JOIN_UNIQUE_INNER)
2108  {
2109  cheapest_total_inner = (Path *)
2110  create_unique_path(root, innerrel,
2111  cheapest_total_inner, extra->sjinfo);
2112  Assert(cheapest_total_inner);
2113  jointype = JOIN_INNER;
2114  try_hashjoin_path(root,
2115  joinrel,
2116  cheapest_total_outer,
2117  cheapest_total_inner,
2118  hashclauses,
2119  jointype,
2120  extra);
2121  if (cheapest_startup_outer != NULL &&
2122  cheapest_startup_outer != cheapest_total_outer)
2123  try_hashjoin_path(root,
2124  joinrel,
2125  cheapest_startup_outer,
2126  cheapest_total_inner,
2127  hashclauses,
2128  jointype,
2129  extra);
2130  }
2131  else
2132  {
2133  /*
2134  * For other jointypes, we consider the cheapest startup outer
2135  * together with the cheapest total inner, and then consider
2136  * pairings of cheapest-total paths including parameterized ones.
2137  * There is no use in generating parameterized paths on the basis
2138  * of possibly cheap startup cost, so this is sufficient.
2139  */
2140  ListCell *lc1;
2141  ListCell *lc2;
2142 
2143  if (cheapest_startup_outer != NULL)
2144  try_hashjoin_path(root,
2145  joinrel,
2146  cheapest_startup_outer,
2147  cheapest_total_inner,
2148  hashclauses,
2149  jointype,
2150  extra);
2151 
2152  foreach(lc1, outerrel->cheapest_parameterized_paths)
2153  {
2154  Path *outerpath = (Path *) lfirst(lc1);
2155 
2156  /*
2157  * We cannot use an outer path that is parameterized by the
2158  * inner rel.
2159  */
2160  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2161  continue;
2162 
2163  foreach(lc2, innerrel->cheapest_parameterized_paths)
2164  {
2165  Path *innerpath = (Path *) lfirst(lc2);
2166 
2167  /*
2168  * We cannot use an inner path that is parameterized by
2169  * the outer rel, either.
2170  */
2171  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2172  continue;
2173 
2174  if (outerpath == cheapest_startup_outer &&
2175  innerpath == cheapest_total_inner)
2176  continue; /* already tried it */
2177 
2178  try_hashjoin_path(root,
2179  joinrel,
2180  outerpath,
2181  innerpath,
2182  hashclauses,
2183  jointype,
2184  extra);
2185  }
2186  }
2187  }
2188 
2189  /*
2190  * If the joinrel is parallel-safe, we may be able to consider a
2191  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2192  * because the outer path will be partial, and therefore we won't be
2193  * able to properly guarantee uniqueness. Similarly, we can't handle
2194  * JOIN_FULL and JOIN_RIGHT, because they can produce false null
2195  * extended rows. Also, the resulting path must not be parameterized.
2196  * We would be able to support JOIN_FULL and JOIN_RIGHT for Parallel
2197  * Hash, since in that case we're back to a single hash table with a
2198  * single set of match bits for each batch, but that will require
2199  * figuring out a deadlock-free way to wait for the probe to finish.
2200  */
2201  if (joinrel->consider_parallel &&
2202  save_jointype != JOIN_UNIQUE_OUTER &&
2203  save_jointype != JOIN_FULL &&
2204  save_jointype != JOIN_RIGHT &&
2205  outerrel->partial_pathlist != NIL &&
2206  bms_is_empty(joinrel->lateral_relids))
2207  {
2208  Path *cheapest_partial_outer;
2209  Path *cheapest_partial_inner = NULL;
2210  Path *cheapest_safe_inner = NULL;
2211 
2212  cheapest_partial_outer =
2213  (Path *) linitial(outerrel->partial_pathlist);
2214 
2215  /*
2216  * Can we use a partial inner plan too, so that we can build a
2217  * shared hash table in parallel? We can't handle
2218  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2219  */
2220  if (innerrel->partial_pathlist != NIL &&
2221  save_jointype != JOIN_UNIQUE_INNER &&
2222  enable_parallel_hash)
2223  {
2224  cheapest_partial_inner =
2225  (Path *) linitial(innerrel->partial_pathlist);
2226  try_partial_hashjoin_path(root, joinrel,
2227  cheapest_partial_outer,
2228  cheapest_partial_inner,
2229  hashclauses, jointype, extra,
2230  true /* parallel_hash */ );
2231  }
2232 
2233  /*
2234  * Normally, given that the joinrel is parallel-safe, the cheapest
2235  * total inner path will also be parallel-safe, but if not, we'll
2236  * have to search for the cheapest safe, unparameterized inner
2237  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2238  * inner path.
2239  */
2240  if (cheapest_total_inner->parallel_safe)
2241  cheapest_safe_inner = cheapest_total_inner;
2242  else if (save_jointype != JOIN_UNIQUE_INNER)
2243  cheapest_safe_inner =
2244  get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
2245 
2246  if (cheapest_safe_inner != NULL)
2247  try_partial_hashjoin_path(root, joinrel,
2248  cheapest_partial_outer,
2249  cheapest_safe_inner,
2250  hashclauses, jointype, extra,
2251  false /* parallel_hash */ );
2252  }
2253  }
2254 }
2255 
2256 /*
2257  * select_mergejoin_clauses
2258  * Select mergejoin clauses that are usable for a particular join.
2259  * Returns a list of RestrictInfo nodes for those clauses.
2260  *
2261  * *mergejoin_allowed is normally set to true, but it is set to false if
2262  * this is a right/full join and there are nonmergejoinable join clauses.
2263  * The executor's mergejoin machinery cannot handle such cases, so we have
2264  * to avoid generating a mergejoin plan. (Note that this flag does NOT
2265  * consider whether there are actually any mergejoinable clauses. This is
2266  * correct because in some cases we need to build a clauseless mergejoin.
2267  * Simply returning NIL is therefore not enough to distinguish safe from
2268  * unsafe cases.)
2269  *
2270  * We also mark each selected RestrictInfo to show which side is currently
2271  * being considered as outer. These are transient markings that are only
2272  * good for the duration of the current add_paths_to_joinrel() call!
2273  *
2274  * We examine each restrictinfo clause known for the join to see
2275  * if it is mergejoinable and involves vars from the two sub-relations
2276  * currently of interest.
2277  */
2278 static List *
2279 select_mergejoin_clauses(PlannerInfo *root,
2280  RelOptInfo *joinrel,
2281  RelOptInfo *outerrel,
2282  RelOptInfo *innerrel,
2283  List *restrictlist,
2284  JoinType jointype,
2285  bool *mergejoin_allowed)
2286 {
2287  List *result_list = NIL;
2288  bool isouterjoin = IS_OUTER_JOIN(jointype);
2289  bool have_nonmergeable_joinclause = false;
2290  ListCell *l;
2291 
2292  foreach(l, restrictlist)
2293  {
2294  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2295 
2296  /*
2297  * If processing an outer join, only use its own join clauses in the
2298  * merge. For inner joins we can use pushed-down clauses too. (Note:
2299  * we don't set have_nonmergeable_joinclause here because pushed-down
2300  * clauses will become otherquals not joinquals.)
2301  */
2302  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2303  continue;
2304 
2305  /* Check that clause is a mergeable operator clause */
2306  if (!restrictinfo->can_join ||
2307  restrictinfo->mergeopfamilies == NIL)
2308  {
2309  /*
2310  * The executor can handle extra joinquals that are constants, but
2311  * not anything else, when doing right/full merge join. (The
2312  * reason to support constants is so we can do FULL JOIN ON
2313  * FALSE.)
2314  */
2315  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2316  have_nonmergeable_joinclause = true;
2317  continue; /* not mergejoinable */
2318  }
2319 
2320  /*
2321  * Check if clause has the form "outer op inner" or "inner op outer".
2322  */
2323  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2324  {
2325  have_nonmergeable_joinclause = true;
2326  continue; /* no good for these input relations */
2327  }
2328 
2329  /*
2330  * Insist that each side have a non-redundant eclass. This
2331  * restriction is needed because various bits of the planner expect
2332  * that each clause in a merge be associable with some pathkey in a
2333  * canonical pathkey list, but redundant eclasses can't appear in
2334  * canonical sort orderings. (XXX it might be worth relaxing this,
2335  * but not enough time to address it for 8.3.)
2336  */
2337  update_mergeclause_eclasses(root, restrictinfo);
2338 
2339  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2340  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2341  {
2342  have_nonmergeable_joinclause = true;
2343  continue; /* can't handle redundant eclasses */
2344  }
2345 
2346  result_list = lappend(result_list, restrictinfo);
2347  }
2348 
2349  /*
2350  * Report whether mergejoin is allowed (see comment at top of function).
2351  */
2352  switch (jointype)
2353  {
2354  case JOIN_RIGHT:
2355  case JOIN_FULL:
2356  *mergejoin_allowed = !have_nonmergeable_joinclause;
2357  break;
2358  default:
2359  *mergejoin_allowed = true;
2360  break;
2361  }
2362 
2363  return result_list;
2364 }
innerrel_is_unique
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:1079
bms_join
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:987
bms_is_subset
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:332
bms_free
void bms_free(Bitmapset *a)
Definition: bitmapset.c:209
bms_is_member
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:444
bms_difference
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:298
bms_intersect
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:260
bms_add_members
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:818
bms_overlap
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:511
bms_nonempty_difference
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:564
bms_is_empty
#define bms_is_empty(a)
Definition: bitmapset.h:105
OidIsValid
#define OidIsValid(objectId)
Definition: c.h:759
contain_volatile_functions
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:477
initial_cost_mergejoin
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, JoinPathExtraData *extra)
Definition: costsize.c:3245
enable_memoize
bool enable_memoize
Definition: costsize.c:145
compute_semi_anti_join_factors
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:4732
enable_material
bool enable_material
Definition: costsize.c:144
initial_cost_hashjoin
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra, bool parallel_hash)
Definition: costsize.c:3803
enable_hashjoin
bool enable_hashjoin
Definition: costsize.c:147
enable_mergejoin
bool enable_mergejoin
Definition: costsize.c:146
initial_cost_nestloop
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2964
enable_parallel_hash
bool enable_parallel_hash
Definition: costsize.c:152
ERROR
#define ERROR
Definition: elog.h:39
ExecMaterializesOutput
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:637
if
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
try_hashjoin_path
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1041
get_memoize_path
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:556
clause_sides_match_join
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1168
select_mergejoin_clauses
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2279
sort_inner_and_outer
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1200
add_paths_to_joinrel
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinpath.c:123
paraminfo_get_equal_hashops
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List **param_exprs, List **operators, bool *binary_mode)
Definition: joinpath.c:431
try_nestloop_path
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:679
consider_parallel_nestloop
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1940
PATH_PARAM_BY_PARENT
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:36
set_join_pathlist_hook
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:30
try_mergejoin_path
static void try_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, bool is_partial)
Definition: joinpath.c:876
consider_parallel_mergejoin
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1900
generate_mergejoin_paths
static void generate_mergejoin_paths(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial)
Definition: joinpath.c:1402
hash_inner_and_outer
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2024
try_partial_mergejoin_path
static void try_partial_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:971
PATH_PARAM_BY_REL
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:42
allow_star_schema_join
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:358
try_partial_hashjoin_path
static void try_partial_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra, bool parallel_hash)
Definition: joinpath.c:1107
match_unsorted_outer
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1650
try_partial_nestloop_path
static void try_partial_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:794
have_dangerous_phv
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1194
Assert
Assert(fmt[strlen(fmt) - 1] !='\n')
list_truncate
List * list_truncate(List *list, int new_size)
Definition: list.c:630
lappend
List * lappend(List *list, void *datum)
Definition: list.c:338
lappend_oid
List * lappend_oid(List *list, Oid datum)
Definition: list.c:374
list_copy
List * list_copy(const List *oldlist)
Definition: list.c:1572
list_delete_nth_cell
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:766
list_free
void list_free(List *list)
Definition: list.c:1545
lcons
List * lcons(void *datum, List *list)
Definition: list.c:494
exprType
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:43
IsA
#define IsA(nodeptr, _type_)
Definition: nodes.h:179
IS_OUTER_JOIN
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:347
JoinType
JoinType
Definition: nodes.h:299
JOIN_SEMI
@ JOIN_SEMI
Definition: nodes.h:318
JOIN_FULL
@ JOIN_FULL
Definition: nodes.h:306
JOIN_INNER
@ JOIN_INNER
Definition: nodes.h:304
JOIN_RIGHT
@ JOIN_RIGHT
Definition: nodes.h:307
JOIN_LEFT
@ JOIN_LEFT
Definition: nodes.h:305
JOIN_UNIQUE_OUTER
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:325
JOIN_UNIQUE_INNER
@ JOIN_UNIQUE_INNER
Definition: nodes.h:326
JOIN_ANTI
@ JOIN_ANTI
Definition: nodes.h:319
build_join_pathkeys
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1093
make_inner_pathkeys_for_merge
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1620
get_cheapest_path_for_pathkeys
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:420
find_mergeclauses_for_outer_pathkeys
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1309
trim_mergeclauses_for_inner_pathkeys
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1723
select_outer_pathkeys_for_merge
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1424
update_mergeclause_eclasses
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1275
get_cheapest_parallel_safe_total_inner
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:498
pathkeys_contained_in
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:340
create_nestloop_path
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:2420
calc_non_nestloop_required_outer
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2387
create_unique_path
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1652
calc_nestloop_required_outer
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2360
reparameterize_path_by_child
Path * reparameterize_path_by_child(PlannerInfo *root, Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:4030
create_mergejoin_path
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:2506
create_memoize_path
MemoizePath * create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, bool binary_mode, double calls)
Definition: pathnode.c:1596
add_partial_path
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
create_material_path
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1564
create_hashjoin_path
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:2572
add_partial_path_precheck
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:867
add_path
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
compare_path_costs
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71
add_path_precheck
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:644
EC_MUST_BE_REDUNDANT
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1394
RINFO_IS_PUSHED_DOWN
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2664
TOTAL_COST
@ TOTAL_COST
Definition: pathnodes.h:38
STARTUP_COST
@ STARTUP_COST
Definition: pathnodes.h:38
PATH_REQ_OUTER
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1643
RELOPT_OTHER_JOINREL
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:821
set_join_pathlist_hook_type
void(* set_join_pathlist_hook_type)(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: paths.h:36
lfirst
#define lfirst(lc)
Definition: pg_list.h:172
list_length
static int list_length(const List *l)
Definition: pg_list.h:152
NIL
#define NIL
Definition: pg_list.h:68
list_head
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
linitial
#define linitial(l)
Definition: pg_list.h:178
lsecond
#define lsecond(l)
Definition: pg_list.h:183
foreach_current_index
#define foreach_current_index(cell)
Definition: pg_list.h:403
InvalidOid
#define InvalidOid
Definition: postgres_ext.h:36
Oid
unsigned int Oid
Definition: postgres_ext.h:31
JoinPathExtraData::mergeclause_list
List * mergeclause_list
Definition: pathnodes.h:3165
JoinPathExtraData::param_source_rels
Relids param_source_rels
Definition: pathnodes.h:3169
JoinPathExtraData::semifactors
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3168
JoinPathExtraData::sjinfo
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3167
List
Definition: pg_list.h:54
Node
Definition: nodes.h:129
OpExpr::args
List * args
Definition: primnodes.h:763
ParamPathInfo::ppi_clauses
List * ppi_clauses
Definition: pathnodes.h:1555
Path::pathkeys
List * pathkeys
Definition: pathnodes.h:1639
Path::pathtype
NodeTag pathtype
Definition: pathnodes.h:1600
Path::rows
Cardinality rows
Definition: pathnodes.h:1634
Path::parallel_safe
bool parallel_safe
Definition: pathnodes.h:1629
PlannerInfo::outer_join_rels
Relids outer_join_rels
Definition: pathnodes.h:261
PlannerInfo::join_info_list
List * join_info_list
Definition: pathnodes.h:340
PlannerInfo::all_baserels
Relids all_baserels
Definition: pathnodes.h:255
RelOptInfo::baserestrictinfo
List * baserestrictinfo
Definition: pathnodes.h:970
RelOptInfo::relids
Relids relids
Definition: pathnodes.h:862
RelOptInfo::reltarget
struct PathTarget * reltarget
Definition: pathnodes.h:884
RelOptInfo::lateral_vars
List * lateral_vars
Definition: pathnodes.h:925
RelOptInfo::consider_parallel
bool consider_parallel
Definition: pathnodes.h:878
RelOptInfo::top_parent_relids
Relids top_parent_relids
Definition: pathnodes.h:994
RelOptInfo::lateral_relids
Relids lateral_relids
Definition: pathnodes.h:904
RelOptInfo::cheapest_parameterized_paths
List * cheapest_parameterized_paths
Definition: pathnodes.h:895
RelOptInfo::pathlist
List * pathlist
Definition: pathnodes.h:889
RelOptInfo::reloptkind
RelOptKind reloptkind
Definition: pathnodes.h:856
RelOptInfo::cheapest_startup_path
struct Path * cheapest_startup_path
Definition: pathnodes.h:892
RelOptInfo::cheapest_total_path
struct Path * cheapest_total_path
Definition: pathnodes.h:893
RelOptInfo::partial_pathlist
List * partial_pathlist
Definition: pathnodes.h:891
RestrictInfo::clause
Expr * clause
Definition: pathnodes.h:2513
SpecialJoinInfo::min_righthand
Relids min_righthand
Definition: pathnodes.h:2830
SpecialJoinInfo::jointype
JoinType jointype
Definition: pathnodes.h:2833
SpecialJoinInfo::min_lefthand
Relids min_lefthand
Definition: pathnodes.h:2829
lookup_type_cache
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:339
TYPECACHE_EQ_OPR
#define TYPECACHE_EQ_OPR
Definition: typcache.h:136
TYPECACHE_HASH_PROC
#define TYPECACHE_HASH_PROC
Definition: typcache.h:140