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 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 28 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 106 of file joinpath.c.

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, hash_inner_and_outer(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_SEMI, 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().

113 {
114  JoinPathExtraData extra;
115  bool mergejoin_allowed = true;
116  ListCell *lc;
117 
118  extra.restrictlist = restrictlist;
119  extra.mergeclause_list = NIL;
120  extra.sjinfo = sjinfo;
121  extra.param_source_rels = NULL;
122 
123  /*
124  * Find potential mergejoin clauses. We can skip this if we are not
125  * interested in doing a mergejoin. However, mergejoin may be our only
126  * way of implementing a full outer join, so override enable_mergejoin if
127  * it's a full join.
128  */
129  if (enable_mergejoin || jointype == JOIN_FULL)
131  joinrel,
132  outerrel,
133  innerrel,
134  restrictlist,
135  jointype,
136  &mergejoin_allowed);
137 
138  /*
139  * If it's SEMI or ANTI join, compute correction factors for cost
140  * estimation. These will be the same for all paths.
141  */
142  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
143  compute_semi_anti_join_factors(root, outerrel, innerrel,
144  jointype, sjinfo, restrictlist,
145  &extra.semifactors);
146 
147  /*
148  * Decide whether it's sensible to generate parameterized paths for this
149  * joinrel, and if so, which relations such paths should require. There
150  * is usually no need to create a parameterized result path unless there
151  * is a join order restriction that prevents joining one of our input rels
152  * directly to the parameter source rel instead of joining to the other
153  * input rel. (But see allow_star_schema_join().) This restriction
154  * reduces the number of parameterized paths we have to deal with at
155  * higher join levels, without compromising the quality of the resulting
156  * plan. We express the restriction as a Relids set that must overlap the
157  * parameterization of any proposed join path.
158  */
159  foreach(lc, root->join_info_list)
160  {
161  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
162 
163  /*
164  * SJ is relevant to this join if we have some part of its RHS
165  * (possibly not all of it), and haven't yet joined to its LHS. (This
166  * test is pretty simplistic, but should be sufficient considering the
167  * join has already been proven legal.) If the SJ is relevant, it
168  * presents constraints for joining to anything not in its RHS.
169  */
170  if (bms_overlap(joinrel->relids, sjinfo2->min_righthand) &&
171  !bms_overlap(joinrel->relids, sjinfo2->min_lefthand))
174  sjinfo2->min_righthand));
175 
176  /* full joins constrain both sides symmetrically */
177  if (sjinfo2->jointype == JOIN_FULL &&
178  bms_overlap(joinrel->relids, sjinfo2->min_lefthand) &&
179  !bms_overlap(joinrel->relids, sjinfo2->min_righthand))
182  sjinfo2->min_lefthand));
183  }
184 
185  /*
186  * However, when a LATERAL subquery is involved, there will simply not be
187  * any paths for the joinrel that aren't parameterized by whatever the
188  * subquery is parameterized by, unless its parameterization is resolved
189  * within the joinrel. So we might as well allow additional dependencies
190  * on whatever residual lateral dependencies the joinrel will have.
191  */
193  joinrel->lateral_relids);
194 
195  /*
196  * 1. Consider mergejoin paths where both relations must be explicitly
197  * sorted. Skip this if we can't mergejoin.
198  */
199  if (mergejoin_allowed)
200  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
201  jointype, &extra);
202 
203  /*
204  * 2. Consider paths where the outer relation need not be explicitly
205  * sorted. This includes both nestloops and mergejoins where the outer
206  * path is already ordered. Again, skip this if we can't mergejoin.
207  * (That's okay because we know that nestloop can't handle right/full
208  * joins at all, so it wouldn't work in the prohibited cases either.)
209  */
210  if (mergejoin_allowed)
211  match_unsorted_outer(root, joinrel, outerrel, innerrel,
212  jointype, &extra);
213 
214 #ifdef NOT_USED
215 
216  /*
217  * 3. Consider paths where the inner relation need not be explicitly
218  * sorted. This includes mergejoins only (nestloops were already built in
219  * match_unsorted_outer).
220  *
221  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
222  * significant difference between the inner and outer side of a mergejoin,
223  * so match_unsorted_inner creates no paths that aren't equivalent to
224  * those made by match_unsorted_outer when add_paths_to_joinrel() is
225  * invoked with the two rels given in the other order.
226  */
227  if (mergejoin_allowed)
228  match_unsorted_inner(root, joinrel, outerrel, innerrel,
229  jointype, &extra);
230 #endif
231 
232  /*
233  * 4. Consider paths where both outer and inner relations must be hashed
234  * before being joined. As above, disregard enable_hashjoin for full
235  * joins, because there may be no other alternative.
236  */
237  if (enable_hashjoin || jointype == JOIN_FULL)
238  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
239  jointype, &extra);
240 
241  /*
242  * 5. If inner and outer relations are foreign tables (or joins) belonging
243  * to the same server and assigned to the same user to check access
244  * permissions as, give the FDW a chance to push down joins.
245  */
246  if (joinrel->fdwroutine &&
248  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
249  outerrel, innerrel,
250  jointype, &extra);
251 
252  /*
253  * 6. Finally, give extensions a chance to manipulate the path list.
254  */
256  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
257  jointype, &extra);
258 }
#define NIL
Definition: pg_list.h:69
SemiAntiJoinFactors semifactors
Definition: relation.h:2133
List * join_info_list
Definition: relation.h:249
Relids min_righthand
Definition: relation.h:1870
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:1547
Relids lateral_relids
Definition: relation.h:519
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:749
Relids all_baserels
Definition: relation.h:195
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:188
Relids param_source_rels
Definition: relation.h:2134
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:838
struct FdwRoutine * fdwroutine
Definition: relation.h:545
List * mergeclause_list
Definition: relation.h:2131
Relids relids
Definition: relation.h:494
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:1778
List * restrictlist
Definition: relation.h:2130
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:26
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:3671
JoinType jointype
Definition: relation.h:1873
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:1869
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:1201
static bool allow_star_schema_join ( PlannerInfo root,
Path outer_path,
Path inner_path 
)
inlinestatic

