PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
joinpath.c File Reference
#include "postgres.h"
#include <math.h>
#include "executor/executor.h"
#include "foreign/fdwapi.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
Include dependency graph for joinpath.c:

Go to the source code of this file.

Macros

#define PATH_PARAM_BY_REL(path, rel)   ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
 

Functions

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)
 
static void sort_inner_and_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void match_unsorted_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void consider_parallel_nestloop (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void consider_parallel_mergejoin (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
 
static void hash_inner_and_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static Listselect_mergejoin_clauses (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
 
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)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
static bool allow_star_schema_join (PlannerInfo *root, Path *outer_path, Path *inner_path)
 
static void try_nestloop_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
 
static void try_partial_nestloop_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
 
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)
 
static void try_hashjoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
 
static void try_partial_hashjoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
 
static bool clause_sides_match_join (RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
 

Variables

set_join_pathlist_hook_type set_join_pathlist_hook = NULL
 

Macro Definition Documentation

#define PATH_PARAM_BY_REL (   path,
  rel 
)    ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))

Definition at line 29 of file joinpath.c.

Referenced by hash_inner_and_outer(), match_unsorted_outer(), and sort_inner_and_outer().

Function Documentation

void add_paths_to_joinrel ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
SpecialJoinInfo sjinfo,
List restrictlist 
)

Definition at line 107 of file joinpath.c.

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, NULL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, and sort_inner_and_outer().

Referenced by populate_joinrel_with_paths().

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 }
#define NIL
Definition: pg_list.h:69
SemiAntiJoinFactors semifactors
Definition: relation.h:2184
List * join_info_list
Definition: relation.h:250
Relids min_righthand
Definition: relation.h:1918
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1583
Relids lateral_relids
Definition: relation.h:550
SpecialJoinInfo * sjinfo
Definition: relation.h:2183
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:785
Relids all_baserels
Definition: relation.h:196
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:188
Relids param_source_rels
Definition: relation.h:2185
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
struct FdwRoutine * fdwroutine
Definition: relation.h:576
List * mergeclause_list
Definition: relation.h:2181
Relids relids
Definition: relation.h:525
bool innerrel_is_unique(PlannerInfo *root, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:962
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1814
List * restrictlist
Definition: relation.h:2180
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:27
bool enable_mergejoin
Definition: costsize.c:127
#define NULL
Definition: c.h:229
#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:3736
JoinType jointype
Definition: relation.h:1921
bool enable_hashjoin
Definition: costsize.c:128
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
Relids min_lefthand
Definition: relation.h:1917
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:755
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1237
static bool allow_star_schema_join ( PlannerInfo root,
Path outer_path,
Path inner_path 
)
inlinestatic

Definition at line 320 of file joinpath.c.

References bms_nonempty_difference(), bms_overlap(), Path::parent, PATH_REQ_OUTER, and RelOptInfo::relids.

Referenced by try_nestloop_path().

323 {
324  Relids innerparams = PATH_REQ_OUTER(inner_path);
325  Relids outerrelids = outer_path->parent->relids;
326 
327  /*
328  * It's a star-schema case if the outer rel provides some but not all of
329  * the inner rel's parameterization.
330  */
331  return (bms_overlap(innerparams, outerrelids) &&
332  bms_nonempty_difference(innerparams, outerrelids));
333 }
RelOptInfo * parent
Definition: relation.h:953
Relids relids
Definition: relation.h:525
#define PATH_REQ_OUTER(path)
Definition: relation.h:973
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
static bool clause_sides_match_join ( RestrictInfo rinfo,
RelOptInfo outerrel,
RelOptInfo innerrel 
)
inlinestatic

Definition at line 753 of file joinpath.c.

References bms_is_subset(), RestrictInfo::left_relids, RestrictInfo::outer_is_left, RelOptInfo::relids, and RestrictInfo::right_relids.

Referenced by hash_inner_and_outer(), and select_mergejoin_clauses().

755 {
756  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
757  bms_is_subset(rinfo->right_relids, innerrel->relids))
758  {
759  /* lefthand side is outer */
760  rinfo->outer_is_left = true;
761  return true;
762  }
763  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
764  bms_is_subset(rinfo->right_relids, outerrel->relids))
765  {
766  /* righthand side is outer */
767  rinfo->outer_is_left = false;
768  return true;
769  }
770  return false; /* no good for these input relations */
771 }
Relids left_relids
Definition: relation.h:1774
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
bool outer_is_left
Definition: relation.h:1802
Relids relids
Definition: relation.h:525
Relids right_relids
Definition: relation.h:1775
static void consider_parallel_mergejoin ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra,
Path inner_cheapest_total 
)
static

Definition at line 1471 of file joinpath.c.

References build_join_pathkeys(), generate_mergejoin_paths(), lfirst, RelOptInfo::partial_pathlist, and Path::pathkeys.

Referenced by match_unsorted_outer().

1478 {
1479  ListCell *lc1;
1480 
1481  /* generate merge join path for each partial outer path */
1482  foreach(lc1, outerrel->partial_pathlist)
1483  {
1484  Path *outerpath = (Path *) lfirst(lc1);
1485  List *merge_pathkeys;
1486 
1487  /*
1488  * Figure out what useful ordering any paths we create will have.
1489  */
1490  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1491  outerpath->pathkeys);
1492 
1493  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1494  extra, false, inner_cheapest_total,
1495  merge_pathkeys, true);
1496  }
1497 }
List * partial_pathlist
Definition: relation.h:541
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:822
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:987
List * pathkeys
Definition: relation.h:968
#define lfirst(lc)
Definition: pg_list.h:106
Definition: pg_list.h:45
Definition: relation.h:947
static void consider_parallel_nestloop ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1511 of file joinpath.c.

References Assert, build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, create_unique_path(), JOIN_INNER, JOIN_UNIQUE_INNER, lfirst, Path::parallel_safe, RelOptInfo::partial_pathlist, Path::pathkeys, JoinPathExtraData::sjinfo, and try_partial_nestloop_path().

Referenced by match_unsorted_outer().

1517 {
1518  JoinType save_jointype = jointype;
1519  ListCell *lc1;
1520 
1521  if (jointype == JOIN_UNIQUE_INNER)
1522  jointype = JOIN_INNER;
1523 
1524  foreach(lc1, outerrel->partial_pathlist)
1525  {
1526  Path *outerpath = (Path *) lfirst(lc1);
1527  List *pathkeys;
1528  ListCell *lc2;
1529 
1530  /* Figure out what useful ordering any paths we create will have. */
1531  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1532  outerpath->pathkeys);
1533 
1534  /*
1535  * Try the cheapest parameterized paths; only those which will produce
1536  * an unparameterized path when joined to this outerrel will survive
1537  * try_partial_nestloop_path. The cheapest unparameterized path is
1538  * also in this list.
1539  */
1540  foreach(lc2, innerrel->cheapest_parameterized_paths)
1541  {
1542  Path *innerpath = (Path *) lfirst(lc2);
1543 
1544  /* Can't join to an inner path that is not parallel-safe */
1545  if (!innerpath->parallel_safe)
1546  continue;
1547 
1548  /*
1549  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1550  * cheapest_total_path, and we have to unique-ify it. (We might
1551  * be able to relax this to allow other safe, unparameterized
1552  * inner paths, but right now create_unique_path is not on board
1553  * with that.)
1554  */
1555  if (save_jointype == JOIN_UNIQUE_INNER)
1556  {
1557  if (innerpath != innerrel->cheapest_total_path)
1558  continue;
1559  innerpath = (Path *) create_unique_path(root, innerrel,
1560  innerpath,
1561  extra->sjinfo);
1562  Assert(innerpath);
1563  }
1564 
1565  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1566  pathkeys, jointype, extra);
1567  }
1568  }
1569 }
List * partial_pathlist
Definition: relation.h:541
List * cheapest_parameterized_paths
Definition: relation.h:545
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1428
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:822
JoinType
Definition: nodes.h:672
SpecialJoinInfo * sjinfo
Definition: relation.h:2183
struct Path * cheapest_total_path
Definition: relation.h:543
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:414
List * pathkeys
Definition: relation.h:968
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:959
Definition: pg_list.h:45
Definition: relation.h:947
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 
)
static

