PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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 "optimizer/cost.h"
22 #include "optimizer/pathnode.h"
23 #include "optimizer/paths.h"
24 #include "optimizer/planmain.h"
25 
26 /* Hook for plugins to get control in add_paths_to_joinrel() */
28 
29 #define PATH_PARAM_BY_REL(path, rel) \
30  ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
31 
32 static void try_partial_mergejoin_path(PlannerInfo *root,
33  RelOptInfo *joinrel,
34  Path *outer_path,
35  Path *inner_path,
36  List *pathkeys,
37  List *mergeclauses,
38  List *outersortkeys,
39  List *innersortkeys,
40  JoinType jointype,
41  JoinPathExtraData *extra);
42 static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
43  RelOptInfo *outerrel, RelOptInfo *innerrel,
44  JoinType jointype, JoinPathExtraData *extra);
45 static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,
46  RelOptInfo *outerrel, RelOptInfo *innerrel,
47  JoinType jointype, JoinPathExtraData *extra);
48 static void consider_parallel_nestloop(PlannerInfo *root,
49  RelOptInfo *joinrel,
50  RelOptInfo *outerrel,
51  RelOptInfo *innerrel,
52  JoinType jointype,
53  JoinPathExtraData *extra);
55  RelOptInfo *joinrel,
56  RelOptInfo *outerrel,
57  RelOptInfo *innerrel,
58  JoinType jointype,
59  JoinPathExtraData *extra,
60  Path *inner_cheapest_total);
61 static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
62  RelOptInfo *outerrel, RelOptInfo *innerrel,
63  JoinType jointype, JoinPathExtraData *extra);
65  RelOptInfo *joinrel,
66  RelOptInfo *outerrel,
67  RelOptInfo *innerrel,
68  List *restrictlist,
69  JoinType jointype,
70  bool *mergejoin_allowed);
71 static void generate_mergejoin_paths(PlannerInfo *root,
72  RelOptInfo *joinrel,
73  RelOptInfo *innerrel,
74  Path *outerpath,
75  JoinType jointype,
76  JoinPathExtraData *extra,
77  bool useallclauses,
78  Path *inner_cheapest_total,
79  List *merge_pathkeys,
80  bool is_partial);
81 
82 
83 /*
84  * add_paths_to_joinrel
85  * Given a join relation and two component rels from which it can be made,
86  * consider all possible paths that use the two component rels as outer
87  * and inner rel respectively. Add these paths to the join rel's pathlist
88  * if they survive comparison with other paths (and remove any existing
89  * paths that are dominated by these paths).
90  *
91  * Modifies the pathlist field of the joinrel node to contain the best
92  * paths found so far.
93  *
94  * jointype is not necessarily the same as sjinfo->jointype; it might be
95  * "flipped around" if we are considering joining the rels in the opposite
96  * direction from what's indicated in sjinfo.
97  *
98  * Also, this routine and others in this module accept the special JoinTypes
99  * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should
100  * unique-ify the outer or inner relation and then apply a regular inner
101  * join. These values are not allowed to propagate outside this module,
102  * however. Path cost estimation code may need to recognize that it's
103  * dealing with such a case --- the combination of nominal jointype INNER
104  * with sjinfo->jointype == JOIN_SEMI indicates that.
105  */
106 void
108  RelOptInfo *joinrel,
109  RelOptInfo *outerrel,
110  RelOptInfo *innerrel,
111  JoinType jointype,
112  SpecialJoinInfo *sjinfo,
113  List *restrictlist)
114 {
115  JoinPathExtraData extra;
116  bool mergejoin_allowed = true;
117  ListCell *lc;
118 
119  extra.restrictlist = restrictlist;
120  extra.mergeclause_list = NIL;
121  extra.sjinfo = sjinfo;
122  extra.param_source_rels = NULL;
123 
124  /*
125  * See if the inner relation is provably unique for this outer rel.
126  *
127  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
128  * matter since the executor can make the equivalent optimization anyway;
129  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
130  * must be considering a semijoin whose inner side is not provably unique
131  * (else reduce_unique_semijoins would've simplified it), so there's no
132  * point in calling innerrel_is_unique. However, if the LHS covers all of
133  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
134  * because the path produced by create_unique_path will be unique relative
135  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
136  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
137  * letting that value escape this module.
138  */
139  switch (jointype)
140  {
141  case JOIN_SEMI:
142  case JOIN_ANTI:
143  extra.inner_unique = false; /* well, unproven */
144  break;
145  case JOIN_UNIQUE_INNER:
146  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
147  outerrel->relids);
148  break;
149  case JOIN_UNIQUE_OUTER:
150  extra.inner_unique = innerrel_is_unique(root,
151  outerrel->relids,
152  innerrel,
153  JOIN_INNER,
154  restrictlist,
155  false);
156  break;
157  default:
158  extra.inner_unique = innerrel_is_unique(root,
159  outerrel->relids,
160  innerrel,
161  jointype,
162  restrictlist,
163  false);
164  break;
165  }
166 
167  /*
168  * Find potential mergejoin clauses. We can skip this if we are not
169  * interested in doing a mergejoin. However, mergejoin may be our only
170  * way of implementing a full outer join, so override enable_mergejoin if
171  * it's a full join.
172  */
173  if (enable_mergejoin || jointype == JOIN_FULL)
175  joinrel,
176  outerrel,
177  innerrel,
178  restrictlist,
179  jointype,
180  &mergejoin_allowed);
181 
182  /*
183  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
184  * for cost estimation. These will be the same for all paths.
185  */
186  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
187  compute_semi_anti_join_factors(root, outerrel, innerrel,
188  jointype, sjinfo, restrictlist,
189  &extra.semifactors);
190 
191  /*
192  * Decide whether it's sensible to generate parameterized paths for this
193  * joinrel, and if so, which relations such paths should require. There
194  * is usually no need to create a parameterized result path unless there
195  * is a join order restriction that prevents joining one of our input rels
196  * directly to the parameter source rel instead of joining to the other
197  * input rel. (But see allow_star_schema_join().) This restriction
198  * reduces the number of parameterized paths we have to deal with at
199  * higher join levels, without compromising the quality of the resulting
200  * plan. We express the restriction as a Relids set that must overlap the
201  * parameterization of any proposed join path.
202  */
203  foreach(lc, root->join_info_list)
204  {
205  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
206 
207  /*
208  * SJ is relevant to this join if we have some part of its RHS
209  * (possibly not all of it), and haven't yet joined to its LHS. (This
210  * test is pretty simplistic, but should be sufficient considering the
211  * join has already been proven legal.) If the SJ is relevant, it
212  * presents constraints for joining to anything not in its RHS.
213  */
214  if (bms_overlap(joinrel->relids, sjinfo2->min_righthand) &&
215  !bms_overlap(joinrel->relids, sjinfo2->min_lefthand))
218  sjinfo2->min_righthand));
219 
220  /* full joins constrain both sides symmetrically */
221  if (sjinfo2->jointype == JOIN_FULL &&
222  bms_overlap(joinrel->relids, sjinfo2->min_lefthand) &&
223  !bms_overlap(joinrel->relids, sjinfo2->min_righthand))
226  sjinfo2->min_lefthand));
227  }
228 
229  /*
230  * However, when a LATERAL subquery is involved, there will simply not be
231  * any paths for the joinrel that aren't parameterized by whatever the
232  * subquery is parameterized by, unless its parameterization is resolved
233  * within the joinrel. So we might as well allow additional dependencies
234  * on whatever residual lateral dependencies the joinrel will have.
235  */
237  joinrel->lateral_relids);
238 
239  /*
240  * 1. Consider mergejoin paths where both relations must be explicitly
241  * sorted. Skip this if we can't mergejoin.
242  */
243  if (mergejoin_allowed)
244  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
245  jointype, &extra);
246 
247  /*
248  * 2. Consider paths where the outer relation need not be explicitly
249  * sorted. This includes both nestloops and mergejoins where the outer
250  * path is already ordered. Again, skip this if we can't mergejoin.
251  * (That's okay because we know that nestloop can't handle right/full
252  * joins at all, so it wouldn't work in the prohibited cases either.)
253  */
254  if (mergejoin_allowed)
255  match_unsorted_outer(root, joinrel, outerrel, innerrel,
256  jointype, &extra);
257 
258 #ifdef NOT_USED
259 
260  /*
261  * 3. Consider paths where the inner relation need not be explicitly
262  * sorted. This includes mergejoins only (nestloops were already built in
263  * match_unsorted_outer).
264  *
265  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
266  * significant difference between the inner and outer side of a mergejoin,
267  * so match_unsorted_inner creates no paths that aren't equivalent to
268  * those made by match_unsorted_outer when add_paths_to_joinrel() is
269  * invoked with the two rels given in the other order.
270  */
271  if (mergejoin_allowed)
272  match_unsorted_inner(root, joinrel, outerrel, innerrel,
273  jointype, &extra);
274 #endif
275 
276  /*
277  * 4. Consider paths where both outer and inner relations must be hashed
278  * before being joined. As above, disregard enable_hashjoin for full
279  * joins, because there may be no other alternative.
280  */
281  if (enable_hashjoin || jointype == JOIN_FULL)
282  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
283  jointype, &extra);
284 
285  /*
286  * 5. If inner and outer relations are foreign tables (or joins) belonging
287  * to the same server and assigned to the same user to check access
288  * permissions as, give the FDW a chance to push down joins.
289  */
290  if (joinrel->fdwroutine &&
292  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
293  outerrel, innerrel,
294  jointype, &extra);
295 
296  /*
297  * 6. Finally, give extensions a chance to manipulate the path list.
298  */
300  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
301  jointype, &extra);
302 }
303 
304 /*
305  * We override the param_source_rels heuristic to accept nestloop paths in
306  * which the outer rel satisfies some but not all of the inner path's
307  * parameterization. This is necessary to get good plans for star-schema
308  * scenarios, in which a parameterized path for a large table may require
309  * parameters from multiple small tables that will not get joined directly to
310  * each other. We can handle that by stacking nestloops that have the small
311  * tables on the outside; but this breaks the rule the param_source_rels
312  * heuristic is based on, namely that parameters should not be passed down
313  * across joins unless there's a join-order-constraint-based reason to do so.
314  * So we ignore the param_source_rels restriction when this case applies.
315  *
316  * allow_star_schema_join() returns TRUE if the param_source_rels restriction
317  * should be overridden, ie, it's okay to perform this join.
318  */
319 static inline bool
321  Relids outerrelids,
322  Relids inner_paramrels)
323 {
324  /*
325  * It's a star-schema case if the outer rel provides some but not all of
326  * the inner rel's parameterization.
327  */
328  return (bms_overlap(inner_paramrels, outerrelids) &&
329  bms_nonempty_difference(inner_paramrels, outerrelids));
330 }
331 
332 /*
333  * try_nestloop_path
334  * Consider a nestloop join path; if it appears useful, push it into
335  * the joinrel's pathlist via add_path().
336  */
337 static void
339  RelOptInfo *joinrel,
340  Path *outer_path,
341  Path *inner_path,
342  List *pathkeys,
343  JoinType jointype,
344  JoinPathExtraData *extra)
345 {
346  Relids required_outer;
347  JoinCostWorkspace workspace;
348  RelOptInfo *innerrel = inner_path->parent;
349  RelOptInfo *outerrel = outer_path->parent;
350  Relids innerrelids = innerrel->relids;
351  Relids outerrelids = outerrel->relids;
352  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
353  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
354 
355  /*
356  * Check to see if proposed path is still parameterized, and reject if the
357  * parameterization wouldn't be sensible --- unless allow_star_schema_join
358  * says to allow it anyway. Also, we must reject if have_dangerous_phv
359  * doesn't like the look of it, which could only happen if the nestloop is
360  * still parameterized.
361  */
362  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
363  innerrelids, inner_paramrels);
364  if (required_outer &&
365  ((!bms_overlap(required_outer, extra->param_source_rels) &&
366  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
367  have_dangerous_phv(root, outerrelids, inner_paramrels)))
368  {
369  /* Waste no memory when we reject a path here */
370  bms_free(required_outer);
371  return;
372  }
373 
374  /*
375  * Do a precheck to quickly eliminate obviously-inferior paths. We
376  * calculate a cheap lower bound on the path's cost and then use
377  * add_path_precheck() to see if the path is clearly going to be dominated
378  * by some existing path for the joinrel. If not, do the full pushup with
379  * creating a fully valid path structure and submitting it to add_path().
380  * The latter two steps are expensive enough to make this two-phase
381  * methodology worthwhile.
382  */
383  initial_cost_nestloop(root, &workspace, jointype,
384  outer_path, inner_path, extra);
385 
386  if (add_path_precheck(joinrel,
387  workspace.startup_cost, workspace.total_cost,
388  pathkeys, required_outer))
389  {
390  add_path(joinrel, (Path *)
392  joinrel,
393  jointype,
394  &workspace,
395  extra,
396  outer_path,
397  inner_path,
398  extra->restrictlist,
399  pathkeys,
400  required_outer));
401  }
402  else
403  {
404  /* Waste no memory when we reject a path here */
405  bms_free(required_outer);
406  }
407 }
408 
409 /*
410  * try_partial_nestloop_path
411  * Consider a partial nestloop join path; if it appears useful, push it into
412  * the joinrel's partial_pathlist via add_partial_path().
413  */
414 static void
416  RelOptInfo *joinrel,
417  Path *outer_path,
418  Path *inner_path,
419  List *pathkeys,
420  JoinType jointype,
421  JoinPathExtraData *extra)
422 {
423  JoinCostWorkspace workspace;
424 
425  /*
426  * If the inner path is parameterized, the parameterization must be fully
427  * satisfied by the proposed outer path. Parameterized partial paths are
428  * not supported. The caller should already have verified that no
429  * extra_lateral_rels are required here.
430  */
432  if (inner_path->param_info != NULL)
433  {
434  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
435 
436  if (!bms_is_subset(inner_paramrels, outer_path->parent->relids))
437  return;
438  }
439 
440  /*
441  * Before creating a path, get a quick lower bound on what it is likely to
442  * cost. Bail out right away if it looks terrible.
443  */
444  initial_cost_nestloop(root, &workspace, jointype,
445  outer_path, inner_path, extra);
446  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
447  return;
448 
449  /* Might be good enough to be worth trying, so let's try it. */
450  add_partial_path(joinrel, (Path *)
452  joinrel,
453  jointype,
454  &workspace,
455  extra,
456  outer_path,
457  inner_path,
458  extra->restrictlist,
459  pathkeys,
460  NULL));
461 }
462 
463 /*
464  * try_mergejoin_path
465  * Consider a merge join path; if it appears useful, push it into
466  * the joinrel's pathlist via add_path().
467  */
468 static void
470  RelOptInfo *joinrel,
471  Path *outer_path,
472  Path *inner_path,
473  List *pathkeys,
474  List *mergeclauses,
475  List *outersortkeys,
476  List *innersortkeys,
477  JoinType jointype,
478  JoinPathExtraData *extra,
479  bool is_partial)
480 {
481  Relids required_outer;
482  JoinCostWorkspace workspace;
483 
484  if (is_partial)
485  {
487  joinrel,
488  outer_path,
489  inner_path,
490  pathkeys,
491  mergeclauses,
492  outersortkeys,
493  innersortkeys,
494  jointype,
495  extra);
496  return;
497  }
498 
499  /*
500  * Check to see if proposed path is still parameterized, and reject if the
501  * parameterization wouldn't be sensible.
502  */
503  required_outer = calc_non_nestloop_required_outer(outer_path,
504  inner_path);
505  if (required_outer &&
506  !bms_overlap(required_outer, extra->param_source_rels))
507  {
508  /* Waste no memory when we reject a path here */
509  bms_free(required_outer);
510  return;
511  }
512 
513  /*
514  * If the given paths are already well enough ordered, we can skip doing
515  * an explicit sort.
516  */
517  if (outersortkeys &&
518  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
519  outersortkeys = NIL;
520  if (innersortkeys &&
521  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
522  innersortkeys = NIL;
523 
524  /*
525  * See comments in try_nestloop_path().
526  */
527  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
528  outer_path, inner_path,
529  outersortkeys, innersortkeys,
530  extra);
531 
532  if (add_path_precheck(joinrel,
533  workspace.startup_cost, workspace.total_cost,
534  pathkeys, required_outer))
535  {
536  add_path(joinrel, (Path *)
538  joinrel,
539  jointype,
540  &workspace,
541  extra,
542  outer_path,
543  inner_path,
544  extra->restrictlist,
545  pathkeys,
546  required_outer,
547  mergeclauses,
548  outersortkeys,
549  innersortkeys));
550  }
551  else
552  {
553  /* Waste no memory when we reject a path here */
554  bms_free(required_outer);
555  }
556 }
557 
558 /*
559  * try_partial_mergejoin_path
560  * Consider a partial merge join path; if it appears useful, push it into
561  * the joinrel's pathlist via add_partial_path().
562  */
563 static void
565  RelOptInfo *joinrel,
566  Path *outer_path,
567  Path *inner_path,
568  List *pathkeys,
569  List *mergeclauses,
570  List *outersortkeys,
571  List *innersortkeys,
572  JoinType jointype,
573  JoinPathExtraData *extra)
574 {
575  JoinCostWorkspace workspace;
576 
577  /*
578  * See comments in try_partial_hashjoin_path().
579  */
581  if (inner_path->param_info != NULL)
582  {
583  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
584 
585  if (!bms_is_empty(inner_paramrels))
586  return;
587  }
588 
589  /*
590  * If the given paths are already well enough ordered, we can skip doing
591  * an explicit sort.
592  */
593  if (outersortkeys &&
594  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
595  outersortkeys = NIL;
596  if (innersortkeys &&
597  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
598  innersortkeys = NIL;
599 
600  /*
601  * See comments in try_partial_nestloop_path().
602  */
603  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
604  outer_path, inner_path,
605  outersortkeys, innersortkeys,
606  extra);
607 
608  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
609  return;
610 
611  /* Might be good enough to be worth trying, so let's try it. */
612  add_partial_path(joinrel, (Path *)
614  joinrel,
615  jointype,
616  &workspace,
617  extra,
618  outer_path,
619  inner_path,
620  extra->restrictlist,
621  pathkeys,
622  NULL,
623  mergeclauses,
624  outersortkeys,
625  innersortkeys));
626 }
627 
628 /*
629  * try_hashjoin_path
630  * Consider a hash join path; if it appears useful, push it into
631  * the joinrel's pathlist via add_path().
632  */
633 static void
635  RelOptInfo *joinrel,
636  Path *outer_path,
637  Path *inner_path,
638  List *hashclauses,
639  JoinType jointype,
640  JoinPathExtraData *extra)
641 {
642  Relids required_outer;
643  JoinCostWorkspace workspace;
644 
645  /*
646  * Check to see if proposed path is still parameterized, and reject if the
647  * parameterization wouldn't be sensible.
648  */
649  required_outer = calc_non_nestloop_required_outer(outer_path,
650  inner_path);
651  if (required_outer &&
652  !bms_overlap(required_outer, extra->param_source_rels))
653  {
654  /* Waste no memory when we reject a path here */
655  bms_free(required_outer);
656  return;
657  }
658 
659  /*
660  * See comments in try_nestloop_path(). Also note that hashjoin paths
661  * never have any output pathkeys, per comments in create_hashjoin_path.
662  */
663  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
664  outer_path, inner_path, extra);
665 
666  if (add_path_precheck(joinrel,
667  workspace.startup_cost, workspace.total_cost,
668  NIL, required_outer))
669  {
670  add_path(joinrel, (Path *)
672  joinrel,
673  jointype,
674  &workspace,
675  extra,
676  outer_path,
677  inner_path,
678  extra->restrictlist,
679  required_outer,
680  hashclauses));
681  }
682  else
683  {
684  /* Waste no memory when we reject a path here */
685  bms_free(required_outer);
686  }
687 }
688 
689 /*
690  * try_partial_hashjoin_path
691  * Consider a partial hashjoin join path; if it appears useful, push it into
692  * the joinrel's partial_pathlist via add_partial_path().
693  */
694 static void
696  RelOptInfo *joinrel,
697  Path *outer_path,
698  Path *inner_path,
699  List *hashclauses,
700  JoinType jointype,
701  JoinPathExtraData *extra)
702 {
703  JoinCostWorkspace workspace;
704 
705  /*
706  * If the inner path is parameterized, the parameterization must be fully
707  * satisfied by the proposed outer path. Parameterized partial paths are
708  * not supported. The caller should already have verified that no
709  * extra_lateral_rels are required here.
710  */
712  if (inner_path->param_info != NULL)
713  {
714  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
715 
716  if (!bms_is_empty(inner_paramrels))
717  return;
718  }
719 
720  /*
721  * Before creating a path, get a quick lower bound on what it is likely to
722  * cost. Bail out right away if it looks terrible.
723  */
724  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
725  outer_path, inner_path, extra);
726  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
727  return;
728 
729  /* Might be good enough to be worth trying, so let's try it. */
730  add_partial_path(joinrel, (Path *)
732  joinrel,
733  jointype,
734  &workspace,
735  extra,
736  outer_path,
737  inner_path,
738  extra->restrictlist,
739  NULL,
740  hashclauses));
741 }
742 
743 /*
744  * clause_sides_match_join
745  * Determine whether a join clause is of the right form to use in this join.
746  *
747  * We already know that the clause is a binary opclause referencing only the
748  * rels in the current join. The point here is to check whether it has the
749  * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
750  * rather than mixing outer and inner vars on either side. If it matches,
751  * we set the transient flag outer_is_left to identify which side is which.
752  */
753 static inline bool
755  RelOptInfo *innerrel)
756 {
757  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
758  bms_is_subset(rinfo->right_relids, innerrel->relids))
759  {
760  /* lefthand side is outer */
761  rinfo->outer_is_left = true;
762  return true;
763  }
764  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
765  bms_is_subset(rinfo->right_relids, outerrel->relids))
766  {
767  /* righthand side is outer */
768  rinfo->outer_is_left = false;
769  return true;
770  }
771  return false; /* no good for these input relations */
772 }
773 
774 /*
775  * sort_inner_and_outer
776  * Create mergejoin join paths by explicitly sorting both the outer and
777  * inner join relations on each available merge ordering.
778  *
779  * 'joinrel' is the join relation
780  * 'outerrel' is the outer join relation
781  * 'innerrel' is the inner join relation
782  * 'jointype' is the type of join to do
783  * 'extra' contains additional input values
784  */
785 static void
787  RelOptInfo *joinrel,
788  RelOptInfo *outerrel,
789  RelOptInfo *innerrel,
790  JoinType jointype,
791  JoinPathExtraData *extra)
792 {
793  JoinType save_jointype = jointype;
794  Path *outer_path;
795  Path *inner_path;
796  Path *cheapest_partial_outer = NULL;
797  Path *cheapest_safe_inner = NULL;
798  List *all_pathkeys;
799  ListCell *l;
800 
801  /*
802  * We only consider the cheapest-total-cost input paths, since we are
803  * assuming here that a sort is required. We will consider
804  * cheapest-startup-cost input paths later, and only if they don't need a
805  * sort.
806  *
807  * This function intentionally does not consider parameterized input
808  * paths, except when the cheapest-total is parameterized. If we did so,
809  * we'd have a combinatorial explosion of mergejoin paths of dubious
810  * value. This interacts with decisions elsewhere that also discriminate
811  * against mergejoins with parameterized inputs; see comments in
812  * src/backend/optimizer/README.
813  */
814  outer_path = outerrel->cheapest_total_path;
815  inner_path = innerrel->cheapest_total_path;
816 
817  /*
818  * If either cheapest-total path is parameterized by the other rel, we
819  * can't use a mergejoin. (There's no use looking for alternative input
820  * paths, since these should already be the least-parameterized available
821  * paths.)
822  */
823  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
824  PATH_PARAM_BY_REL(inner_path, outerrel))
825  return;
826 
827  /*
828  * If unique-ification is requested, do it and then handle as a plain
829  * inner join.
830  */
831  if (jointype == JOIN_UNIQUE_OUTER)
832  {
833  outer_path = (Path *) create_unique_path(root, outerrel,
834  outer_path, extra->sjinfo);
835  Assert(outer_path);
836  jointype = JOIN_INNER;
837  }
838  else if (jointype == JOIN_UNIQUE_INNER)
839  {
840  inner_path = (Path *) create_unique_path(root, innerrel,
841  inner_path, extra->sjinfo);
842  Assert(inner_path);
843  jointype = JOIN_INNER;
844  }
845 
846  /*
847  * If the joinrel is parallel-safe, we may be able to consider a partial
848  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
849  * outer path will be partial, and therefore we won't be able to properly
850  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
851  * JOIN_RIGHT, because they can produce false null extended rows. Also,
852  * the resulting path must not be parameterized.
853  */
854  if (joinrel->consider_parallel &&
855  save_jointype != JOIN_UNIQUE_OUTER &&
856  save_jointype != JOIN_FULL &&
857  save_jointype != JOIN_RIGHT &&
858  outerrel->partial_pathlist != NIL &&
859  bms_is_empty(joinrel->lateral_relids))
860  {
861  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
862 
863  if (inner_path->parallel_safe)
864  cheapest_safe_inner = inner_path;
865  else if (save_jointype != JOIN_UNIQUE_INNER)
866  cheapest_safe_inner =
868  }
869 
870  /*
871  * Each possible ordering of the available mergejoin clauses will generate
872  * a differently-sorted result path at essentially the same cost. We have
873  * no basis for choosing one over another at this level of joining, but
874  * some sort orders may be more useful than others for higher-level
875  * mergejoins, so it's worth considering multiple orderings.
876  *
877  * Actually, it's not quite true that every mergeclause ordering will
878  * generate a different path order, because some of the clauses may be
879  * partially redundant (refer to the same EquivalenceClasses). Therefore,
880  * what we do is convert the mergeclause list to a list of canonical
881  * pathkeys, and then consider different orderings of the pathkeys.
882  *
883  * Generating a path for *every* permutation of the pathkeys doesn't seem
884  * like a winning strategy; the cost in planning time is too high. For
885  * now, we generate one path for each pathkey, listing that pathkey first
886  * and the rest in random order. This should allow at least a one-clause
887  * mergejoin without re-sorting against any other possible mergejoin
888  * partner path. But if we've not guessed the right ordering of secondary
889  * keys, we may end up evaluating clauses as qpquals when they could have
890  * been done as mergeclauses. (In practice, it's rare that there's more
891  * than two or three mergeclauses, so expending a huge amount of thought
892  * on that is probably not worth it.)
893  *
894  * The pathkey order returned by select_outer_pathkeys_for_merge() has
895  * some heuristics behind it (see that function), so be sure to try it
896  * exactly as-is as well as making variants.
897  */
898  all_pathkeys = select_outer_pathkeys_for_merge(root,
899  extra->mergeclause_list,
900  joinrel);
901 
902  foreach(l, all_pathkeys)
903  {
904  List *front_pathkey = (List *) lfirst(l);
905  List *cur_mergeclauses;
906  List *outerkeys;
907  List *innerkeys;
908  List *merge_pathkeys;
909 
910  /* Make a pathkey list with this guy first */
911  if (l != list_head(all_pathkeys))
912  outerkeys = lcons(front_pathkey,
913  list_delete_ptr(list_copy(all_pathkeys),
914  front_pathkey));
915  else
916  outerkeys = all_pathkeys; /* no work at first one... */
917 
918  /* Sort the mergeclauses into the corresponding ordering */
919  cur_mergeclauses = find_mergeclauses_for_pathkeys(root,
920  outerkeys,
921  true,
922  extra->mergeclause_list);
923 
924  /* Should have used them all... */
925  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
926 
927  /* Build sort pathkeys for the inner side */
928  innerkeys = make_inner_pathkeys_for_merge(root,
929  cur_mergeclauses,
930  outerkeys);
931 
932  /* Build pathkeys representing output sort order */
933  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
934  outerkeys);
935 
936  /*
937  * And now we can make the path.
938  *
939  * Note: it's possible that the cheapest paths will already be sorted
940  * properly. try_mergejoin_path will detect that case and suppress an
941  * explicit sort step, so we needn't do so here.
942  */
943  try_mergejoin_path(root,
944  joinrel,
945  outer_path,
946  inner_path,
947  merge_pathkeys,
948  cur_mergeclauses,
949  outerkeys,
950  innerkeys,
951  jointype,
952  extra,
953  false);
954 
955  /*
956  * If we have partial outer and parallel safe inner path then try
957  * partial mergejoin path.
958  */
959  if (cheapest_partial_outer && cheapest_safe_inner)
961  joinrel,
962  cheapest_partial_outer,
963  cheapest_safe_inner,
964  merge_pathkeys,
965  cur_mergeclauses,
966  outerkeys,
967  innerkeys,
968  jointype,
969  extra);
970  }
971 }
972 
973 /*
974  * generate_mergejoin_paths
975  * Creates possible mergejoin paths for input outerpath.
976  *
977  * We generate mergejoins if mergejoin clauses are available. We have
978  * two ways to generate the inner path for a mergejoin: sort the cheapest
979  * inner path, or use an inner path that is already suitably ordered for the
980  * merge. If we have several mergeclauses, it could be that there is no inner
981  * path (or only a very expensive one) for the full list of mergeclauses, but
982  * better paths exist if we truncate the mergeclause list (thereby discarding
983  * some sort key requirements). So, we consider truncations of the
984  * mergeclause list as well as the full list. (Ideally we'd consider all
985  * subsets of the mergeclause list, but that seems way too expensive.)
986  */
987 static void
989  RelOptInfo *joinrel,
990  RelOptInfo *innerrel,
991  Path *outerpath,
992  JoinType jointype,
993  JoinPathExtraData *extra,
994  bool useallclauses,
995  Path *inner_cheapest_total,
996  List *merge_pathkeys,
997  bool is_partial)
998 {
999  List *mergeclauses;
1000  List *innersortkeys;
1001  List *trialsortkeys;
1002  Path *cheapest_startup_inner;
1003  Path *cheapest_total_inner;
1004  JoinType save_jointype = jointype;
1005  int num_sortkeys;
1006  int sortkeycnt;
1007 
1008  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1009  jointype = JOIN_INNER;
1010 
1011  /* Look for useful mergeclauses (if any) */
1012  mergeclauses = find_mergeclauses_for_pathkeys(root,
1013  outerpath->pathkeys,
1014  true,
1015  extra->mergeclause_list);
1016 
1017  /*
1018  * Done with this outer path if no chance for a mergejoin.
1019  *
1020  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1021  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1022  * but since mergejoin is our only join type that supports FULL JOIN
1023  * without any join clauses, it's necessary to generate a clauseless
1024  * mergejoin path instead.
1025  */
1026  if (mergeclauses == NIL)
1027  {
1028  if (jointype == JOIN_FULL)
1029  /* okay to try for mergejoin */ ;
1030  else
1031  return;
1032  }
1033  if (useallclauses &&
1034  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1035  return;
1036 
1037  /* Compute the required ordering of the inner path */
1038  innersortkeys = make_inner_pathkeys_for_merge(root,
1039  mergeclauses,
1040  outerpath->pathkeys);
1041 
1042  /*
1043  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1044  * a sort will be needed, only cheapest total cost matters. (But
1045  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1046  * already correctly sorted.)
1047  */
1048  try_mergejoin_path(root,
1049  joinrel,
1050  outerpath,
1051  inner_cheapest_total,
1052  merge_pathkeys,
1053  mergeclauses,
1054  NIL,
1055  innersortkeys,
1056  jointype,
1057  extra,
1058  is_partial);
1059 
1060  /* Can't do anything else if inner path needs to be unique'd */
1061  if (save_jointype == JOIN_UNIQUE_INNER)
1062  return;
1063 
1064  /*
1065  * Look for presorted inner paths that satisfy the innersortkey list ---
1066  * or any truncation thereof, if we are allowed to build a mergejoin using
1067  * a subset of the merge clauses. Here, we consider both cheap startup
1068  * cost and cheap total cost.
1069  *
1070  * Currently we do not consider parameterized inner paths here. This
1071  * interacts with decisions elsewhere that also discriminate against
1072  * mergejoins with parameterized inputs; see comments in
1073  * src/backend/optimizer/README.
1074  *
1075  * As we shorten the sortkey list, we should consider only paths that are
1076  * strictly cheaper than (in particular, not the same as) any path found
1077  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1078  * merge keys than a given path allows (treating the rest as plain
1079  * joinquals), which is unlikely to be a good idea. Also, eliminating
1080  * paths here on the basis of compare_path_costs is a lot cheaper than
1081  * building the mergejoin path only to throw it away.
1082  *
1083  * If inner_cheapest_total is well enough sorted to have not required a
1084  * sort in the path made above, we shouldn't make a duplicate path with
1085  * it, either. We handle that case with the same logic that handles the
1086  * previous consideration, by initializing the variables that track
1087  * cheapest-so-far properly. Note that we do NOT reject
1088  * inner_cheapest_total if we find it matches some shorter set of
1089  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1090  * sorting inner_cheapest_total, whereas we did sort it above, so the
1091  * plans being considered are different.
1092  */
1093  if (pathkeys_contained_in(innersortkeys,
1094  inner_cheapest_total->pathkeys))
1095  {
1096  /* inner_cheapest_total didn't require a sort */
1097  cheapest_startup_inner = inner_cheapest_total;
1098  cheapest_total_inner = inner_cheapest_total;
1099  }
1100  else
1101  {
1102  /* it did require a sort, at least for the full set of keys */
1103  cheapest_startup_inner = NULL;
1104  cheapest_total_inner = NULL;
1105  }
1106  num_sortkeys = list_length(innersortkeys);
1107  if (num_sortkeys > 1 && !useallclauses)
1108  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1109  else
1110  trialsortkeys = innersortkeys; /* won't really truncate */
1111 
1112  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1113  {
1114  Path *innerpath;
1115  List *newclauses = NIL;
1116 
1117  /*
1118  * Look for an inner path ordered well enough for the first
1119  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1120  * destructively, which is why we made a copy...
1121  */
1122  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1123  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1124  trialsortkeys,
1125  NULL,
1126  TOTAL_COST,
1127  is_partial);
1128  if (innerpath != NULL &&
1129  (cheapest_total_inner == NULL ||
1130  compare_path_costs(innerpath, cheapest_total_inner,
1131  TOTAL_COST) < 0))
1132  {
1133  /* Found a cheap (or even-cheaper) sorted path */
1134  /* Select the right mergeclauses, if we didn't already */
1135  if (sortkeycnt < num_sortkeys)
1136  {
1137  newclauses =
1139  trialsortkeys,
1140  false,
1141  mergeclauses);
1142  Assert(newclauses != NIL);
1143  }
1144  else
1145  newclauses = mergeclauses;
1146  try_mergejoin_path(root,
1147  joinrel,
1148  outerpath,
1149  innerpath,
1150  merge_pathkeys,
1151  newclauses,
1152  NIL,
1153  NIL,
1154  jointype,
1155  extra,
1156  is_partial);
1157  cheapest_total_inner = innerpath;
1158  }
1159  /* Same on the basis of cheapest startup cost ... */
1160  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1161  trialsortkeys,
1162  NULL,
1163  STARTUP_COST,
1164  is_partial);
1165  if (innerpath != NULL &&
1166  (cheapest_startup_inner == NULL ||
1167  compare_path_costs(innerpath, cheapest_startup_inner,
1168  STARTUP_COST) < 0))
1169  {
1170  /* Found a cheap (or even-cheaper) sorted path */
1171  if (innerpath != cheapest_total_inner)
1172  {
1173  /*
1174  * Avoid rebuilding clause list if we already made one; saves
1175  * memory in big join trees...
1176  */
1177  if (newclauses == NIL)
1178  {
1179  if (sortkeycnt < num_sortkeys)
1180  {
1181  newclauses =
1183  trialsortkeys,
1184  false,
1185  mergeclauses);
1186  Assert(newclauses != NIL);
1187  }
1188  else
1189  newclauses = mergeclauses;
1190  }
1191  try_mergejoin_path(root,
1192  joinrel,
1193  outerpath,
1194  innerpath,
1195  merge_pathkeys,
1196  newclauses,
1197  NIL,
1198  NIL,
1199  jointype,
1200  extra,
1201  is_partial);
1202  }
1203  cheapest_startup_inner = innerpath;
1204  }
1205 
1206  /*
1207  * Don't consider truncated sortkeys if we need all clauses.
1208  */
1209  if (useallclauses)
1210  break;
1211  }
1212 }
1213 
1214 /*
1215  * match_unsorted_outer
1216  * Creates possible join paths for processing a single join relation
1217  * 'joinrel' by employing either iterative substitution or
1218  * mergejoining on each of its possible outer paths (considering
1219  * only outer paths that are already ordered well enough for merging).
1220  *
1221  * We always generate a nestloop path for each available outer path.
1222  * In fact we may generate as many as five: one on the cheapest-total-cost
1223  * inner path, one on the same with materialization, one on the
1224  * cheapest-startup-cost inner path (if different), one on the
1225  * cheapest-total inner-indexscan path (if any), and one on the
1226  * cheapest-startup inner-indexscan path (if different).
1227  *
1228  * We also consider mergejoins if mergejoin clauses are available. See
1229  * detailed comments in generate_mergejoin_paths.
1230  *
1231  * 'joinrel' is the join relation
1232  * 'outerrel' is the outer join relation
1233  * 'innerrel' is the inner join relation
1234  * 'jointype' is the type of join to do
1235  * 'extra' contains additional input values
1236  */
1237 static void
1239  RelOptInfo *joinrel,
1240  RelOptInfo *outerrel,
1241  RelOptInfo *innerrel,
1242  JoinType jointype,
1243  JoinPathExtraData *extra)
1244 {
1245  JoinType save_jointype = jointype;
1246  bool nestjoinOK;
1247  bool useallclauses;
1248  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1249  Path *matpath = NULL;
1250  ListCell *lc1;
1251 
1252  /*
1253  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1254  * are doing a right or full mergejoin, we must use *all* the mergeclauses
1255  * as join clauses, else we will not have a valid plan. (Although these
1256  * two flags are currently inverses, keep them separate for clarity and
1257  * possible future changes.)
1258  */
1259  switch (jointype)
1260  {
1261  case JOIN_INNER:
1262  case JOIN_LEFT:
1263  case JOIN_SEMI:
1264  case JOIN_ANTI:
1265  nestjoinOK = true;
1266  useallclauses = false;
1267  break;
1268  case JOIN_RIGHT:
1269  case JOIN_FULL:
1270  nestjoinOK = false;
1271  useallclauses = true;
1272  break;
1273  case JOIN_UNIQUE_OUTER:
1274  case JOIN_UNIQUE_INNER:
1275  jointype = JOIN_INNER;
1276  nestjoinOK = true;
1277  useallclauses = false;
1278  break;
1279  default:
1280  elog(ERROR, "unrecognized join type: %d",
1281  (int) jointype);
1282  nestjoinOK = false; /* keep compiler quiet */
1283  useallclauses = false;
1284  break;
1285  }
1286 
1287  /*
1288  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1289  * we will consider it below as a member of cheapest_parameterized_paths,
1290  * but the other possibilities considered in this routine aren't usable.
1291  */
1292  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1293  inner_cheapest_total = NULL;
1294 
1295  /*
1296  * If we need to unique-ify the inner path, we will consider only the
1297  * cheapest-total inner.
1298  */
1299  if (save_jointype == JOIN_UNIQUE_INNER)
1300  {
1301  /* No way to do this with an inner path parameterized by outer rel */
1302  if (inner_cheapest_total == NULL)
1303  return;
1304  inner_cheapest_total = (Path *)
1305  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1306  Assert(inner_cheapest_total);
1307  }
1308  else if (nestjoinOK)
1309  {
1310  /*
1311  * Consider materializing the cheapest inner path, unless
1312  * enable_material is off or the path in question materializes its
1313  * output anyway.
1314  */
1315  if (enable_material && inner_cheapest_total != NULL &&
1316  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1317  matpath = (Path *)
1318  create_material_path(innerrel, inner_cheapest_total);
1319  }
1320 
1321  foreach(lc1, outerrel->pathlist)
1322  {
1323  Path *outerpath = (Path *) lfirst(lc1);
1324  List *merge_pathkeys;
1325 
1326  /*
1327  * We cannot use an outer path that is parameterized by the inner rel.
1328  */
1329  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1330  continue;
1331 
1332  /*
1333  * If we need to unique-ify the outer path, it's pointless to consider
1334  * any but the cheapest outer. (XXX we don't consider parameterized
1335  * outers, nor inners, for unique-ified cases. Should we?)
1336  */
1337  if (save_jointype == JOIN_UNIQUE_OUTER)
1338  {
1339  if (outerpath != outerrel->cheapest_total_path)
1340  continue;
1341  outerpath = (Path *) create_unique_path(root, outerrel,
1342  outerpath, extra->sjinfo);
1343  Assert(outerpath);
1344  }
1345 
1346  /*
1347  * The result will have this sort order (even if it is implemented as
1348  * a nestloop, and even if some of the mergeclauses are implemented by
1349  * qpquals rather than as true mergeclauses):
1350  */
1351  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1352  outerpath->pathkeys);
1353 
1354  if (save_jointype == JOIN_UNIQUE_INNER)
1355  {
1356  /*
1357  * Consider nestloop join, but only with the unique-ified cheapest
1358  * inner path
1359  */
1360  try_nestloop_path(root,
1361  joinrel,
1362  outerpath,
1363  inner_cheapest_total,
1364  merge_pathkeys,
1365  jointype,
1366  extra);
1367  }
1368  else if (nestjoinOK)
1369  {
1370  /*
1371  * Consider nestloop joins using this outer path and various
1372  * available paths for the inner relation. We consider the
1373  * cheapest-total paths for each available parameterization of the
1374  * inner relation, including the unparameterized case.
1375  */
1376  ListCell *lc2;
1377 
1378  foreach(lc2, innerrel->cheapest_parameterized_paths)
1379  {
1380  Path *innerpath = (Path *) lfirst(lc2);
1381 
1382  try_nestloop_path(root,
1383  joinrel,
1384  outerpath,
1385  innerpath,
1386  merge_pathkeys,
1387  jointype,
1388  extra);
1389  }
1390 
1391  /* Also consider materialized form of the cheapest inner path */
1392  if (matpath != NULL)
1393  try_nestloop_path(root,
1394  joinrel,
1395  outerpath,
1396  matpath,
1397  merge_pathkeys,
1398  jointype,
1399  extra);
1400  }
1401 
1402  /* Can't do anything else if outer path needs to be unique'd */
1403  if (save_jointype == JOIN_UNIQUE_OUTER)
1404  continue;
1405 
1406  /* Can't do anything else if inner rel is parameterized by outer */
1407  if (inner_cheapest_total == NULL)
1408  continue;
1409 
1410  /* Generate merge join paths */
1411  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1412  save_jointype, extra, useallclauses,
1413  inner_cheapest_total, merge_pathkeys,
1414  false);
1415  }
1416 
1417  /*
1418  * Consider partial nestloop and mergejoin plan if outerrel has any
1419  * partial path and the joinrel is parallel-safe. However, we can't
1420  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1421  * therefore we won't be able to properly guarantee uniqueness. Nor can
1422  * we handle extra_lateral_rels, since partial paths must not be
1423  * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1424  * because they can produce false null extended rows.
1425  */
1426  if (joinrel->consider_parallel &&
1427  save_jointype != JOIN_UNIQUE_OUTER &&
1428  save_jointype != JOIN_FULL &&
1429  save_jointype != JOIN_RIGHT &&
1430  outerrel->partial_pathlist != NIL &&
1431  bms_is_empty(joinrel->lateral_relids))
1432  {
1433  if (nestjoinOK)
1434  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1435  save_jointype, extra);
1436 
1437  /*
1438  * If inner_cheapest_total is NULL or non parallel-safe then find the
1439  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1440  * can't use any alternative inner path.
1441  */
1442  if (inner_cheapest_total == NULL ||
1443  !inner_cheapest_total->parallel_safe)
1444  {
1445  if (save_jointype == JOIN_UNIQUE_INNER)
1446  return;
1447 
1448  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(
1449  innerrel->pathlist);
1450  }
1451 
1452  if (inner_cheapest_total)
1453  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1454  save_jointype, extra,
1455  inner_cheapest_total);
1456  }
1457 }
1458 
1459 /*
1460  * consider_parallel_mergejoin
1461  * Try to build partial paths for a joinrel by joining a partial path
1462  * for the outer relation to a complete path for the inner relation.
1463  *
1464  * 'joinrel' is the join relation
1465  * 'outerrel' is the outer join relation
1466  * 'innerrel' is the inner join relation
1467  * 'jointype' is the type of join to do
1468  * 'extra' contains additional input values
1469  * 'inner_cheapest_total' cheapest total path for innerrel
1470  */
1471 static void
1473  RelOptInfo *joinrel,
1474  RelOptInfo *outerrel,
1475  RelOptInfo *innerrel,
1476  JoinType jointype,
1477  JoinPathExtraData *extra,
1478  Path *inner_cheapest_total)
1479 {
1480  ListCell *lc1;
1481 
1482  /* generate merge join path for each partial outer path */
1483  foreach(lc1, outerrel->partial_pathlist)
1484  {
1485  Path *outerpath = (Path *) lfirst(lc1);
1486  List *merge_pathkeys;
1487 
1488  /*
1489  * Figure out what useful ordering any paths we create will have.
1490  */
1491  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1492  outerpath->pathkeys);
1493 
1494  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1495  extra, false, inner_cheapest_total,
1496  merge_pathkeys, true);
1497  }
1498 }
1499 
1500 /*
1501  * consider_parallel_nestloop
1502  * Try to build partial paths for a joinrel by joining a partial path for the
1503  * outer relation to a complete path for the inner relation.
1504  *
1505  * 'joinrel' is the join relation
1506  * 'outerrel' is the outer join relation
1507  * 'innerrel' is the inner join relation
1508  * 'jointype' is the type of join to do
1509  * 'extra' contains additional input values
1510  */
1511 static void
1513  RelOptInfo *joinrel,
1514  RelOptInfo *outerrel,
1515  RelOptInfo *innerrel,
1516  JoinType jointype,
1517  JoinPathExtraData *extra)
1518 {
1519  JoinType save_jointype = jointype;
1520  ListCell *lc1;
1521 
1522  if (jointype == JOIN_UNIQUE_INNER)
1523  jointype = JOIN_INNER;
1524 
1525  foreach(lc1, outerrel->partial_pathlist)
1526  {
1527  Path *outerpath = (Path *) lfirst(lc1);
1528  List *pathkeys;
1529  ListCell *lc2;
1530 
1531  /* Figure out what useful ordering any paths we create will have. */
1532  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1533  outerpath->pathkeys);
1534 
1535  /*
1536  * Try the cheapest parameterized paths; only those which will produce
1537  * an unparameterized path when joined to this outerrel will survive
1538  * try_partial_nestloop_path. The cheapest unparameterized path is
1539  * also in this list.
1540  */
1541  foreach(lc2, innerrel->cheapest_parameterized_paths)
1542  {
1543  Path *innerpath = (Path *) lfirst(lc2);
1544 
1545  /* Can't join to an inner path that is not parallel-safe */
1546  if (!innerpath->parallel_safe)
1547  continue;
1548 
1549  /*
1550  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1551  * cheapest_total_path, and we have to unique-ify it. (We might
1552  * be able to relax this to allow other safe, unparameterized
1553  * inner paths, but right now create_unique_path is not on board
1554  * with that.)
1555  */
1556  if (save_jointype == JOIN_UNIQUE_INNER)
1557  {
1558  if (innerpath != innerrel->cheapest_total_path)
1559  continue;
1560  innerpath = (Path *) create_unique_path(root, innerrel,
1561  innerpath,
1562  extra->sjinfo);
1563  Assert(innerpath);
1564  }
1565 
1566  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1567  pathkeys, jointype, extra);
1568  }
1569  }
1570 }
1571 
1572 /*
1573  * hash_inner_and_outer
1574  * Create hashjoin join paths by explicitly hashing both the outer and
1575  * inner keys of each available hash clause.
1576  *
1577  * 'joinrel' is the join relation
1578  * 'outerrel' is the outer join relation
1579  * 'innerrel' is the inner join relation
1580  * 'jointype' is the type of join to do
1581  * 'extra' contains additional input values
1582  */
1583 static void
1585  RelOptInfo *joinrel,
1586  RelOptInfo *outerrel,
1587  RelOptInfo *innerrel,
1588  JoinType jointype,
1589  JoinPathExtraData *extra)
1590 {
1591  JoinType save_jointype = jointype;
1592  bool isouterjoin = IS_OUTER_JOIN(jointype);
1593  List *hashclauses;
1594  ListCell *l;
1595 
1596  /*
1597  * We need to build only one hashclauses list for any given pair of outer
1598  * and inner relations; all of the hashable clauses will be used as keys.
1599  *
1600  * Scan the join's restrictinfo list to find hashjoinable clauses that are
1601  * usable with this pair of sub-relations.
1602  */
1603  hashclauses = NIL;
1604  foreach(l, extra->restrictlist)
1605  {
1606  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1607 
1608  /*
1609  * If processing an outer join, only use its own join clauses for
1610  * hashing. For inner joins we need not be so picky.
1611  */
1612  if (isouterjoin && restrictinfo->is_pushed_down)
1613  continue;
1614 
1615  if (!restrictinfo->can_join ||
1616  restrictinfo->hashjoinoperator == InvalidOid)
1617  continue; /* not hashjoinable */
1618 
1619  /*
1620  * Check if clause has the form "outer op inner" or "inner op outer".
1621  */
1622  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1623  continue; /* no good for these input relations */
1624 
1625  hashclauses = lappend(hashclauses, restrictinfo);
1626  }
1627 
1628  /* If we found any usable hashclauses, make paths */
1629  if (hashclauses)
1630  {
1631  /*
1632  * We consider both the cheapest-total-cost and cheapest-startup-cost
1633  * outer paths. There's no need to consider any but the
1634  * cheapest-total-cost inner path, however.
1635  */
1636  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
1637  Path *cheapest_total_outer = outerrel->cheapest_total_path;
1638  Path *cheapest_total_inner = innerrel->cheapest_total_path;
1639 
1640  /*
1641  * If either cheapest-total path is parameterized by the other rel, we
1642  * can't use a hashjoin. (There's no use looking for alternative
1643  * input paths, since these should already be the least-parameterized
1644  * available paths.)
1645  */
1646  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
1647  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
1648  return;
1649 
1650  /* Unique-ify if need be; we ignore parameterized possibilities */
1651  if (jointype == JOIN_UNIQUE_OUTER)
1652  {
1653  cheapest_total_outer = (Path *)
1654  create_unique_path(root, outerrel,
1655  cheapest_total_outer, extra->sjinfo);
1656  Assert(cheapest_total_outer);
1657  jointype = JOIN_INNER;
1658  try_hashjoin_path(root,
1659  joinrel,
1660  cheapest_total_outer,
1661  cheapest_total_inner,
1662  hashclauses,
1663  jointype,
1664  extra);
1665  /* no possibility of cheap startup here */
1666  }
1667  else if (jointype == JOIN_UNIQUE_INNER)
1668  {
1669  cheapest_total_inner = (Path *)
1670  create_unique_path(root, innerrel,
1671  cheapest_total_inner, extra->sjinfo);
1672  Assert(cheapest_total_inner);
1673  jointype = JOIN_INNER;
1674  try_hashjoin_path(root,
1675  joinrel,
1676  cheapest_total_outer,
1677  cheapest_total_inner,
1678  hashclauses,
1679  jointype,
1680  extra);
1681  if (cheapest_startup_outer != NULL &&
1682  cheapest_startup_outer != cheapest_total_outer)
1683  try_hashjoin_path(root,
1684  joinrel,
1685  cheapest_startup_outer,
1686  cheapest_total_inner,
1687  hashclauses,
1688  jointype,
1689  extra);
1690  }
1691  else
1692  {
1693  /*
1694  * For other jointypes, we consider the cheapest startup outer
1695  * together with the cheapest total inner, and then consider
1696  * pairings of cheapest-total paths including parameterized ones.
1697  * There is no use in generating parameterized paths on the basis
1698  * of possibly cheap startup cost, so this is sufficient.
1699  */
1700  ListCell *lc1;
1701  ListCell *lc2;
1702 
1703  if (cheapest_startup_outer != NULL)
1704  try_hashjoin_path(root,
1705  joinrel,
1706  cheapest_startup_outer,
1707  cheapest_total_inner,
1708  hashclauses,
1709  jointype,
1710  extra);
1711 
1712  foreach(lc1, outerrel->cheapest_parameterized_paths)
1713  {
1714  Path *outerpath = (Path *) lfirst(lc1);
1715 
1716  /*
1717  * We cannot use an outer path that is parameterized by the
1718  * inner rel.
1719  */
1720  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1721  continue;
1722 
1723  foreach(lc2, innerrel->cheapest_parameterized_paths)
1724  {
1725  Path *innerpath = (Path *) lfirst(lc2);
1726 
1727  /*
1728  * We cannot use an inner path that is parameterized by
1729  * the outer rel, either.
1730  */
1731  if (PATH_PARAM_BY_REL(innerpath, outerrel))
1732  continue;
1733 
1734  if (outerpath == cheapest_startup_outer &&
1735  innerpath == cheapest_total_inner)
1736  continue; /* already tried it */
1737 
1738  try_hashjoin_path(root,
1739  joinrel,
1740  outerpath,
1741  innerpath,
1742  hashclauses,
1743  jointype,
1744  extra);
1745  }
1746  }
1747  }
1748 
1749  /*
1750  * If the joinrel is parallel-safe, we may be able to consider a
1751  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
1752  * because the outer path will be partial, and therefore we won't be
1753  * able to properly guarantee uniqueness. Similarly, we can't handle
1754  * JOIN_FULL and JOIN_RIGHT, because they can produce false null
1755  * extended rows. Also, the resulting path must not be parameterized.
1756  */
1757  if (joinrel->consider_parallel &&
1758  save_jointype != JOIN_UNIQUE_OUTER &&
1759  save_jointype != JOIN_FULL &&
1760  save_jointype != JOIN_RIGHT &&
1761  outerrel->partial_pathlist != NIL &&
1762  bms_is_empty(joinrel->lateral_relids))
1763  {
1764  Path *cheapest_partial_outer;
1765  Path *cheapest_safe_inner = NULL;
1766 
1767  cheapest_partial_outer =
1768  (Path *) linitial(outerrel->partial_pathlist);
1769 
1770  /*
1771  * Normally, given that the joinrel is parallel-safe, the cheapest
1772  * total inner path will also be parallel-safe, but if not, we'll
1773  * have to search for the cheapest safe, unparameterized inner
1774  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
1775  * inner path.
1776  */
1777  if (cheapest_total_inner->parallel_safe)
1778  cheapest_safe_inner = cheapest_total_inner;
1779  else if (save_jointype != JOIN_UNIQUE_INNER)
1780  cheapest_safe_inner =
1782 
1783  if (cheapest_safe_inner != NULL)
1784  try_partial_hashjoin_path(root, joinrel,
1785  cheapest_partial_outer,
1786  cheapest_safe_inner,
1787  hashclauses, jointype, extra);
1788  }
1789  }
1790 }
1791 
1792 /*
1793  * select_mergejoin_clauses
1794  * Select mergejoin clauses that are usable for a particular join.
1795  * Returns a list of RestrictInfo nodes for those clauses.
1796  *
1797  * *mergejoin_allowed is normally set to TRUE, but it is set to FALSE if
1798  * this is a right/full join and there are nonmergejoinable join clauses.
1799  * The executor's mergejoin machinery cannot handle such cases, so we have
1800  * to avoid generating a mergejoin plan. (Note that this flag does NOT
1801  * consider whether there are actually any mergejoinable clauses. This is
1802  * correct because in some cases we need to build a clauseless mergejoin.
1803  * Simply returning NIL is therefore not enough to distinguish safe from
1804  * unsafe cases.)
1805  *
1806  * We also mark each selected RestrictInfo to show which side is currently
1807  * being considered as outer. These are transient markings that are only
1808  * good for the duration of the current add_paths_to_joinrel() call!
1809  *
1810  * We examine each restrictinfo clause known for the join to see
1811  * if it is mergejoinable and involves vars from the two sub-relations
1812  * currently of interest.
1813  */
1814 static List *
1816  RelOptInfo *joinrel,
1817  RelOptInfo *outerrel,
1818  RelOptInfo *innerrel,
1819  List *restrictlist,
1820  JoinType jointype,
1821  bool *mergejoin_allowed)
1822 {
1823  List *result_list = NIL;
1824  bool isouterjoin = IS_OUTER_JOIN(jointype);
1825  bool have_nonmergeable_joinclause = false;
1826  ListCell *l;
1827 
1828  foreach(l, restrictlist)
1829  {
1830  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1831 
1832  /*
1833  * If processing an outer join, only use its own join clauses in the
1834  * merge. For inner joins we can use pushed-down clauses too. (Note:
1835  * we don't set have_nonmergeable_joinclause here because pushed-down
1836  * clauses will become otherquals not joinquals.)
1837  */
1838  if (isouterjoin && restrictinfo->is_pushed_down)
1839  continue;
1840 
1841  /* Check that clause is a mergeable operator clause */
1842  if (!restrictinfo->can_join ||
1843  restrictinfo->mergeopfamilies == NIL)
1844  {
1845  /*
1846  * The executor can handle extra joinquals that are constants, but
1847  * not anything else, when doing right/full merge join. (The
1848  * reason to support constants is so we can do FULL JOIN ON
1849  * FALSE.)
1850  */
1851  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
1852  have_nonmergeable_joinclause = true;
1853  continue; /* not mergejoinable */
1854  }
1855 
1856  /*
1857  * Check if clause has the form "outer op inner" or "inner op outer".
1858  */
1859  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1860  {
1861  have_nonmergeable_joinclause = true;
1862  continue; /* no good for these input relations */
1863  }
1864 
1865  /*
1866  * Insist that each side have a non-redundant eclass. This
1867  * restriction is needed because various bits of the planner expect
1868  * that each clause in a merge be associable with some pathkey in a
1869  * canonical pathkey list, but redundant eclasses can't appear in
1870  * canonical sort orderings. (XXX it might be worth relaxing this,
1871  * but not enough time to address it for 8.3.)
1872  *
1873  * Note: it would be bad if this condition failed for an otherwise
1874  * mergejoinable FULL JOIN clause, since that would result in
1875  * undesirable planner failure. I believe that is not possible
1876  * however; a variable involved in a full join could only appear in
1877  * below_outer_join eclasses, which aren't considered redundant.
1878  *
1879  * This case *can* happen for left/right join clauses: the outer-side
1880  * variable could be equated to a constant. Because we will propagate
1881  * that constant across the join clause, the loss of ability to do a
1882  * mergejoin is not really all that big a deal, and so it's not clear
1883  * that improving this is important.
1884  */
1885  update_mergeclause_eclasses(root, restrictinfo);
1886 
1887  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
1888  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
1889  {
1890  have_nonmergeable_joinclause = true;
1891  continue; /* can't handle redundant eclasses */
1892  }
1893 
1894  result_list = lappend(result_list, restrictinfo);
1895  }
1896 
1897  /*
1898  * Report whether mergejoin is allowed (see comment at top of function).
1899  */
1900  switch (jointype)
1901  {
1902  case JOIN_RIGHT:
1903  case JOIN_FULL:
1904  *mergejoin_allowed = !have_nonmergeable_joinclause;
1905  break;
1906  default:
1907  *mergejoin_allowed = true;
1908  break;
1909  }
1910 
1911  return result_list;
1912 }
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:343
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:469
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:634
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
SemiAntiJoinFactors semifactors
Definition: relation.h:2240
List * join_info_list
Definition: relation.h:250
Relids min_righthand
Definition: relation.h:1974
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:338
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:876
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:647
struct Path * cheapest_startup_path
Definition: relation.h:588
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1388
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
static void try_partial_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:695
List * list_truncate(List *list, int new_size)
Definition: list.c:350
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:722
ParamPathInfo * param_info
Definition: relation.h:1011
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2920
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2029
List * list_copy(const List *oldlist)
Definition: list.c:1160
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1292
List * partial_pathlist
Definition: relation.h:587
Relids left_relids
Definition: relation.h:1828
EquivalenceClass * right_ec
Definition: relation.h:1850
List * cheapest_parameterized_paths
Definition: relation.h:591
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1427
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
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:2150
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:2369
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:822
List * mergeopfamilies
Definition: relation.h:1846
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1584
JoinType
Definition: nodes.h:673
NodeTag pathtype
Definition: relation.h:1006
void(* set_join_pathlist_hook_type)(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: paths.h:36
Relids lateral_relids
Definition: relation.h:596
SpecialJoinInfo * sjinfo
Definition: relation.h:2239
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:786
#define linitial(l)
Definition: pg_list.h:111
Relids all_baserels
Definition: relation.h:196
#define ERROR
Definition: elog.h:43
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:191
Relids param_source_rels
Definition: relation.h:2241
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
bool can_join
Definition: relation.h:1807
RelOptInfo * parent
Definition: relation.h:1008
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:61
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:2062
struct Path * cheapest_total_path
Definition: relation.h:589
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:415
bool outer_is_left
Definition: relation.h:1856
struct FdwRoutine * fdwroutine
Definition: relation.h:622
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:988
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
List * mergeclause_list
Definition: relation.h:2237
Relids relids
Definition: relation.h:571
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: relation.h:847
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:421
bool innerrel_is_unique(PlannerInfo *root, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:970
List * lappend(List *list, void *datum)
Definition: list.c:128
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1512
Expr * clause
Definition: relation.h:1801
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1815
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1472
List * restrictlist
Definition: relation.h:2236
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:27
#define InvalidOid
Definition: postgres_ext.h:36
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1120
bool is_pushed_down
Definition: relation.h:1803
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:29
List * lcons(void *datum, List *list)
Definition: list.c:259
List * pathkeys
Definition: relation.h:1022
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
bool enable_mergejoin
Definition: costsize.c:127
Relids right_relids
Definition: relation.h:1829
#define Assert(condition)
Definition: c.h:664
#define lfirst(lc)
Definition: pg_list.h:106
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:3780
bool parallel_safe
Definition: relation.h:1014
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:754
#define PATH_REQ_OUTER(path)
Definition: relation.h:1027
JoinType jointype
Definition: relation.h:1977
Oid hashjoinoperator
Definition: relation.h:1859
static int list_length(const List *l)
Definition: pg_list.h:89
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:1996
bool consider_parallel
Definition: relation.h:579
bool enable_hashjoin
Definition: costsize.c:128
List * find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, List *restrictinfos)
Definition: pathkeys.c:1003
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition: pathnode.c:2215
EquivalenceClass * left_ec
Definition: relation.h:1849
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:752
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:564
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinpath.c:107
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:577
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2087
List * pathlist
Definition: relation.h:585
Relids ppi_req_outer
Definition: relation.h:967
#define elog
Definition: elog.h:219
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:320
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:1973
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:968
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:755
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1152
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
bool enable_material
Definition: costsize.c:126
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1238