Definition at line 276 of file joinpath.c.

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

Referenced by try_nestloop_path().

279 {
280  Relids innerparams = PATH_REQ_OUTER(inner_path);
281  Relids outerrelids = outer_path->parent->relids;
282 
283  /*
284  * It's a star-schema case if the outer rel provides some but not all of
285  * the inner rel's parameterization.
286  */
287  return (bms_overlap(innerparams, outerrelids) &&
288  bms_nonempty_difference(innerparams, outerrelids));
289 }
RelOptInfo * parent
Definition: relation.h:917
Relids relids
Definition: relation.h:494
#define PATH_REQ_OUTER(path)
Definition: relation.h:937
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 717 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().

719 {
720  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
721  bms_is_subset(rinfo->right_relids, innerrel->relids))
722  {
723  /* lefthand side is outer */
724  rinfo->outer_is_left = true;
725  return true;
726  }
727  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
728  bms_is_subset(rinfo->right_relids, outerrel->relids))
729  {
730  /* righthand side is outer */
731  rinfo->outer_is_left = false;
732  return true;
733  }
734  return false; /* no good for these input relations */
735 }
Relids left_relids
Definition: relation.h:1726
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
bool outer_is_left
Definition: relation.h:1754
Relids relids
Definition: relation.h:494
Relids right_relids
Definition: relation.h:1727
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 1435 of file joinpath.c.

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

Referenced by match_unsorted_outer().

1442 {
1443  ListCell *lc1;
1444 
1445  /* generate merge join path for each partial outer path */
1446  foreach(lc1, outerrel->partial_pathlist)
1447  {
1448  Path *outerpath = (Path *) lfirst(lc1);
1449  List *merge_pathkeys;
1450 
1451  /*
1452  * Figure out what useful ordering any paths we create will have.
1453  */
1454  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1455  outerpath->pathkeys);
1456 
1457  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1458  extra, false, inner_cheapest_total,
1459  merge_pathkeys, true);
1460  }
1461 }
List * partial_pathlist
Definition: relation.h:510
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:951
List * pathkeys
Definition: relation.h:932
#define lfirst(lc)
Definition: pg_list.h:106
Definition: pg_list.h:45
Definition: relation.h:911
static void consider_parallel_nestloop ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1475 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().

1481 {
1482  JoinType save_jointype = jointype;
1483  ListCell *lc1;
1484 
1485  if (jointype == JOIN_UNIQUE_INNER)
1486  jointype = JOIN_INNER;
1487 
1488  foreach(lc1, outerrel->partial_pathlist)
1489  {
1490  Path *outerpath = (Path *) lfirst(lc1);
1491  List *pathkeys;
1492  ListCell *lc2;
1493 
1494  /* Figure out what useful ordering any paths we create will have. */
1495  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1496  outerpath->pathkeys);
1497 
1498  /*
1499  * Try the cheapest parameterized paths; only those which will produce
1500  * an unparameterized path when joined to this outerrel will survive
1501  * try_partial_nestloop_path. The cheapest unparameterized path is
1502  * also in this list.
1503  */
1504  foreach(lc2, innerrel->cheapest_parameterized_paths)
1505  {
1506  Path *innerpath = (Path *) lfirst(lc2);
1507 
1508  /* Can't join to an inner path that is not parallel-safe */
1509  if (!innerpath->parallel_safe)
1510  continue;
1511 
1512  /*
1513  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1514  * cheapest_total_path, and we have to unique-ify it. (We might
1515  * be able to relax this to allow other safe, unparameterized
1516  * inner paths, but right now create_unique_path is not on board
1517  * with that.)
1518  */
1519  if (save_jointype == JOIN_UNIQUE_INNER)
1520  {
1521  if (innerpath != innerrel->cheapest_total_path)
1522  continue;
1523  innerpath = (Path *) create_unique_path(root, innerrel,
1524  innerpath,
1525  extra->sjinfo);
1526  Assert(innerpath);
1527  }
1528 
1529  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1530  pathkeys, jointype, extra);
1531  }
1532  }
1533 }
List * partial_pathlist
Definition: relation.h:510
List * cheapest_parameterized_paths
Definition: relation.h:514
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:669
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
struct Path * cheapest_total_path
Definition: relation.h:512
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:372
List * pathkeys
Definition: relation.h:932
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
bool parallel_safe
Definition: relation.h:923
Definition: pg_list.h:45
Definition: relation.h:911
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 951 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().

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

Definition at line 1547 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().