Definition at line 987 of file joinpath.c.

References Assert, compare_path_costs(), find_mergeclauses_for_pathkeys(), get_cheapest_path_for_pathkeys(), JOIN_FULL, JOIN_INNER, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, list_copy(), list_length(), list_truncate(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, NULL, Path::pathkeys, pathkeys_contained_in(), RelOptInfo::pathlist, STARTUP_COST, TOTAL_COST, and try_mergejoin_path().

Referenced by consider_parallel_mergejoin(), and match_unsorted_outer().

997 {
998  List *mergeclauses;
999  List *innersortkeys;
1000  List *trialsortkeys;
1001  Path *cheapest_startup_inner;
1002  Path *cheapest_total_inner;
1003  JoinType save_jointype = jointype;
1004  int num_sortkeys;
1005  int sortkeycnt;
1006 
1007  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1008  jointype = JOIN_INNER;
1009 
1010  /* Look for useful mergeclauses (if any) */
1011  mergeclauses = find_mergeclauses_for_pathkeys(root,
1012  outerpath->pathkeys,
1013  true,
1014  extra->mergeclause_list);
1015 
1016  /*
1017  * Done with this outer path if no chance for a mergejoin.
1018  *
1019  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1020  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1021  * but since mergejoin is our only join type that supports FULL JOIN
1022  * without any join clauses, it's necessary to generate a clauseless
1023  * mergejoin path instead.
1024  */
1025  if (mergeclauses == NIL)
1026  {
1027  if (jointype == JOIN_FULL)
1028  /* okay to try for mergejoin */ ;
1029  else
1030  return;
1031  }
1032  if (useallclauses &&
1033  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1034  return;
1035 
1036  /* Compute the required ordering of the inner path */
1037  innersortkeys = make_inner_pathkeys_for_merge(root,
1038  mergeclauses,
1039  outerpath->pathkeys);
1040 
1041  /*
1042  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1043  * a sort will be needed, only cheapest total cost matters. (But
1044  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1045  * already correctly sorted.)
1046  */
1047  try_mergejoin_path(root,
1048  joinrel,
1049  outerpath,
1050  inner_cheapest_total,
1051  merge_pathkeys,
1052  mergeclauses,
1053  NIL,
1054  innersortkeys,
1055  jointype,
1056  extra,
1057  is_partial);
1058 
1059  /* Can't do anything else if inner path needs to be unique'd */
1060  if (save_jointype == JOIN_UNIQUE_INNER)
1061  return;
1062 
1063  /*
1064  * Look for presorted inner paths that satisfy the innersortkey list ---
1065  * or any truncation thereof, if we are allowed to build a mergejoin using
1066  * a subset of the merge clauses. Here, we consider both cheap startup
1067  * cost and cheap total cost.
1068  *
1069  * Currently we do not consider parameterized inner paths here. This
1070  * interacts with decisions elsewhere that also discriminate against
1071  * mergejoins with parameterized inputs; see comments in
1072  * src/backend/optimizer/README.
1073  *
1074  * As we shorten the sortkey list, we should consider only paths that are
1075  * strictly cheaper than (in particular, not the same as) any path found
1076  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1077  * merge keys than a given path allows (treating the rest as plain
1078  * joinquals), which is unlikely to be a good idea. Also, eliminating
1079  * paths here on the basis of compare_path_costs is a lot cheaper than
1080  * building the mergejoin path only to throw it away.
1081  *
1082  * If inner_cheapest_total is well enough sorted to have not required a
1083  * sort in the path made above, we shouldn't make a duplicate path with
1084  * it, either. We handle that case with the same logic that handles the
1085  * previous consideration, by initializing the variables that track
1086  * cheapest-so-far properly. Note that we do NOT reject
1087  * inner_cheapest_total if we find it matches some shorter set of
1088  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1089  * sorting inner_cheapest_total, whereas we did sort it above, so the
1090  * plans being considered are different.
1091  */
1092  if (pathkeys_contained_in(innersortkeys,
1093  inner_cheapest_total->pathkeys))
1094  {
1095  /* inner_cheapest_total didn't require a sort */
1096  cheapest_startup_inner = inner_cheapest_total;
1097  cheapest_total_inner = inner_cheapest_total;
1098  }
1099  else
1100  {
1101  /* it did require a sort, at least for the full set of keys */
1102  cheapest_startup_inner = NULL;
1103  cheapest_total_inner = NULL;
1104  }
1105  num_sortkeys = list_length(innersortkeys);
1106  if (num_sortkeys > 1 && !useallclauses)
1107  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1108  else
1109  trialsortkeys = innersortkeys; /* won't really truncate */
1110 
1111  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1112  {
1113  Path *innerpath;
1114  List *newclauses = NIL;
1115 
1116  /*
1117  * Look for an inner path ordered well enough for the first
1118  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1119  * destructively, which is why we made a copy...
1120  */
1121  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1122  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1123  trialsortkeys,
1124  NULL,
1125  TOTAL_COST,
1126  is_partial);
1127  if (innerpath != NULL &&
1128  (cheapest_total_inner == NULL ||
1129  compare_path_costs(innerpath, cheapest_total_inner,
1130  TOTAL_COST) < 0))
1131  {
1132  /* Found a cheap (or even-cheaper) sorted path */
1133  /* Select the right mergeclauses, if we didn't already */
1134  if (sortkeycnt < num_sortkeys)
1135  {
1136  newclauses =
1138  trialsortkeys,
1139  false,
1140  mergeclauses);
1141  Assert(newclauses != NIL);
1142  }
1143  else
1144  newclauses = mergeclauses;
1145  try_mergejoin_path(root,
1146  joinrel,
1147  outerpath,
1148  innerpath,
1149  merge_pathkeys,
1150  newclauses,
1151  NIL,
1152  NIL,
1153  jointype,
1154  extra,
1155  is_partial);
1156  cheapest_total_inner = innerpath;
1157  }
1158  /* Same on the basis of cheapest startup cost ... */
1159  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1160  trialsortkeys,
1161  NULL,
1162  STARTUP_COST,
1163  is_partial);
1164  if (innerpath != NULL &&
1165  (cheapest_startup_inner == NULL ||
1166  compare_path_costs(innerpath, cheapest_startup_inner,
1167  STARTUP_COST) < 0))
1168  {
1169  /* Found a cheap (or even-cheaper) sorted path */
1170  if (innerpath != cheapest_total_inner)
1171  {
1172  /*
1173  * Avoid rebuilding clause list if we already made one; saves
1174  * memory in big join trees...
1175  */
1176  if (newclauses == NIL)
1177  {
1178  if (sortkeycnt < num_sortkeys)
1179  {
1180  newclauses =
1182  trialsortkeys,
1183  false,
1184  mergeclauses);
1185  Assert(newclauses != NIL);
1186  }
1187  else
1188  newclauses = mergeclauses;
1189  }
1190  try_mergejoin_path(root,
1191  joinrel,
1192  outerpath,
1193  innerpath,
1194  merge_pathkeys,
1195  newclauses,
1196  NIL,
1197  NIL,
1198  jointype,
1199  extra,
1200  is_partial);
1201  }
1202  cheapest_startup_inner = innerpath;
1203  }
1204 
1205  /*
1206  * Don't consider truncated sortkeys if we need all clauses.
1207  */
1208  if (useallclauses)
1209  break;
1210  }
1211 }
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:468
#define NIL
Definition: pg_list.h:69
List * list_truncate(List *list, int new_size)
Definition: list.c:350
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
JoinType
Definition: nodes.h:672
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:61
List * mergeclause_list
Definition: relation.h:2181
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * pathkeys
Definition: relation.h:968
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
static int list_length(const List *l)
Definition: pg_list.h:89
List * find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, List *restrictinfos)
Definition: pathkeys.c:1003
List * pathlist
Definition: relation.h:539
Definition: pg_list.h:45
Definition: relation.h:947
static void hash_inner_and_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1583 of file joinpath.c.