1553 {
1554  JoinType save_jointype = jointype;
1555  bool isouterjoin = IS_OUTER_JOIN(jointype);
1556  List *hashclauses;
1557  ListCell *l;
1558 
1559  /*
1560  * We need to build only one hashclauses list for any given pair of outer
1561  * and inner relations; all of the hashable clauses will be used as keys.
1562  *
1563  * Scan the join's restrictinfo list to find hashjoinable clauses that are
1564  * usable with this pair of sub-relations.
1565  */
1566  hashclauses = NIL;
1567  foreach(l, extra->restrictlist)
1568  {
1569  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1570 
1571  /*
1572  * If processing an outer join, only use its own join clauses for
1573  * hashing. For inner joins we need not be so picky.
1574  */
1575  if (isouterjoin && restrictinfo->is_pushed_down)
1576  continue;
1577 
1578  if (!restrictinfo->can_join ||
1579  restrictinfo->hashjoinoperator == InvalidOid)
1580  continue; /* not hashjoinable */
1581 
1582  /*
1583  * Check if clause has the form "outer op inner" or "inner op outer".
1584  */
1585  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1586  continue; /* no good for these input relations */
1587 
1588  hashclauses = lappend(hashclauses, restrictinfo);
1589  }
1590 
1591  /* If we found any usable hashclauses, make paths */
1592  if (hashclauses)
1593  {
1594  /*
1595  * We consider both the cheapest-total-cost and cheapest-startup-cost
1596  * outer paths. There's no need to consider any but the
1597  * cheapest-total-cost inner path, however.
1598  */
1599  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
1600  Path *cheapest_total_outer = outerrel->cheapest_total_path;
1601  Path *cheapest_total_inner = innerrel->cheapest_total_path;
1602 
1603  /*
1604  * If either cheapest-total path is parameterized by the other rel, we
1605  * can't use a hashjoin. (There's no use looking for alternative
1606  * input paths, since these should already be the least-parameterized
1607  * available paths.)
1608  */
1609  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
1610  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
1611  return;
1612 
1613  /* Unique-ify if need be; we ignore parameterized possibilities */
1614  if (jointype == JOIN_UNIQUE_OUTER)
1615  {
1616  cheapest_total_outer = (Path *)
1617  create_unique_path(root, outerrel,
1618  cheapest_total_outer, extra->sjinfo);
1619  Assert(cheapest_total_outer);
1620  jointype = JOIN_INNER;
1621  try_hashjoin_path(root,
1622  joinrel,
1623  cheapest_total_outer,
1624  cheapest_total_inner,
1625  hashclauses,
1626  jointype,
1627  extra);
1628  /* no possibility of cheap startup here */
1629  }
1630  else if (jointype == JOIN_UNIQUE_INNER)
1631  {
1632  cheapest_total_inner = (Path *)
1633  create_unique_path(root, innerrel,
1634  cheapest_total_inner, extra->sjinfo);
1635  Assert(cheapest_total_inner);
1636  jointype = JOIN_INNER;
1637  try_hashjoin_path(root,
1638  joinrel,
1639  cheapest_total_outer,
1640  cheapest_total_inner,
1641  hashclauses,
1642  jointype,
1643  extra);
1644  if (cheapest_startup_outer != NULL &&
1645  cheapest_startup_outer != cheapest_total_outer)
1646  try_hashjoin_path(root,
1647  joinrel,
1648  cheapest_startup_outer,
1649  cheapest_total_inner,
1650  hashclauses,
1651  jointype,
1652  extra);
1653  }
1654  else
1655  {
1656  /*
1657  * For other jointypes, we consider the cheapest startup outer
1658  * together with the cheapest total inner, and then consider
1659  * pairings of cheapest-total paths including parameterized ones.
1660  * There is no use in generating parameterized paths on the basis
1661  * of possibly cheap startup cost, so this is sufficient.
1662  */
1663  ListCell *lc1;
1664  ListCell *lc2;
1665 
1666  if (cheapest_startup_outer != NULL)
1667  try_hashjoin_path(root,
1668  joinrel,
1669  cheapest_startup_outer,
1670  cheapest_total_inner,
1671  hashclauses,
1672  jointype,
1673  extra);
1674 
1675  foreach(lc1, outerrel->cheapest_parameterized_paths)
1676  {
1677  Path *outerpath = (Path *) lfirst(lc1);
1678 
1679  /*
1680  * We cannot use an outer path that is parameterized by the
1681  * inner rel.
1682  */
1683  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1684  continue;
1685 
1686  foreach(lc2, innerrel->cheapest_parameterized_paths)
1687  {
1688  Path *innerpath = (Path *) lfirst(lc2);
1689 
1690  /*
1691  * We cannot use an inner path that is parameterized by
1692  * the outer rel, either.
1693  */
1694  if (PATH_PARAM_BY_REL(innerpath, outerrel))
1695  continue;
1696 
1697  if (outerpath == cheapest_startup_outer &&
1698  innerpath == cheapest_total_inner)
1699  continue; /* already tried it */
1700 
1701  try_hashjoin_path(root,
1702  joinrel,
1703  outerpath,
1704  innerpath,
1705  hashclauses,
1706  jointype,
1707  extra);
1708  }
1709  }
1710  }
1711 
1712  /*
1713  * If the joinrel is parallel-safe, we may be able to consider a
1714  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
1715  * because the outer path will be partial, and therefore we won't be
1716  * able to properly guarantee uniqueness. Similarly, we can't handle
1717  * JOIN_FULL and JOIN_RIGHT, because they can produce false null
1718  * extended rows. Also, the resulting path must not be parameterized.
1719  */
1720  if (joinrel->consider_parallel &&
1721  save_jointype != JOIN_UNIQUE_OUTER &&
1722  save_jointype != JOIN_FULL &&
1723  save_jointype != JOIN_RIGHT &&
1724  outerrel->partial_pathlist != NIL &&
1725  bms_is_empty(joinrel->lateral_relids))
1726  {
1727  Path *cheapest_partial_outer;
1728  Path *cheapest_safe_inner = NULL;
1729 
1730  cheapest_partial_outer =
1731  (Path *) linitial(outerrel->partial_pathlist);
1732 
1733  /*
1734  * Normally, given that the joinrel is parallel-safe, the cheapest
1735  * total inner path will also be parallel-safe, but if not, we'll
1736  * have to search for the cheapest safe, unparameterized inner
1737  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
1738  * inner path.
1739  */
1740  if (cheapest_total_inner->parallel_safe)
1741  cheapest_safe_inner = cheapest_total_inner;
1742  else if (save_jointype != JOIN_UNIQUE_INNER)
1743  cheapest_safe_inner =
1745 
1746  if (cheapest_safe_inner != NULL)
1747  try_partial_hashjoin_path(root, joinrel,
1748  cheapest_partial_outer,
1749  cheapest_safe_inner,
1750  hashclauses, jointype, extra);
1751  }
1752  }
1753 }
#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:593
struct Path * cheapest_startup_path
Definition: relation.h:511
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:656
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:718
List * partial_pathlist
Definition: relation.h:510
List * cheapest_parameterized_paths
Definition: relation.h:514
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1428
JoinType
Definition: nodes.h:669
Relids lateral_relids
Definition: relation.h:519
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
#define linitial(l)
Definition: pg_list.h:110
bool can_join
Definition: relation.h:1705
struct Path * cheapest_total_path
Definition: relation.h:512
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:2130
#define InvalidOid
Definition: postgres_ext.h:36
bool is_pushed_down
Definition: relation.h:1701
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:28
#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:923
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:717
Oid hashjoinoperator
Definition: relation.h:1757
bool consider_parallel
Definition: relation.h:502
List * pathlist
Definition: relation.h:508
Definition: pg_list.h:45
Definition: relation.h:911
static void match_unsorted_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1201 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().

1207 {
1208  JoinType save_jointype = jointype;
1209  bool nestjoinOK;
1210  bool useallclauses;
1211  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1212  Path *matpath = NULL;
1213  ListCell *lc1;
1214 
1215  /*
1216  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1217  * are doing a right or full mergejoin, we must use *all* the mergeclauses
1218  * as join clauses, else we will not have a valid plan. (Although these
1219  * two flags are currently inverses, keep them separate for clarity and
1220  * possible future changes.)
1221  */
1222  switch (jointype)
1223  {
1224  case JOIN_INNER:
1225  case JOIN_LEFT:
1226  case JOIN_SEMI:
1227  case JOIN_ANTI:
1228  nestjoinOK = true;
1229  useallclauses = false;
1230  break;
1231  case JOIN_RIGHT:
1232  case JOIN_FULL:
1233  nestjoinOK = false;
1234  useallclauses = true;
1235  break;
1236  case JOIN_UNIQUE_OUTER:
1237  case JOIN_UNIQUE_INNER:
1238  jointype = JOIN_INNER;
1239  nestjoinOK = true;
1240  useallclauses = false;
1241  break;
1242  default:
1243  elog(ERROR, "unrecognized join type: %d",
1244  (int) jointype);
1245  nestjoinOK = false; /* keep compiler quiet */
1246  useallclauses = false;
1247  break;
1248  }
1249 
1250  /*
1251  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1252  * we will consider it below as a member of cheapest_parameterized_paths,
1253  * but the other possibilities considered in this routine aren't usable.
1254  */
1255  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1256  inner_cheapest_total = NULL;
1257 
1258  /*
1259  * If we need to unique-ify the inner path, we will consider only the
1260  * cheapest-total inner.
1261  */
1262  if (save_jointype == JOIN_UNIQUE_INNER)
1263  {
1264  /* No way to do this with an inner path parameterized by outer rel */
1265  if (inner_cheapest_total == NULL)
1266  return;
1267  inner_cheapest_total = (Path *)
1268  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1269  Assert(inner_cheapest_total);
1270  }
1271  else if (nestjoinOK)
1272  {
1273  /*
1274  * Consider materializing the cheapest inner path, unless
1275  * enable_material is off or the path in question materializes its
1276  * output anyway.
1277  */
1278  if (enable_material && inner_cheapest_total != NULL &&
1279  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1280  matpath = (Path *)
1281  create_material_path(innerrel, inner_cheapest_total);
1282  }
1283 
1284  foreach(lc1, outerrel->pathlist)
1285  {
1286  Path *outerpath = (Path *) lfirst(lc1);
1287  List *merge_pathkeys;
1288 
1289  /*
1290  * We cannot use an outer path that is parameterized by the inner rel.
1291  */
1292  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1293  continue;
1294 
1295  /*
1296  * If we need to unique-ify the outer path, it's pointless to consider
1297  * any but the cheapest outer. (XXX we don't consider parameterized
1298  * outers, nor inners, for unique-ified cases. Should we?)
1299  */
1300  if (save_jointype == JOIN_UNIQUE_OUTER)
1301  {
1302  if (outerpath != outerrel->cheapest_total_path)
1303  continue;
1304  outerpath = (Path *) create_unique_path(root, outerrel,
1305  outerpath, extra->sjinfo);
1306  Assert(outerpath);
1307  }
1308 
1309  /*
1310  * The result will have this sort order (even if it is implemented as
1311  * a nestloop, and even if some of the mergeclauses are implemented by
1312  * qpquals rather than as true mergeclauses):
1313  */
1314  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1315  outerpath->pathkeys);
1316 
1317  if (save_jointype == JOIN_UNIQUE_INNER)
1318  {
1319  /*
1320  * Consider nestloop join, but only with the unique-ified cheapest
1321  * inner path
1322  */
1323  try_nestloop_path(root,
1324  joinrel,
1325  outerpath,
1326  inner_cheapest_total,
1327  merge_pathkeys,
1328  jointype,
1329  extra);
1330  }
1331  else if (nestjoinOK)
1332  {
1333  /*
1334  * Consider nestloop joins using this outer path and various
1335  * available paths for the inner relation. We consider the
1336  * cheapest-total paths for each available parameterization of the
1337  * inner relation, including the unparameterized case.
1338  */
1339  ListCell *lc2;
1340 
1341  foreach(lc2, innerrel->cheapest_parameterized_paths)
1342  {
1343  Path *innerpath = (Path *) lfirst(lc2);
1344 
1345  try_nestloop_path(root,
1346  joinrel,
1347  outerpath,
1348  innerpath,
1349  merge_pathkeys,
1350  jointype,
1351  extra);
1352  }
1353 
1354  /* Also consider materialized form of the cheapest inner path */
1355  if (matpath != NULL)
1356  try_nestloop_path(root,
1357  joinrel,
1358  outerpath,
1359  matpath,
1360  merge_pathkeys,
1361  jointype,
1362  extra);
1363  }
1364 
1365  /* Can't do anything else if outer path needs to be unique'd */
1366  if (save_jointype == JOIN_UNIQUE_OUTER)
1367  continue;
1368 
1369  /* Can't do anything else if inner rel is parameterized by outer */
1370  if (inner_cheapest_total == NULL)
1371  continue;
1372 
1373  /* Generate merge join paths */
1374  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1375  save_jointype, extra, useallclauses,
1376  inner_cheapest_total, merge_pathkeys,
1377  false);
1378  }
1379 
1380  /*
1381  * Consider partial nestloop and mergejoin plan if outerrel has any
1382  * partial path and the joinrel is parallel-safe. However, we can't
1383  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1384  * therefore we won't be able to properly guarantee uniqueness. Nor can
1385  * we handle extra_lateral_rels, since partial paths must not be
1386  * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1387  * because they can produce false null extended rows.
1388  */
1389  if (joinrel->consider_parallel &&
1390  save_jointype != JOIN_UNIQUE_OUTER &&
1391  save_jointype != JOIN_FULL &&
1392  save_jointype != JOIN_RIGHT &&
1393  outerrel->partial_pathlist != NIL &&
1394  bms_is_empty(joinrel->lateral_relids))
1395  {
1396  if (nestjoinOK)
1397  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1398  save_jointype, extra);
1399 
1400  /*
1401  * If inner_cheapest_total is NULL or non parallel-safe then find the
1402  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1403  * can't use any alternative inner path.
1404  */
1405  if (inner_cheapest_total == NULL ||
1406  !inner_cheapest_total->parallel_safe)
1407  {
1408  if (save_jointype == JOIN_UNIQUE_INNER)
1409  return;
1410 
1411  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(
1412  innerrel->pathlist);
1413  }
1414 
1415  if (inner_cheapest_total)
1416  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1417  save_jointype, extra,
1418  inner_cheapest_total);
1419  }
1420 }
#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:297
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1389
List * partial_pathlist
Definition: relation.h:510
List * cheapest_parameterized_paths
Definition: relation.h:514
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:669
NodeTag pathtype
Definition: relation.h:915
Relids lateral_relids
Definition: relation.h:519
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
#define ERROR
Definition: elog.h:43
struct Path * cheapest_total_path
Definition: relation.h:512
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:951
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:1475
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:1435
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:28
List * pathkeys
Definition: relation.h:932
#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:923
bool consider_parallel
Definition: relation.h:502
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:566
List * pathlist
Definition: relation.h:508
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
Definition: relation.h:911
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 1778 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().