References Assert, bms_is_empty(), RestrictInfo::can_join, RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, clause_sides_match_join(), RelOptInfo::consider_parallel, create_unique_path(), get_cheapest_parallel_safe_total_inner(), RestrictInfo::hashjoinoperator, InvalidOid, IS_OUTER_JOIN, RestrictInfo::is_pushed_down, JOIN_FULL, JOIN_INNER, JOIN_RIGHT, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, lappend(), RelOptInfo::lateral_relids, lfirst, linitial, NIL, NULL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, JoinPathExtraData::restrictlist, JoinPathExtraData::sjinfo, try_hashjoin_path(), and try_partial_hashjoin_path().

Referenced by add_paths_to_joinrel().

1589 {
1590  JoinType save_jointype = jointype;
1591  bool isouterjoin = IS_OUTER_JOIN(jointype);
1592  List *hashclauses;
1593  ListCell *l;
1594 
1595  /*
1596  * We need to build only one hashclauses list for any given pair of outer
1597  * and inner relations; all of the hashable clauses will be used as keys.
1598  *
1599  * Scan the join's restrictinfo list to find hashjoinable clauses that are
1600  * usable with this pair of sub-relations.
1601  */
1602  hashclauses = NIL;
1603  foreach(l, extra->restrictlist)
1604  {
1605  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1606 
1607  /*
1608  * If processing an outer join, only use its own join clauses for
1609  * hashing. For inner joins we need not be so picky.
1610  */
1611  if (isouterjoin && restrictinfo->is_pushed_down)
1612  continue;
1613 
1614  if (!restrictinfo->can_join ||
1615  restrictinfo->hashjoinoperator == InvalidOid)
1616  continue; /* not hashjoinable */
1617 
1618  /*
1619  * Check if clause has the form "outer op inner" or "inner op outer".
1620  */
1621  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1622  continue; /* no good for these input relations */
1623 
1624  hashclauses = lappend(hashclauses, restrictinfo);
1625  }
1626 
1627  /* If we found any usable hashclauses, make paths */
1628  if (hashclauses)
1629  {
1630  /*
1631  * We consider both the cheapest-total-cost and cheapest-startup-cost
1632  * outer paths. There's no need to consider any but the
1633  * cheapest-total-cost inner path, however.
1634  */
1635  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
1636  Path *cheapest_total_outer = outerrel->cheapest_total_path;
1637  Path *cheapest_total_inner = innerrel->cheapest_total_path;
1638 
1639  /*
1640  * If either cheapest-total path is parameterized by the other rel, we
1641  * can't use a hashjoin. (There's no use looking for alternative
1642  * input paths, since these should already be the least-parameterized
1643  * available paths.)
1644  */
1645  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
1646  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
1647  return;
1648 
1649  /* Unique-ify if need be; we ignore parameterized possibilities */
1650  if (jointype == JOIN_UNIQUE_OUTER)
1651  {
1652  cheapest_total_outer = (Path *)
1653  create_unique_path(root, outerrel,
1654  cheapest_total_outer, extra->sjinfo);
1655  Assert(cheapest_total_outer);
1656  jointype = JOIN_INNER;
1657  try_hashjoin_path(root,
1658  joinrel,
1659  cheapest_total_outer,
1660  cheapest_total_inner,
1661  hashclauses,
1662  jointype,
1663  extra);
1664  /* no possibility of cheap startup here */
1665  }
1666  else if (jointype == JOIN_UNIQUE_INNER)
1667  {
1668  cheapest_total_inner = (Path *)
1669  create_unique_path(root, innerrel,
1670  cheapest_total_inner, extra->sjinfo);
1671  Assert(cheapest_total_inner);
1672  jointype = JOIN_INNER;
1673  try_hashjoin_path(root,
1674  joinrel,
1675  cheapest_total_outer,
1676  cheapest_total_inner,
1677  hashclauses,
1678  jointype,
1679  extra);
1680  if (cheapest_startup_outer != NULL &&
1681  cheapest_startup_outer != cheapest_total_outer)
1682  try_hashjoin_path(root,
1683  joinrel,
1684  cheapest_startup_outer,
1685  cheapest_total_inner,
1686  hashclauses,
1687  jointype,
1688  extra);
1689  }
1690  else
1691  {
1692  /*
1693  * For other jointypes, we consider the cheapest startup outer
1694  * together with the cheapest total inner, and then consider
1695  * pairings of cheapest-total paths including parameterized ones.
1696  * There is no use in generating parameterized paths on the basis
1697  * of possibly cheap startup cost, so this is sufficient.
1698  */
1699  ListCell *lc1;
1700  ListCell *lc2;
1701 
1702  if (cheapest_startup_outer != NULL)
1703  try_hashjoin_path(root,
1704  joinrel,
1705  cheapest_startup_outer,
1706  cheapest_total_inner,
1707  hashclauses,
1708  jointype,
1709  extra);
1710 
1711  foreach(lc1, outerrel->cheapest_parameterized_paths)
1712  {
1713  Path *outerpath = (Path *) lfirst(lc1);
1714 
1715  /*
1716  * We cannot use an outer path that is parameterized by the
1717  * inner rel.
1718  */
1719  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1720  continue;
1721 
1722  foreach(lc2, innerrel->cheapest_parameterized_paths)
1723  {
1724  Path *innerpath = (Path *) lfirst(lc2);
1725 
1726  /*
1727  * We cannot use an inner path that is parameterized by
1728  * the outer rel, either.
1729  */
1730  if (PATH_PARAM_BY_REL(innerpath, outerrel))
1731  continue;
1732 
1733  if (outerpath == cheapest_startup_outer &&
1734  innerpath == cheapest_total_inner)
1735  continue; /* already tried it */
1736 
1737  try_hashjoin_path(root,
1738  joinrel,
1739  outerpath,
1740  innerpath,
1741  hashclauses,
1742  jointype,
1743  extra);
1744  }
1745  }
1746  }
1747 
1748  /*
1749  * If the joinrel is parallel-safe, we may be able to consider a
1750  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
1751  * because the outer path will be partial, and therefore we won't be
1752  * able to properly guarantee uniqueness. Similarly, we can't handle
1753  * JOIN_FULL and JOIN_RIGHT, because they can produce false null
1754  * extended rows. Also, the resulting path must not be parameterized.
1755  */
1756  if (joinrel->consider_parallel &&
1757  save_jointype != JOIN_UNIQUE_OUTER &&
1758  save_jointype != JOIN_FULL &&
1759  save_jointype != JOIN_RIGHT &&
1760  outerrel->partial_pathlist != NIL &&
1761  bms_is_empty(joinrel->lateral_relids))
1762  {
1763  Path *cheapest_partial_outer;
1764  Path *cheapest_safe_inner = NULL;
1765 
1766  cheapest_partial_outer =
1767  (Path *) linitial(outerrel->partial_pathlist);
1768 
1769  /*
1770  * Normally, given that the joinrel is parallel-safe, the cheapest
1771  * total inner path will also be parallel-safe, but if not, we'll
1772  * have to search for the cheapest safe, unparameterized inner
1773  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
1774  * inner path.
1775  */
1776  if (cheapest_total_inner->parallel_safe)
1777  cheapest_safe_inner = cheapest_total_inner;
1778  else if (save_jointype != JOIN_UNIQUE_INNER)
1779  cheapest_safe_inner =
1781 
1782  if (cheapest_safe_inner != NULL)
1783  try_partial_hashjoin_path(root, joinrel,
1784  cheapest_partial_outer,
1785  cheapest_safe_inner,
1786  hashclauses, jointype, extra);
1787  }
1788  }
1789 }
#define NIL
Definition: pg_list.h:69
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:633
struct Path * cheapest_startup_path
Definition: relation.h:542
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:694
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:721
List * partial_pathlist
Definition: relation.h:541
List * cheapest_parameterized_paths
Definition: relation.h:545
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1428
JoinType
Definition: nodes.h:672
Relids lateral_relids
Definition: relation.h:550
SpecialJoinInfo * sjinfo
Definition: relation.h:2183
#define linitial(l)
Definition: pg_list.h:111
bool can_join
Definition: relation.h:1753
struct Path * cheapest_total_path
Definition: relation.h:543
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:421
List * lappend(List *list, void *datum)
Definition: list.c:128
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * restrictlist
Definition: relation.h:2180
#define InvalidOid
Definition: postgres_ext.h:36
bool is_pushed_down
Definition: relation.h:1749
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:29
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:959
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:753
Oid hashjoinoperator
Definition: relation.h:1805
bool consider_parallel
Definition: relation.h:533
List * pathlist
Definition: relation.h:539
Definition: pg_list.h:45
Definition: relation.h:947
static void match_unsorted_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1237 of file joinpath.c.