1785 {
1786  List *result_list = NIL;
1787  bool isouterjoin = IS_OUTER_JOIN(jointype);
1788  bool have_nonmergeable_joinclause = false;
1789  ListCell *l;
1790 
1791  foreach(l, restrictlist)
1792  {
1793  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1794 
1795  /*
1796  * If processing an outer join, only use its own join clauses in the
1797  * merge. For inner joins we can use pushed-down clauses too. (Note:
1798  * we don't set have_nonmergeable_joinclause here because pushed-down
1799  * clauses will become otherquals not joinquals.)
1800  */
1801  if (isouterjoin && restrictinfo->is_pushed_down)
1802  continue;
1803 
1804  /* Check that clause is a mergeable operator clause */
1805  if (!restrictinfo->can_join ||
1806  restrictinfo->mergeopfamilies == NIL)
1807  {
1808  /*
1809  * The executor can handle extra joinquals that are constants, but
1810  * not anything else, when doing right/full merge join. (The
1811  * reason to support constants is so we can do FULL JOIN ON
1812  * FALSE.)
1813  */
1814  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
1815  have_nonmergeable_joinclause = true;
1816  continue; /* not mergejoinable */
1817  }
1818 
1819  /*
1820  * Check if clause has the form "outer op inner" or "inner op outer".
1821  */
1822  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1823  {
1824  have_nonmergeable_joinclause = true;
1825  continue; /* no good for these input relations */
1826  }
1827 
1828  /*
1829  * Insist that each side have a non-redundant eclass. This
1830  * restriction is needed because various bits of the planner expect
1831  * that each clause in a merge be associable with some pathkey in a
1832  * canonical pathkey list, but redundant eclasses can't appear in
1833  * canonical sort orderings. (XXX it might be worth relaxing this,
1834  * but not enough time to address it for 8.3.)
1835  *
1836  * Note: it would be bad if this condition failed for an otherwise
1837  * mergejoinable FULL JOIN clause, since that would result in
1838  * undesirable planner failure. I believe that is not possible
1839  * however; a variable involved in a full join could only appear in
1840  * below_outer_join eclasses, which aren't considered redundant.
1841  *
1842  * This case *can* happen for left/right join clauses: the outer-side
1843  * variable could be equated to a constant. Because we will propagate
1844  * that constant across the join clause, the loss of ability to do a
1845  * mergejoin is not really all that big a deal, and so it's not clear
1846  * that improving this is important.
1847  */
1848  update_mergeclause_eclasses(root, restrictinfo);
1849 
1850  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
1851  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
1852  {
1853  have_nonmergeable_joinclause = true;
1854  continue; /* can't handle redundant eclasses */
1855  }
1856 
1857  result_list = lappend(result_list, restrictinfo);
1858  }
1859 
1860  /*
1861  * Report whether mergejoin is allowed (see comment at top of function).
1862  */
1863  switch (jointype)
1864  {
1865  case JOIN_RIGHT:
1866  case JOIN_FULL:
1867  *mergejoin_allowed = !have_nonmergeable_joinclause;
1868  break;
1869  default:
1870  *mergejoin_allowed = true;
1871  break;
1872  }
1873 
1874  return result_list;
1875 }
#define NIL
Definition: pg_list.h:69
#define IsA(nodeptr, _type_)
Definition: nodes.h:557
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:718
EquivalenceClass * right_ec
Definition: relation.h:1748
List * mergeopfamilies
Definition: relation.h:1744
bool can_join
Definition: relation.h:1705
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: relation.h:756
List * lappend(List *list, void *datum)
Definition: list.c:128
Expr * clause
Definition: relation.h:1699
bool is_pushed_down
Definition: relation.h:1701
#define lfirst(lc)
Definition: pg_list.h:106
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:717
EquivalenceClass * left_ec
Definition: relation.h:1747
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 749 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().