References Assert, bms_is_empty(), build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, consider_parallel_mergejoin(), consider_parallel_nestloop(), create_material_path(), create_unique_path(), elog, enable_material, ERROR, ExecMaterializesOutput(), generate_mergejoin_paths(), get_cheapest_parallel_safe_total_inner(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_LEFT, JOIN_RIGHT, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lfirst, NIL, NULL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, JoinPathExtraData::sjinfo, and try_nestloop_path().

Referenced by add_paths_to_joinrel().

1243 {
1244  JoinType save_jointype = jointype;
1245  bool nestjoinOK;
1246  bool useallclauses;
1247  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1248  Path *matpath = NULL;
1249  ListCell *lc1;
1250 
1251  /*
1252  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1253  * are doing a right or full mergejoin, we must use *all* the mergeclauses
1254  * as join clauses, else we will not have a valid plan. (Although these
1255  * two flags are currently inverses, keep them separate for clarity and
1256  * possible future changes.)
1257  */
1258  switch (jointype)
1259  {
1260  case JOIN_INNER:
1261  case JOIN_LEFT:
1262  case JOIN_SEMI:
1263  case JOIN_ANTI:
1264  nestjoinOK = true;
1265  useallclauses = false;
1266  break;
1267  case JOIN_RIGHT:
1268  case JOIN_FULL:
1269  nestjoinOK = false;
1270  useallclauses = true;
1271  break;
1272  case JOIN_UNIQUE_OUTER:
1273  case JOIN_UNIQUE_INNER:
1274  jointype = JOIN_INNER;
1275  nestjoinOK = true;
1276  useallclauses = false;
1277  break;
1278  default:
1279  elog(ERROR, "unrecognized join type: %d",
1280  (int) jointype);
1281  nestjoinOK = false; /* keep compiler quiet */
1282  useallclauses = false;
1283  break;
1284  }
1285 
1286  /*
1287  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1288  * we will consider it below as a member of cheapest_parameterized_paths,
1289  * but the other possibilities considered in this routine aren't usable.
1290  */
1291  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1292  inner_cheapest_total = NULL;
1293 
1294  /*
1295  * If we need to unique-ify the inner path, we will consider only the
1296  * cheapest-total inner.
1297  */
1298  if (save_jointype == JOIN_UNIQUE_INNER)
1299  {
1300  /* No way to do this with an inner path parameterized by outer rel */
1301  if (inner_cheapest_total == NULL)
1302  return;
1303  inner_cheapest_total = (Path *)
1304  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1305  Assert(inner_cheapest_total);
1306  }
1307  else if (nestjoinOK)
1308  {
1309  /*
1310  * Consider materializing the cheapest inner path, unless
1311  * enable_material is off or the path in question materializes its
1312  * output anyway.
1313  */
1314  if (enable_material && inner_cheapest_total != NULL &&
1315  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1316  matpath = (Path *)
1317  create_material_path(innerrel, inner_cheapest_total);
1318  }
1319 
1320  foreach(lc1, outerrel->pathlist)
1321  {
1322  Path *outerpath = (Path *) lfirst(lc1);
1323  List *merge_pathkeys;
1324 
1325  /*
1326  * We cannot use an outer path that is parameterized by the inner rel.
1327  */
1328  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1329  continue;
1330 
1331  /*
1332  * If we need to unique-ify the outer path, it's pointless to consider
1333  * any but the cheapest outer. (XXX we don't consider parameterized
1334  * outers, nor inners, for unique-ified cases. Should we?)
1335  */
1336  if (save_jointype == JOIN_UNIQUE_OUTER)
1337  {
1338  if (outerpath != outerrel->cheapest_total_path)
1339  continue;
1340  outerpath = (Path *) create_unique_path(root, outerrel,
1341  outerpath, extra->sjinfo);
1342  Assert(outerpath);
1343  }
1344 
1345  /*
1346  * The result will have this sort order (even if it is implemented as
1347  * a nestloop, and even if some of the mergeclauses are implemented by
1348  * qpquals rather than as true mergeclauses):
1349  */
1350  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1351  outerpath->pathkeys);
1352 
1353  if (save_jointype == JOIN_UNIQUE_INNER)
1354  {
1355  /*
1356  * Consider nestloop join, but only with the unique-ified cheapest
1357  * inner path
1358  */
1359  try_nestloop_path(root,
1360  joinrel,
1361  outerpath,
1362  inner_cheapest_total,
1363  merge_pathkeys,
1364  jointype,
1365  extra);
1366  }
1367  else if (nestjoinOK)
1368  {
1369  /*
1370  * Consider nestloop joins using this outer path and various
1371  * available paths for the inner relation. We consider the
1372  * cheapest-total paths for each available parameterization of the
1373  * inner relation, including the unparameterized case.
1374  */
1375  ListCell *lc2;
1376 
1377  foreach(lc2, innerrel->cheapest_parameterized_paths)
1378  {
1379  Path *innerpath = (Path *) lfirst(lc2);
1380 
1381  try_nestloop_path(root,
1382  joinrel,
1383  outerpath,
1384  innerpath,
1385  merge_pathkeys,
1386  jointype,
1387  extra);
1388  }
1389 
1390  /* Also consider materialized form of the cheapest inner path */
1391  if (matpath != NULL)
1392  try_nestloop_path(root,
1393  joinrel,
1394  outerpath,
1395  matpath,
1396  merge_pathkeys,
1397  jointype,
1398  extra);
1399  }
1400 
1401  /* Can't do anything else if outer path needs to be unique'd */
1402  if (save_jointype == JOIN_UNIQUE_OUTER)
1403  continue;
1404 
1405  /* Can't do anything else if inner rel is parameterized by outer */
1406  if (inner_cheapest_total == NULL)
1407  continue;
1408 
1409  /* Generate merge join paths */
1410  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1411  save_jointype, extra, useallclauses,
1412  inner_cheapest_total, merge_pathkeys,
1413  false);
1414  }
1415 
1416  /*
1417  * Consider partial nestloop and mergejoin plan if outerrel has any
1418  * partial path and the joinrel is parallel-safe. However, we can't
1419  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1420  * therefore we won't be able to properly guarantee uniqueness. Nor can
1421  * we handle extra_lateral_rels, since partial paths must not be
1422  * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1423  * because they can produce false null extended rows.
1424  */
1425  if (joinrel->consider_parallel &&
1426  save_jointype != JOIN_UNIQUE_OUTER &&
1427  save_jointype != JOIN_FULL &&
1428  save_jointype != JOIN_RIGHT &&
1429  outerrel->partial_pathlist != NIL &&
1430  bms_is_empty(joinrel->lateral_relids))
1431  {
1432  if (nestjoinOK)
1433  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1434  save_jointype, extra);
1435 
1436  /*
1437  * If inner_cheapest_total is NULL or non parallel-safe then find the
1438  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1439  * can't use any alternative inner path.
1440  */
1441  if (inner_cheapest_total == NULL ||
1442  !inner_cheapest_total->parallel_safe)
1443  {
1444  if (save_jointype == JOIN_UNIQUE_INNER)
1445  return;
1446 
1447  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(
1448  innerrel->pathlist);
1449  }
1450 
1451  if (inner_cheapest_total)
1452  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1453  save_jointype, extra,
1454  inner_cheapest_total);
1455  }
1456 }
#define NIL
Definition: pg_list.h:69
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:341
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1389
List * partial_pathlist
Definition: relation.h:541
List * cheapest_parameterized_paths
Definition: relation.h:545
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1428
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:822
JoinType
Definition: nodes.h:672
NodeTag pathtype
Definition: relation.h:951
Relids lateral_relids
Definition: relation.h:550
SpecialJoinInfo * sjinfo
Definition: relation.h:2183
#define ERROR
Definition: elog.h:43
struct Path * cheapest_total_path
Definition: relation.h:543
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:987
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:421
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1511
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1471
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:29
List * pathkeys
Definition: relation.h:968
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:959
bool consider_parallel
Definition: relation.h:533
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:572
List * pathlist
Definition: relation.h:539
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
Definition: relation.h:947
bool enable_material
Definition: costsize.c:126
static List * select_mergejoin_clauses ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
List restrictlist,
JoinType  jointype,
bool mergejoin_allowed 
)
static

Definition at line 1814 of file joinpath.c.

References RestrictInfo::can_join, RestrictInfo::clause, clause_sides_match_join(), EC_MUST_BE_REDUNDANT, IS_OUTER_JOIN, RestrictInfo::is_pushed_down, IsA, JOIN_FULL, JOIN_RIGHT, lappend(), RestrictInfo::left_ec, lfirst, RestrictInfo::mergeopfamilies, NIL, RestrictInfo::right_ec, and update_mergeclause_eclasses().

Referenced by add_paths_to_joinrel().

1821 {
1822  List *result_list = NIL;
1823  bool isouterjoin = IS_OUTER_JOIN(jointype);
1824  bool have_nonmergeable_joinclause = false;
1825  ListCell *l;
1826 
1827  foreach(l, restrictlist)
1828  {
1829  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1830 
1831  /*
1832  * If processing an outer join, only use its own join clauses in the
1833  * merge. For inner joins we can use pushed-down clauses too. (Note:
1834  * we don't set have_nonmergeable_joinclause here because pushed-down
1835  * clauses will become otherquals not joinquals.)
1836  */
1837  if (isouterjoin && restrictinfo->is_pushed_down)
1838  continue;
1839 
1840  /* Check that clause is a mergeable operator clause */
1841  if (!restrictinfo->can_join ||
1842  restrictinfo->mergeopfamilies == NIL)
1843  {
1844  /*
1845  * The executor can handle extra joinquals that are constants, but
1846  * not anything else, when doing right/full merge join. (The
1847  * reason to support constants is so we can do FULL JOIN ON
1848  * FALSE.)
1849  */
1850  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
1851  have_nonmergeable_joinclause = true;
1852  continue; /* not mergejoinable */
1853  }
1854 
1855  /*
1856  * Check if clause has the form "outer op inner" or "inner op outer".
1857  */
1858  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1859  {
1860  have_nonmergeable_joinclause = true;
1861  continue; /* no good for these input relations */
1862  }
1863 
1864  /*
1865  * Insist that each side have a non-redundant eclass. This
1866  * restriction is needed because various bits of the planner expect
1867  * that each clause in a merge be associable with some pathkey in a
1868  * canonical pathkey list, but redundant eclasses can't appear in
1869  * canonical sort orderings. (XXX it might be worth relaxing this,
1870  * but not enough time to address it for 8.3.)
1871  *
1872  * Note: it would be bad if this condition failed for an otherwise
1873  * mergejoinable FULL JOIN clause, since that would result in
1874  * undesirable planner failure. I believe that is not possible
1875  * however; a variable involved in a full join could only appear in
1876  * below_outer_join eclasses, which aren't considered redundant.
1877  *
1878  * This case *can* happen for left/right join clauses: the outer-side
1879  * variable could be equated to a constant. Because we will propagate
1880  * that constant across the join clause, the loss of ability to do a
1881  * mergejoin is not really all that big a deal, and so it's not clear
1882  * that improving this is important.
1883  */
1884  update_mergeclause_eclasses(root, restrictinfo);
1885 
1886  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
1887  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
1888  {
1889  have_nonmergeable_joinclause = true;
1890  continue; /* can't handle redundant eclasses */
1891  }
1892 
1893  result_list = lappend(result_list, restrictinfo);
1894  }
1895 
1896  /*
1897  * Report whether mergejoin is allowed (see comment at top of function).
1898  */
1899  switch (jointype)
1900  {
1901  case JOIN_RIGHT:
1902  case JOIN_FULL:
1903  *mergejoin_allowed = !have_nonmergeable_joinclause;
1904  break;
1905  default:
1906  *mergejoin_allowed = true;
1907  break;
1908  }
1909 
1910  return result_list;
1911 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:721
EquivalenceClass * right_ec
Definition: relation.h:1796
List * mergeopfamilies
Definition: relation.h:1792
bool can_join
Definition: relation.h:1753
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: relation.h:792
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1747
bool is_pushed_down
Definition: relation.h:1749
#define lfirst(lc)
Definition: pg_list.h:106
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:753
EquivalenceClass * left_ec
Definition: relation.h:1795
Definition: pg_list.h:45
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:968
static void sort_inner_and_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 785 of file joinpath.c.

References Assert, bms_is_empty(), build_join_pathkeys(), RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, create_unique_path(), find_mergeclauses_for_pathkeys(), get_cheapest_parallel_safe_total_inner(), JOIN_FULL, JOIN_INNER, JOIN_RIGHT, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lcons(), lfirst, linitial, list_copy(), list_delete_ptr(), list_head(), list_length(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, NULL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, select_outer_pathkeys_for_merge(), JoinPathExtraData::sjinfo, try_mergejoin_path(), and try_partial_mergejoin_path().

Referenced by add_paths_to_joinrel().

791 {
792  JoinType save_jointype = jointype;
793  Path *outer_path;
794  Path *inner_path;
795  Path *cheapest_partial_outer = NULL;
796  Path *cheapest_safe_inner = NULL;
797  List *all_pathkeys;
798  ListCell *l;
799 
800  /*
801  * We only consider the cheapest-total-cost input paths, since we are
802  * assuming here that a sort is required. We will consider
803  * cheapest-startup-cost input paths later, and only if they don't need a
804  * sort.
805  *
806  * This function intentionally does not consider parameterized input
807  * paths, except when the cheapest-total is parameterized. If we did so,
808  * we'd have a combinatorial explosion of mergejoin paths of dubious
809  * value. This interacts with decisions elsewhere that also discriminate
810  * against mergejoins with parameterized inputs; see comments in
811  * src/backend/optimizer/README.
812  */
813  outer_path = outerrel->cheapest_total_path;
814  inner_path = innerrel->cheapest_total_path;
815 
816  /*
817  * If either cheapest-total path is parameterized by the other rel, we
818  * can't use a mergejoin. (There's no use looking for alternative input
819  * paths, since these should already be the least-parameterized available
820  * paths.)
821  */
822  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
823  PATH_PARAM_BY_REL(inner_path, outerrel))
824  return;
825 
826  /*
827  * If unique-ification is requested, do it and then handle as a plain
828  * inner join.
829  */
830  if (jointype == JOIN_UNIQUE_OUTER)
831  {
832  outer_path = (Path *) create_unique_path(root, outerrel,
833  outer_path, extra->sjinfo);
834  Assert(outer_path);
835  jointype = JOIN_INNER;
836  }
837  else if (jointype == JOIN_UNIQUE_INNER)
838  {
839  inner_path = (Path *) create_unique_path(root, innerrel,
840  inner_path, extra->sjinfo);
841  Assert(inner_path);
842  jointype = JOIN_INNER;
843  }
844 
845  /*
846  * If the joinrel is parallel-safe, we may be able to consider a partial
847  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
848  * outer path will be partial, and therefore we won't be able to properly
849  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
850  * JOIN_RIGHT, because they can produce false null extended rows. Also,
851  * the resulting path must not be parameterized.
852  */
853  if (joinrel->consider_parallel &&
854  save_jointype != JOIN_UNIQUE_OUTER &&
855  save_jointype != JOIN_FULL &&
856  save_jointype != JOIN_RIGHT &&
857  outerrel->partial_pathlist != NIL &&
858  bms_is_empty(joinrel->lateral_relids))
859  {
860  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
861 
862  if (inner_path->parallel_safe)
863  cheapest_safe_inner = inner_path;
864  else if (save_jointype != JOIN_UNIQUE_INNER)
865  cheapest_safe_inner =
867  }
868 
869  /*
870  * Each possible ordering of the available mergejoin clauses will generate
871  * a differently-sorted result path at essentially the same cost. We have
872  * no basis for choosing one over another at this level of joining, but
873  * some sort orders may be more useful than others for higher-level
874  * mergejoins, so it's worth considering multiple orderings.
875  *
876  * Actually, it's not quite true that every mergeclause ordering will
877  * generate a different path order, because some of the clauses may be
878  * partially redundant (refer to the same EquivalenceClasses). Therefore,
879  * what we do is convert the mergeclause list to a list of canonical
880  * pathkeys, and then consider different orderings of the pathkeys.
881  *
882  * Generating a path for *every* permutation of the pathkeys doesn't seem
883  * like a winning strategy; the cost in planning time is too high. For
884  * now, we generate one path for each pathkey, listing that pathkey first
885  * and the rest in random order. This should allow at least a one-clause
886  * mergejoin without re-sorting against any other possible mergejoin
887  * partner path. But if we've not guessed the right ordering of secondary
888  * keys, we may end up evaluating clauses as qpquals when they could have
889  * been done as mergeclauses. (In practice, it's rare that there's more
890  * than two or three mergeclauses, so expending a huge amount of thought
891  * on that is probably not worth it.)
892  *
893  * The pathkey order returned by select_outer_pathkeys_for_merge() has
894  * some heuristics behind it (see that function), so be sure to try it
895  * exactly as-is as well as making variants.
896  */
897  all_pathkeys = select_outer_pathkeys_for_merge(root,
898  extra->mergeclause_list,
899  joinrel);
900 
901  foreach(l, all_pathkeys)
902  {
903  List *front_pathkey = (List *) lfirst(l);
904  List *cur_mergeclauses;
905  List *outerkeys;
906  List *innerkeys;
907  List *merge_pathkeys;
908 
909  /* Make a pathkey list with this guy first */
910  if (l != list_head(all_pathkeys))
911  outerkeys = lcons(front_pathkey,
912  list_delete_ptr(list_copy(all_pathkeys),
913  front_pathkey));
914  else
915  outerkeys = all_pathkeys; /* no work at first one... */
916 
917  /* Sort the mergeclauses into the corresponding ordering */
918  cur_mergeclauses = find_mergeclauses_for_pathkeys(root,
919  outerkeys,
920  true,
921  extra->mergeclause_list);
922 
923  /* Should have used them all... */
924  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
925 
926  /* Build sort pathkeys for the inner side */
927  innerkeys = make_inner_pathkeys_for_merge(root,
928  cur_mergeclauses,
929  outerkeys);
930 
931  /* Build pathkeys representing output sort order */
932  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
933  outerkeys);
934 
935  /*
936  * And now we can make the path.
937  *
938  * Note: it's possible that the cheapest paths will already be sorted
939  * properly. try_mergejoin_path will detect that case and suppress an
940  * explicit sort step, so we needn't do so here.
941  */
942  try_mergejoin_path(root,
943  joinrel,
944  outer_path,
945  inner_path,
946  merge_pathkeys,
947  cur_mergeclauses,
948  outerkeys,
949  innerkeys,
950  jointype,
951  extra,
952  false);
953 
954  /*
955  * If we have partial outer and parallel safe inner path then try
956  * partial mergejoin path.
957  */
958  if (cheapest_partial_outer && cheapest_safe_inner)
960  joinrel,
961  cheapest_partial_outer,
962  cheapest_safe_inner,
963  merge_pathkeys,
964  cur_mergeclauses,
965  outerkeys,
966  innerkeys,
967  jointype,
968  extra);
969  }
970 }
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:468
#define NIL
Definition: pg_list.h:69
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:541
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1428
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:590
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:822
JoinType
Definition: nodes.h:672
Relids lateral_relids
Definition: relation.h:550
SpecialJoinInfo * sjinfo
Definition: relation.h:2183
#define linitial(l)
Definition: pg_list.h:111
struct Path * cheapest_total_path
Definition: relation.h:543
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
List * mergeclause_list
Definition: relation.h:2181
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:421
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1120
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:29
List * lcons(void *datum, List *list)
Definition: list.c:259
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:959
static int list_length(const List *l)
Definition: pg_list.h:89
bool consider_parallel
Definition: relation.h:533
List * find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, List *restrictinfos)
Definition: pathkeys.c:1003
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:563
List * pathlist
Definition: relation.h:539
Definition: pg_list.h:45
Definition: relation.h:947
static void try_hashjoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List hashclauses,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 633 of file joinpath.c.