755 {
756  JoinType save_jointype = jointype;
757  Path *outer_path;
758  Path *inner_path;
759  Path *cheapest_partial_outer = NULL;
760  Path *cheapest_safe_inner = NULL;
761  List *all_pathkeys;
762  ListCell *l;
763 
764  /*
765  * We only consider the cheapest-total-cost input paths, since we are
766  * assuming here that a sort is required. We will consider
767  * cheapest-startup-cost input paths later, and only if they don't need a
768  * sort.
769  *
770  * This function intentionally does not consider parameterized input
771  * paths, except when the cheapest-total is parameterized. If we did so,
772  * we'd have a combinatorial explosion of mergejoin paths of dubious
773  * value. This interacts with decisions elsewhere that also discriminate
774  * against mergejoins with parameterized inputs; see comments in
775  * src/backend/optimizer/README.
776  */
777  outer_path = outerrel->cheapest_total_path;
778  inner_path = innerrel->cheapest_total_path;
779 
780  /*
781  * If either cheapest-total path is parameterized by the other rel, we
782  * can't use a mergejoin. (There's no use looking for alternative input
783  * paths, since these should already be the least-parameterized available
784  * paths.)
785  */
786  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
787  PATH_PARAM_BY_REL(inner_path, outerrel))
788  return;
789 
790  /*
791  * If unique-ification is requested, do it and then handle as a plain
792  * inner join.
793  */
794  if (jointype == JOIN_UNIQUE_OUTER)
795  {
796  outer_path = (Path *) create_unique_path(root, outerrel,
797  outer_path, extra->sjinfo);
798  Assert(outer_path);
799  jointype = JOIN_INNER;
800  }
801  else if (jointype == JOIN_UNIQUE_INNER)
802  {
803  inner_path = (Path *) create_unique_path(root, innerrel,
804  inner_path, extra->sjinfo);
805  Assert(inner_path);
806  jointype = JOIN_INNER;
807  }
808 
809  /*
810  * If the joinrel is parallel-safe, we may be able to consider a partial
811  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
812  * outer path will be partial, and therefore we won't be able to properly
813  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
814  * JOIN_RIGHT, because they can produce false null extended rows. Also,
815  * the resulting path must not be parameterized.
816  */
817  if (joinrel->consider_parallel &&
818  save_jointype != JOIN_UNIQUE_OUTER &&
819  save_jointype != JOIN_FULL &&
820  save_jointype != JOIN_RIGHT &&
821  outerrel->partial_pathlist != NIL &&
822  bms_is_empty(joinrel->lateral_relids))
823  {
824  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
825 
826  if (inner_path->parallel_safe)
827  cheapest_safe_inner = inner_path;
828  else if (save_jointype != JOIN_UNIQUE_INNER)
829  cheapest_safe_inner =
831  }
832 
833  /*
834  * Each possible ordering of the available mergejoin clauses will generate
835  * a differently-sorted result path at essentially the same cost. We have
836  * no basis for choosing one over another at this level of joining, but
837  * some sort orders may be more useful than others for higher-level
838  * mergejoins, so it's worth considering multiple orderings.
839  *
840  * Actually, it's not quite true that every mergeclause ordering will
841  * generate a different path order, because some of the clauses may be
842  * partially redundant (refer to the same EquivalenceClasses). Therefore,
843  * what we do is convert the mergeclause list to a list of canonical
844  * pathkeys, and then consider different orderings of the pathkeys.
845  *
846  * Generating a path for *every* permutation of the pathkeys doesn't seem
847  * like a winning strategy; the cost in planning time is too high. For
848  * now, we generate one path for each pathkey, listing that pathkey first
849  * and the rest in random order. This should allow at least a one-clause
850  * mergejoin without re-sorting against any other possible mergejoin
851  * partner path. But if we've not guessed the right ordering of secondary
852  * keys, we may end up evaluating clauses as qpquals when they could have
853  * been done as mergeclauses. (In practice, it's rare that there's more
854  * than two or three mergeclauses, so expending a huge amount of thought
855  * on that is probably not worth it.)
856  *
857  * The pathkey order returned by select_outer_pathkeys_for_merge() has
858  * some heuristics behind it (see that function), so be sure to try it
859  * exactly as-is as well as making variants.
860  */
861  all_pathkeys = select_outer_pathkeys_for_merge(root,
862  extra->mergeclause_list,
863  joinrel);
864 
865  foreach(l, all_pathkeys)
866  {
867  List *front_pathkey = (List *) lfirst(l);
868  List *cur_mergeclauses;
869  List *outerkeys;
870  List *innerkeys;
871  List *merge_pathkeys;
872 
873  /* Make a pathkey list with this guy first */
874  if (l != list_head(all_pathkeys))
875  outerkeys = lcons(front_pathkey,
876  list_delete_ptr(list_copy(all_pathkeys),
877  front_pathkey));
878  else
879  outerkeys = all_pathkeys; /* no work at first one... */
880 
881  /* Sort the mergeclauses into the corresponding ordering */
882  cur_mergeclauses = find_mergeclauses_for_pathkeys(root,
883  outerkeys,
884  true,
885  extra->mergeclause_list);
886 
887  /* Should have used them all... */
888  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
889 
890  /* Build sort pathkeys for the inner side */
891  innerkeys = make_inner_pathkeys_for_merge(root,
892  cur_mergeclauses,
893  outerkeys);
894 
895  /* Build pathkeys representing output sort order */
896  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
897  outerkeys);
898 
899  /*
900  * And now we can make the path.
901  *
902  * Note: it's possible that the cheapest paths will already be sorted
903  * properly. try_mergejoin_path will detect that case and suppress an
904  * explicit sort step, so we needn't do so here.
905  */
906  try_mergejoin_path(root,
907  joinrel,
908  outer_path,
909  inner_path,
910  merge_pathkeys,
911  cur_mergeclauses,
912  outerkeys,
913  innerkeys,
914  jointype,
915  extra,
916  false);
917 
918  /*
919  * If we have partial outer and parallel safe inner path then try
920  * partial mergejoin path.
921  */
922  if (cheapest_partial_outer && cheapest_safe_inner)
924  joinrel,
925  cheapest_partial_outer,
926  cheapest_safe_inner,
927  merge_pathkeys,
928  cur_mergeclauses,
929  outerkeys,
930  innerkeys,
931  jointype,
932  extra);
933  }
934 }
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:428
#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:510
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:669
Relids lateral_relids
Definition: relation.h:519
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
#define linitial(l)
Definition: pg_list.h:110
struct Path * cheapest_total_path
Definition: relation.h:512
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
List * mergeclause_list
Definition: relation.h:2131
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:28
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:923
static int list_length(const List *l)
Definition: pg_list.h:89
bool consider_parallel
Definition: relation.h:502
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:523
List * pathlist
Definition: relation.h:508
Definition: pg_list.h:45
Definition: relation.h:911
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 593 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, JoinPathExtraData::semifactors, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