References add_path(), add_path_precheck(), bms_free(), bms_overlap(), calc_non_nestloop_required_outer(), create_hashjoin_path(), initial_cost_hashjoin(), NIL, JoinPathExtraData::param_source_rels, JoinPathExtraData::restrictlist, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

640 {
641  Relids required_outer;
642  JoinCostWorkspace workspace;
643 
644  /*
645  * Check to see if proposed path is still parameterized, and reject if the
646  * parameterization wouldn't be sensible.
647  */
648  required_outer = calc_non_nestloop_required_outer(outer_path,
649  inner_path);
650  if (required_outer &&
651  !bms_overlap(required_outer, extra->param_source_rels))
652  {
653  /* Waste no memory when we reject a path here */
654  bms_free(required_outer);
655  return;
656  }
657 
658  /*
659  * See comments in try_nestloop_path(). Also note that hashjoin paths
660  * never have any output pathkeys, per comments in create_hashjoin_path.
661  */
662  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
663  outer_path, inner_path, extra);
664 
665  if (add_path_precheck(joinrel,
666  workspace.startup_cost, workspace.total_cost,
667  NIL, required_outer))
668  {
669  add_path(joinrel, (Path *)
671  joinrel,
672  jointype,
673  &workspace,
674  extra,
675  outer_path,
676  inner_path,
677  extra->restrictlist,
678  required_outer,
679  hashclauses));
680  }
681  else
682  {
683  /* Waste no memory when we reject a path here */
684  bms_free(required_outer);
685  }
686 }
#define NIL
Definition: pg_list.h:69
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:647
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2910
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2029
Relids param_source_rels
Definition: relation.h:2185
List * restrictlist
Definition: relation.h:2180
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
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
Definition: relation.h:947
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 
)
static

Definition at line 468 of file joinpath.c.

References add_path(), add_path_precheck(), bms_free(), bms_overlap(), calc_non_nestloop_required_outer(), create_mergejoin_path(), initial_cost_mergejoin(), NIL, JoinPathExtraData::param_source_rels, Path::pathkeys, pathkeys_contained_in(), JoinPathExtraData::restrictlist, JoinCostWorkspace::startup_cost, JoinCostWorkspace::total_cost, and try_partial_mergejoin_path().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

479 {
480  Relids required_outer;
481  JoinCostWorkspace workspace;
482 
483  if (is_partial)
484  {
486  joinrel,
487  outer_path,
488  inner_path,
489  pathkeys,
490  mergeclauses,
491  outersortkeys,
492  innersortkeys,
493  jointype,
494  extra);
495  return;
496  }
497 
498  /*
499  * Check to see if proposed path is still parameterized, and reject if the
500  * parameterization wouldn't be sensible.
501  */
502  required_outer = calc_non_nestloop_required_outer(outer_path,
503  inner_path);
504  if (required_outer &&
505  !bms_overlap(required_outer, extra->param_source_rels))
506  {
507  /* Waste no memory when we reject a path here */
508  bms_free(required_outer);
509  return;
510  }
511 
512  /*
513  * If the given paths are already well enough ordered, we can skip doing
514  * an explicit sort.
515  */
516  if (outersortkeys &&
517  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
518  outersortkeys = NIL;
519  if (innersortkeys &&
520  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
521  innersortkeys = NIL;
522 
523  /*
524  * See comments in try_nestloop_path().
525  */
526  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
527  outer_path, inner_path,
528  outersortkeys, innersortkeys,
529  extra);
530 
531  if (add_path_precheck(joinrel,
532  workspace.startup_cost, workspace.total_cost,
533  pathkeys, required_outer))
534  {
535  add_path(joinrel, (Path *)
537  joinrel,
538  jointype,
539  &workspace,
540  extra,
541  outer_path,
542  inner_path,
543  extra->restrictlist,
544  pathkeys,
545  required_outer,
546  mergeclauses,
547  outersortkeys,
548  innersortkeys));
549  }
550  else
551  {
552  /* Waste no memory when we reject a path here */
553  bms_free(required_outer);
554  }
555 }
#define NIL
Definition: pg_list.h:69
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:647
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2029
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:2359
Relids param_source_rels
Definition: relation.h:2185
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * restrictlist
Definition: relation.h:2180
List * pathkeys
Definition: relation.h:968
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
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:563
Definition: relation.h:947
static void try_nestloop_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 341 of file joinpath.c.

References add_path(), add_path_precheck(), allow_star_schema_join(), bms_free(), bms_overlap(), calc_nestloop_required_outer(), create_nestloop_path(), have_dangerous_phv(), initial_cost_nestloop(), JoinPathExtraData::param_source_rels, Path::parent, PATH_REQ_OUTER, RelOptInfo::relids, JoinPathExtraData::restrictlist, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.

Referenced by match_unsorted_outer().