600 {
601  Relids required_outer;
602  JoinCostWorkspace workspace;
603 
604  /*
605  * Check to see if proposed path is still parameterized, and reject if the
606  * parameterization wouldn't be sensible.
607  */
608  required_outer = calc_non_nestloop_required_outer(outer_path,
609  inner_path);
610  if (required_outer &&
611  !bms_overlap(required_outer, extra->param_source_rels))
612  {
613  /* Waste no memory when we reject a path here */
614  bms_free(required_outer);
615  return;
616  }
617 
618  /*
619  * See comments in try_nestloop_path(). Also note that hashjoin paths
620  * never have any output pathkeys, per comments in create_hashjoin_path.
621  */
622  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
623  outer_path, inner_path,
624  extra->sjinfo, &extra->semifactors);
625 
626  if (add_path_precheck(joinrel,
627  workspace.startup_cost, workspace.total_cost,
628  NIL, required_outer))
629  {
630  add_path(joinrel, (Path *)
632  joinrel,
633  jointype,
634  &workspace,
635  extra->sjinfo,
636  &extra->semifactors,
637  outer_path,
638  inner_path,
639  extra->restrictlist,
640  required_outer,
641  hashclauses));
642  }
643  else
644  {
645  /* Waste no memory when we reject a path here */
646  bms_free(required_outer);
647  }
648 }
#define NIL
Definition: pg_list.h:69
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
SemiAntiJoinFactors semifactors
Definition: relation.h:2133
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:2002
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors, Path *outer_path, Path *inner_path, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition: pathnode.c:2188
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
Relids param_source_rels
Definition: relation.h:2134
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:2846
List * restrictlist
Definition: relation.h:2130
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
Definition: relation.h:911
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 428 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, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, JoinCostWorkspace::total_cost, and try_partial_mergejoin_path().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

439 {
440  Relids required_outer;
441  JoinCostWorkspace workspace;
442 
443  if (is_partial)
444  {
446  joinrel,
447  outer_path,
448  inner_path,
449  pathkeys,
450  mergeclauses,
451  outersortkeys,
452  innersortkeys,
453  jointype,
454  extra);
455  return;
456  }
457 
458  /*
459  * Check to see if proposed path is still parameterized, and reject if the
460  * parameterization wouldn't be sensible.
461  */
462  required_outer = calc_non_nestloop_required_outer(outer_path,
463  inner_path);
464  if (required_outer &&
465  !bms_overlap(required_outer, extra->param_source_rels))
466  {
467  /* Waste no memory when we reject a path here */
468  bms_free(required_outer);
469  return;
470  }
471 
472  /*
473  * If the given paths are already well enough ordered, we can skip doing
474  * an explicit sort.
475  */
476  if (outersortkeys &&
477  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
478  outersortkeys = NIL;
479  if (innersortkeys &&
480  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
481  innersortkeys = NIL;
482 
483  /*
484  * See comments in try_nestloop_path().
485  */
486  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
487  outer_path, inner_path,
488  outersortkeys, innersortkeys,
489  extra->sjinfo);
490 
491  if (add_path_precheck(joinrel,
492  workspace.startup_cost, workspace.total_cost,
493  pathkeys, required_outer))
494  {
495  add_path(joinrel, (Path *)
497  joinrel,
498  jointype,
499  &workspace,
500  extra->sjinfo,
501  outer_path,
502  inner_path,
503  extra->restrictlist,
504  pathkeys,
505  required_outer,
506  mergeclauses,
507  outersortkeys,
508  innersortkeys));
509  }
510  else
511  {
512  /* Waste no memory when we reject a path here */
513  bms_free(required_outer);
514  }
515 }
#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:2002
MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, SpecialJoinInfo *sjinfo, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer, List *mergeclauses, List *outersortkeys, List *innersortkeys)
Definition: pathnode.c:2124
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
Relids param_source_rels
Definition: relation.h:2134
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, SpecialJoinInfo *sjinfo)
Definition: costsize.c:2322
List * restrictlist
Definition: relation.h:2130
List * pathkeys
Definition: relation.h:932
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:523
Definition: relation.h:911
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 297 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, JoinPathExtraData::semifactors, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.

Referenced by match_unsorted_outer().

304 {
305  Relids required_outer;
306  JoinCostWorkspace workspace;
307 
308  /*
309  * Check to see if proposed path is still parameterized, and reject if the
310  * parameterization wouldn't be sensible --- unless allow_star_schema_join
311  * says to allow it anyway. Also, we must reject if have_dangerous_phv
312  * doesn't like the look of it, which could only happen if the nestloop is
313  * still parameterized.
314  */
315  required_outer = calc_nestloop_required_outer(outer_path,
316  inner_path);
317  if (required_outer &&
318  ((!bms_overlap(required_outer, extra->param_source_rels) &&
319  !allow_star_schema_join(root, outer_path, inner_path)) ||
320  have_dangerous_phv(root,
321  outer_path->parent->relids,
322  PATH_REQ_OUTER(inner_path))))
323  {
324  /* Waste no memory when we reject a path here */
325  bms_free(required_outer);
326  return;
327  }
328 
329  /*
330  * Do a precheck to quickly eliminate obviously-inferior paths. We
331  * calculate a cheap lower bound on the path's cost and then use
332  * add_path_precheck() to see if the path is clearly going to be dominated
333  * by some existing path for the joinrel. If not, do the full pushup with
334  * creating a fully valid path structure and submitting it to add_path().
335  * The latter two steps are expensive enough to make this two-phase
336  * methodology worthwhile.
337  */
338  initial_cost_nestloop(root, &workspace, jointype,
339  outer_path, inner_path,
340  extra->sjinfo, &extra->semifactors);
341 
342  if (add_path_precheck(joinrel,
343  workspace.startup_cost, workspace.total_cost,
344  pathkeys, required_outer))
345  {
346  add_path(joinrel, (Path *)
348  joinrel,
349  jointype,
350  &workspace,
351  extra->sjinfo,
352  &extra->semifactors,
353  outer_path,
354  inner_path,
355  extra->restrictlist,
356  pathkeys,
357  required_outer));
358  }
359  else
360  {
361  /* Waste no memory when we reject a path here */
362  bms_free(required_outer);
363  }
364 }
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:2051
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
SemiAntiJoinFactors semifactors
Definition: relation.h:2133
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:647
NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer)
Definition: pathnode.c:2036
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
Relids param_source_rels
Definition: relation.h:2134
RelOptInfo * parent
Definition: relation.h:917
Relids relids
Definition: relation.h:494
List * restrictlist
Definition: relation.h:2130
void bms_free(Bitmapset *a)
Definition: bitmapset.c:201
#define PATH_REQ_OUTER(path)
Definition: relation.h:937
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:443
static bool allow_star_schema_join(PlannerInfo *root, Path *outer_path, Path *inner_path)
Definition: joinpath.c:276
Definition: relation.h:911
Relids calc_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:1970
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 656 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, JoinPathExtraData::semifactors, JoinPathExtraData::sjinfo, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