348 {
349  Relids required_outer;
350  JoinCostWorkspace workspace;
351 
352  /*
353  * Check to see if proposed path is still parameterized, and reject if the
354  * parameterization wouldn't be sensible --- unless allow_star_schema_join
355  * says to allow it anyway. Also, we must reject if have_dangerous_phv
356  * doesn't like the look of it, which could only happen if the nestloop is
357  * still parameterized.
358  */
359  required_outer = calc_nestloop_required_outer(outer_path,
360  inner_path);
361  if (required_outer &&
362  ((!bms_overlap(required_outer, extra->param_source_rels) &&
363  !allow_star_schema_join(root, outer_path, inner_path)) ||
364  have_dangerous_phv(root,
365  outer_path->parent->relids,
366  PATH_REQ_OUTER(inner_path))))
367  {
368  /* Waste no memory when we reject a path here */
369  bms_free(required_outer);
370  return;
371  }
372 
373  /*
374  * Do a precheck to quickly eliminate obviously-inferior paths. We
375  * calculate a cheap lower bound on the path's cost and then use
376  * add_path_precheck() to see if the path is clearly going to be dominated
377  * by some existing path for the joinrel. If not, do the full pushup with
378  * creating a fully valid path structure and submitting it to add_path().
379  * The latter two steps are expensive enough to make this two-phase
380  * methodology worthwhile.
381  */
382  initial_cost_nestloop(root, &workspace, jointype,
383  outer_path, inner_path, extra);
384 
385  if (add_path_precheck(joinrel,
386  workspace.startup_cost, workspace.total_cost,
387  pathkeys, required_outer))
388  {
389  add_path(joinrel, (Path *)
391  joinrel,
392  jointype,
393  &workspace,
394  extra,
395  outer_path,
396  inner_path,
397  extra->restrictlist,
398  pathkeys,
399  required_outer));
400  }
401  else
402  {
403  /* Waste no memory when we reject a path here */
404  bms_free(required_outer);
405  }
406 }
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:647
Relids param_source_rels
Definition: relation.h:2185
RelOptInfo * parent
Definition: relation.h:953
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
Relids relids
Definition: relation.h:525
List * restrictlist
Definition: relation.h:2180
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
#define PATH_REQ_OUTER(path)
Definition: relation.h:973
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2087
static bool allow_star_schema_join(PlannerInfo *root, Path *outer_path, Path *inner_path)
Definition: joinpath.c:320
Definition: relation.h:947
Relids calc_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:1997
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1152
static void try_partial_hashjoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List hashclauses,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 694 of file joinpath.c.

References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty(), create_hashjoin_path(), initial_cost_hashjoin(), RelOptInfo::lateral_relids, NIL, NULL, Path::param_info, ParamPathInfo::ppi_req_outer, JoinPathExtraData::restrictlist, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

701 {
702  JoinCostWorkspace workspace;
703 
704  /*
705  * If the inner path is parameterized, the parameterization must be fully
706  * satisfied by the proposed outer path. Parameterized partial paths are
707  * not supported. The caller should already have verified that no
708  * extra_lateral_rels are required here.
709  */
711  if (inner_path->param_info != NULL)
712  {
713  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
714 
715  if (!bms_is_empty(inner_paramrels))
716  return;
717  }
718 
719  /*
720  * Before creating a path, get a quick lower bound on what it is likely to
721  * cost. Bail out right away if it looks terrible.
722  */
723  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
724  outer_path, inner_path, extra);
725  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
726  return;
727 
728  /* Might be good enough to be worth trying, so let's try it. */
729  add_partial_path(joinrel, (Path *)
731  joinrel,
732  jointype,
733  &workspace,
734  extra,
735  outer_path,
736  inner_path,
737  extra->restrictlist,
738  NULL,
739  hashclauses));
740 }
#define NIL
Definition: pg_list.h:69
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:876
ParamPathInfo * param_info
Definition: relation.h:956
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2910
Relids lateral_relids
Definition: relation.h:550
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * restrictlist
Definition: relation.h:2180
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
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
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:752
Relids ppi_req_outer
Definition: relation.h:912
Definition: relation.h:947
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 
)
static

Definition at line 563 of file joinpath.c.

References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty(), create_mergejoin_path(), initial_cost_mergejoin(), RelOptInfo::lateral_relids, NIL, NULL, Path::param_info, Path::pathkeys, pathkeys_contained_in(), ParamPathInfo::ppi_req_outer, JoinPathExtraData::restrictlist, and JoinCostWorkspace::total_cost.

Referenced by sort_inner_and_outer(), and try_mergejoin_path().

573 {
574  JoinCostWorkspace workspace;
575 
576  /*
577  * See comments in try_partial_hashjoin_path().
578  */
580  if (inner_path->param_info != NULL)
581  {
582  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
583 
584  if (!bms_is_empty(inner_paramrels))
585  return;
586  }
587 
588  /*
589  * If the given paths are already well enough ordered, we can skip doing
590  * an explicit sort.
591  */
592  if (outersortkeys &&
593  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
594  outersortkeys = NIL;
595  if (innersortkeys &&
596  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
597  innersortkeys = NIL;
598 
599  /*
600  * See comments in try_partial_nestloop_path().
601  */
602  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
603  outer_path, inner_path,
604  outersortkeys, innersortkeys,
605  extra);
606 
607  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
608  return;
609 
610  /* Might be good enough to be worth trying, so let's try it. */
611  add_partial_path(joinrel, (Path *)
613  joinrel,
614  jointype,
615  &workspace,
616  extra,
617  outer_path,
618  inner_path,
619  extra->restrictlist,
620  pathkeys,
621  NULL,
622  mergeclauses,
623  outersortkeys,
624  innersortkeys));
625 }
#define NIL
Definition: pg_list.h:69
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:876
ParamPathInfo * param_info
Definition: relation.h:956
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:2359
Relids lateral_relids
Definition: relation.h:550
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
List * restrictlist
Definition: relation.h:2180
List * pathkeys
Definition: relation.h:968
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:752
Relids ppi_req_outer
Definition: relation.h:912
Definition: relation.h:947
static void try_partial_nestloop_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 414 of file joinpath.c.

References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty(), bms_is_subset(), create_nestloop_path(), initial_cost_nestloop(), RelOptInfo::lateral_relids, NULL, Path::param_info, Path::parent, ParamPathInfo::ppi_req_outer, RelOptInfo::relids, JoinPathExtraData::restrictlist, and JoinCostWorkspace::total_cost.

Referenced by consider_parallel_nestloop().

421 {
422  JoinCostWorkspace workspace;
423 
424  /*
425  * If the inner path is parameterized, the parameterization must be fully
426  * satisfied by the proposed outer path. Parameterized partial paths are
427  * not supported. The caller should already have verified that no
428  * extra_lateral_rels are required here.
429  */
431  if (inner_path->param_info != NULL)
432  {
433  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
434 
435  if (!bms_is_subset(inner_paramrels, outer_path->parent->relids))
436  return;
437  }
438 
439  /*
440  * Before creating a path, get a quick lower bound on what it is likely to
441  * cost. Bail out right away if it looks terrible.
442  */
443  initial_cost_nestloop(root, &workspace, jointype,
444  outer_path, inner_path, extra);
445  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
446  return;
447 
448  /* Might be good enough to be worth trying, so let's try it. */
449  add_partial_path(joinrel, (Path *)
451  joinrel,
452  jointype,
453  &workspace,
454  extra,
455  outer_path,
456  inner_path,
457  extra->restrictlist,
458  pathkeys,
459  NULL));
460 }
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:876
ParamPathInfo * param_info
Definition: relation.h:956
Relids lateral_relids
Definition: relation.h:550
RelOptInfo * parent
Definition: relation.h:953
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
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
Relids relids
Definition: relation.h:525
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * restrictlist
Definition: relation.h:2180
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:752
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2087
Relids ppi_req_outer
Definition: relation.h:912
Definition: relation.h:947

Variable Documentation

set_join_pathlist_hook_type set_join_pathlist_hook = NULL

Definition at line 27 of file joinpath.c.

Referenced by add_paths_to_joinrel().