663 {
664  JoinCostWorkspace workspace;
665 
666  /*
667  * If the inner path is parameterized, the parameterization must be fully
668  * satisfied by the proposed outer path. Parameterized partial paths are
669  * not supported. The caller should already have verified that no
670  * extra_lateral_rels are required here.
671  */
673  if (inner_path->param_info != NULL)
674  {
675  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
676 
677  if (!bms_is_empty(inner_paramrels))
678  return;
679  }
680 
681  /*
682  * Before creating a path, get a quick lower bound on what it is likely to
683  * cost. Bail out right away if it looks terrible.
684  */
685  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
686  outer_path, inner_path,
687  extra->sjinfo, &extra->semifactors);
688  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
689  return;
690 
691  /* Might be good enough to be worth trying, so let's try it. */
692  add_partial_path(joinrel, (Path *)
694  joinrel,
695  jointype,
696  &workspace,
697  extra->sjinfo,
698  &extra->semifactors,
699  outer_path,
700  inner_path,
701  extra->restrictlist,
702  NULL,
703  hashclauses));
704 }
#define NIL
Definition: pg_list.h:69
SemiAntiJoinFactors semifactors
Definition: relation.h:2133
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:876
ParamPathInfo * param_info
Definition: relation.h:920
Relids lateral_relids
Definition: relation.h:519
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors, Path *outer_path, Path *inner_path, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition: pathnode.c:2188
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:2846
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * restrictlist
Definition: relation.h:2130
#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:876
Definition: relation.h:911
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 523 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, JoinPathExtraData::sjinfo, and JoinCostWorkspace::total_cost.

Referenced by sort_inner_and_outer(), and try_mergejoin_path().

533 {
534  JoinCostWorkspace workspace;
535 
536  /*
537  * See comments in try_partial_hashjoin_path().
538  */
540  if (inner_path->param_info != NULL)
541  {
542  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
543 
544  if (!bms_is_empty(inner_paramrels))
545  return;
546  }
547 
548  /*
549  * If the given paths are already well enough ordered, we can skip doing
550  * an explicit sort.
551  */
552  if (outersortkeys &&
553  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
554  outersortkeys = NIL;
555  if (innersortkeys &&
556  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
557  innersortkeys = NIL;
558 
559  /*
560  * See comments in try_partial_nestloop_path().
561  */
562  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
563  outer_path, inner_path,
564  outersortkeys, innersortkeys,
565  extra->sjinfo);
566 
567  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
568  return;
569 
570  /* Might be good enough to be worth trying, so let's try it. */
571  add_partial_path(joinrel, (Path *)
573  joinrel,
574  jointype,
575  &workspace,
576  extra->sjinfo,
577  outer_path,
578  inner_path,
579  extra->restrictlist,
580  pathkeys,
581  NULL,
582  mergeclauses,
583  outersortkeys,
584  innersortkeys));
585 }
#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:920
MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, SpecialJoinInfo *sjinfo, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer, List *mergeclauses, List *outersortkeys, List *innersortkeys)
Definition: pathnode.c:2124
Relids lateral_relids
Definition: relation.h:519
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:317
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, SpecialJoinInfo *sjinfo)
Definition: costsize.c:2322
List * restrictlist
Definition: relation.h:2130
List * pathkeys
Definition: relation.h:932
#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:876
Definition: relation.h:911
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 372 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, JoinPathExtraData::semifactors, JoinPathExtraData::sjinfo, and JoinCostWorkspace::total_cost.

Referenced by consider_parallel_nestloop().

379 {
380  JoinCostWorkspace workspace;
381 
382  /*
383  * If the inner path is parameterized, the parameterization must be fully
384  * satisfied by the proposed outer path. Parameterized partial paths are
385  * not supported. The caller should already have verified that no
386  * extra_lateral_rels are required here.
387  */
389  if (inner_path->param_info != NULL)
390  {
391  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
392 
393  if (!bms_is_subset(inner_paramrels, outer_path->parent->relids))
394  return;
395  }
396 
397  /*
398  * Before creating a path, get a quick lower bound on what it is likely to
399  * cost. Bail out right away if it looks terrible.
400  */
401  initial_cost_nestloop(root, &workspace, jointype,
402  outer_path, inner_path,
403  extra->sjinfo, &extra->semifactors);
404  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
405  return;
406 
407  /* Might be good enough to be worth trying, so let's try it. */
408  add_partial_path(joinrel, (Path *)
410  joinrel,
411  jointype,
412  &workspace,
413  extra->sjinfo,
414  &extra->semifactors,
415  outer_path,
416  inner_path,
417  extra->restrictlist,
418  pathkeys,
419  NULL));
420 }
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:2051
SemiAntiJoinFactors semifactors
Definition: relation.h:2133
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:876
ParamPathInfo * param_info
Definition: relation.h:920
NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, SpecialJoinInfo *sjinfo, SemiAntiJoinFactors *semifactors, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer)
Definition: pathnode.c:2036
Relids lateral_relids
Definition: relation.h:519
SpecialJoinInfo * sjinfo
Definition: relation.h:2132
RelOptInfo * parent
Definition: relation.h:917
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:308
Relids relids
Definition: relation.h:494
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:663
List * restrictlist
Definition: relation.h:2130
#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:876
Definition: relation.h:911

Variable Documentation

set_join_pathlist_hook_type set_join_pathlist_hook = NULL

Definition at line 26 of file joinpath.c.

Referenced by add_paths_to_joinrel().