PostgreSQL Source Code  git master
joinpath.c File Reference
#include "postgres.h"
#include <math.h>
#include "executor/executor.h"
#include "foreign/fdwapi.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "utils/typcache.h"
Include dependency graph for joinpath.c:

Go to the source code of this file.

Macros

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

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 bool clause_sides_match_join (RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
 
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, Relids outerrelids, Relids inner_paramrels)
 
static bool paraminfo_get_equal_hashops (PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List **param_exprs, List **operators, bool *binary_mode)
 
static Pathget_memoize_path (PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
 
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, bool parallel_hash)
 

Variables

set_join_pathlist_hook_type set_join_pathlist_hook = NULL
 

Macro Definition Documentation

◆ PATH_PARAM_BY_PARENT

#define PATH_PARAM_BY_PARENT (   path,
  rel 
)
Value:
((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \
(rel)->top_parent_relids))
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:495
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1556

Definition at line 36 of file joinpath.c.

◆ PATH_PARAM_BY_REL

#define PATH_PARAM_BY_REL (   path,
  rel 
)     (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))

Definition at line 42 of file joinpath.c.

◆ PATH_PARAM_BY_REL_SELF

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

Definition at line 39 of file joinpath.c.

Function Documentation

◆ add_paths_to_joinrel()

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

Definition at line 123 of file joinpath.c.

130 {
131  JoinPathExtraData extra;
132  bool mergejoin_allowed = true;
133  ListCell *lc;
134  Relids joinrelids;
135 
136  /*
137  * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
138  * between child relations, even if there is a SpecialJoinInfo node for
139  * the join between the topmost parents. So, while calculating Relids set
140  * representing the restriction, consider relids of topmost parent of
141  * partitions.
142  */
143  if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
144  joinrelids = joinrel->top_parent_relids;
145  else
146  joinrelids = joinrel->relids;
147 
148  extra.restrictlist = restrictlist;
149  extra.mergeclause_list = NIL;
150  extra.sjinfo = sjinfo;
151  extra.param_source_rels = NULL;
152 
153  /*
154  * See if the inner relation is provably unique for this outer rel.
155  *
156  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
157  * matter since the executor can make the equivalent optimization anyway;
158  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
159  * must be considering a semijoin whose inner side is not provably unique
160  * (else reduce_unique_semijoins would've simplified it), so there's no
161  * point in calling innerrel_is_unique. However, if the LHS covers all of
162  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
163  * because the path produced by create_unique_path will be unique relative
164  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
165  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
166  * letting that value escape this module.
167  */
168  switch (jointype)
169  {
170  case JOIN_SEMI:
171  case JOIN_ANTI:
172 
173  /*
174  * XXX it may be worth proving this to allow a Memoize to be
175  * considered for Nested Loop Semi/Anti Joins.
176  */
177  extra.inner_unique = false; /* well, unproven */
178  break;
179  case JOIN_UNIQUE_INNER:
180  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
181  outerrel->relids);
182  break;
183  case JOIN_UNIQUE_OUTER:
184  extra.inner_unique = innerrel_is_unique(root,
185  joinrel->relids,
186  outerrel->relids,
187  innerrel,
188  JOIN_INNER,
189  restrictlist,
190  false);
191  break;
192  default:
193  extra.inner_unique = innerrel_is_unique(root,
194  joinrel->relids,
195  outerrel->relids,
196  innerrel,
197  jointype,
198  restrictlist,
199  false);
200  break;
201  }
202 
203  /*
204  * Find potential mergejoin clauses. We can skip this if we are not
205  * interested in doing a mergejoin. However, mergejoin may be our only
206  * way of implementing a full outer join, so override enable_mergejoin if
207  * it's a full join.
208  */
209  if (enable_mergejoin || jointype == JOIN_FULL)
211  joinrel,
212  outerrel,
213  innerrel,
214  restrictlist,
215  jointype,
216  &mergejoin_allowed);
217 
218  /*
219  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
220  * for cost estimation. These will be the same for all paths.
221  */
222  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
223  compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
224  jointype, sjinfo, restrictlist,
225  &extra.semifactors);
226 
227  /*
228  * Decide whether it's sensible to generate parameterized paths for this
229  * joinrel, and if so, which relations such paths should require. There
230  * is usually no need to create a parameterized result path unless there
231  * is a join order restriction that prevents joining one of our input rels
232  * directly to the parameter source rel instead of joining to the other
233  * input rel. (But see allow_star_schema_join().) This restriction
234  * reduces the number of parameterized paths we have to deal with at
235  * higher join levels, without compromising the quality of the resulting
236  * plan. We express the restriction as a Relids set that must overlap the
237  * parameterization of any proposed join path.
238  */
239  foreach(lc, root->join_info_list)
240  {
241  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
242 
243  /*
244  * SJ is relevant to this join if we have some part of its RHS
245  * (possibly not all of it), and haven't yet joined to its LHS. (This
246  * test is pretty simplistic, but should be sufficient considering the
247  * join has already been proven legal.) If the SJ is relevant, it
248  * presents constraints for joining to anything not in its RHS.
249  */
250  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
251  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
254  sjinfo2->min_righthand));
255 
256  /* full joins constrain both sides symmetrically */
257  if (sjinfo2->jointype == JOIN_FULL &&
258  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
259  !bms_overlap(joinrelids, sjinfo2->min_righthand))
262  sjinfo2->min_lefthand));
263  }
264 
265  /*
266  * However, when a LATERAL subquery is involved, there will simply not be
267  * any paths for the joinrel that aren't parameterized by whatever the
268  * subquery is parameterized by, unless its parameterization is resolved
269  * within the joinrel. So we might as well allow additional dependencies
270  * on whatever residual lateral dependencies the joinrel will have.
271  */
273  joinrel->lateral_relids);
274 
275  /*
276  * 1. Consider mergejoin paths where both relations must be explicitly
277  * sorted. Skip this if we can't mergejoin.
278  */
279  if (mergejoin_allowed)
280  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
281  jointype, &extra);
282 
283  /*
284  * 2. Consider paths where the outer relation need not be explicitly
285  * sorted. This includes both nestloops and mergejoins where the outer
286  * path is already ordered. Again, skip this if we can't mergejoin.
287  * (That's okay because we know that nestloop can't handle right/full
288  * joins at all, so it wouldn't work in the prohibited cases either.)
289  */
290  if (mergejoin_allowed)
291  match_unsorted_outer(root, joinrel, outerrel, innerrel,
292  jointype, &extra);
293 
294 #ifdef NOT_USED
295 
296  /*
297  * 3. Consider paths where the inner relation need not be explicitly
298  * sorted. This includes mergejoins only (nestloops were already built in
299  * match_unsorted_outer).
300  *
301  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
302  * significant difference between the inner and outer side of a mergejoin,
303  * so match_unsorted_inner creates no paths that aren't equivalent to
304  * those made by match_unsorted_outer when add_paths_to_joinrel() is
305  * invoked with the two rels given in the other order.
306  */
307  if (mergejoin_allowed)
308  match_unsorted_inner(root, joinrel, outerrel, innerrel,
309  jointype, &extra);
310 #endif
311 
312  /*
313  * 4. Consider paths where both outer and inner relations must be hashed
314  * before being joined. As above, disregard enable_hashjoin for full
315  * joins, because there may be no other alternative.
316  */
317  if (enable_hashjoin || jointype == JOIN_FULL)
318  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
319  jointype, &extra);
320 
321  /*
322  * 5. If inner and outer relations are foreign tables (or joins) belonging
323  * to the same server and assigned to the same user to check access
324  * permissions as, give the FDW a chance to push down joins.
325  */
326  if (joinrel->fdwroutine &&
327  joinrel->fdwroutine->GetForeignJoinPaths)
328  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
329  outerrel, innerrel,
330  jointype, &extra);
331 
332  /*
333  * 6. Finally, give extensions a chance to manipulate the path list.
334  */
336  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
337  jointype, &extra);
338 }
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:967
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:953
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:316
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:796
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:4730
bool enable_hashjoin
Definition: costsize.c:147
bool enable_mergejoin
Definition: costsize.c:146
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2223
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1144
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:30
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1968
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1594
@ JOIN_SEMI
Definition: nodes.h:307
@ JOIN_FULL
Definition: nodes.h:295
@ JOIN_INNER
Definition: nodes.h:293
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:314
@ JOIN_UNIQUE_INNER
Definition: nodes.h:315
@ JOIN_ANTI
Definition: nodes.h:308
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:782
#define lfirst(lc)
Definition: pg_list.h:170
#define NIL
Definition: pg_list.h:66
List * mergeclause_list
Definition: pathnodes.h:3019
Relids param_source_rels
Definition: pathnodes.h:3023
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3022
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3021
List * join_info_list
Definition: pathnodes.h:333
Relids all_baserels
Definition: pathnodes.h:257
Relids relids
Definition: pathnodes.h:824
Relids top_parent_relids
Definition: pathnodes.h:957
Relids lateral_relids
Definition: pathnodes.h:866
RelOptKind reloptkind
Definition: pathnodes.h:818
Relids min_righthand
Definition: pathnodes.h:2704
JoinType jointype
Definition: pathnodes.h:2707
Relids min_lefthand
Definition: pathnodes.h:2703

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, 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, JoinPathExtraData::param_source_rels, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.

Referenced by populate_joinrel_with_paths().

◆ allow_star_schema_join()

static bool allow_star_schema_join ( PlannerInfo root,
Relids  outerrelids,
Relids  inner_paramrels 
)
inlinestatic

Definition at line 356 of file joinpath.c.

359 {
360  /*
361  * It's a star-schema case if the outer rel provides some but not all of
362  * the inner rel's parameterization.
363  */
364  return (bms_overlap(inner_paramrels, outerrelids) &&
365  bms_nonempty_difference(inner_paramrels, outerrelids));
366 }
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:548

References bms_nonempty_difference(), and bms_overlap().

Referenced by try_nestloop_path().

◆ clause_sides_match_join()

static bool clause_sides_match_join ( RestrictInfo rinfo,
RelOptInfo outerrel,
RelOptInfo innerrel 
)
inlinestatic

Definition at line 1112 of file joinpath.c.

1114 {
1115  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
1116  bms_is_subset(rinfo->right_relids, innerrel->relids))
1117  {
1118  /* lefthand side is outer */
1119  rinfo->outer_is_left = true;
1120  return true;
1121  }
1122  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
1123  bms_is_subset(rinfo->right_relids, outerrel->relids))
1124  {
1125  /* righthand side is outer */
1126  rinfo->outer_is_left = false;
1127  return true;
1128  }
1129  return false; /* no good for these input relations */
1130 }

References bms_is_subset(), and RelOptInfo::relids.

Referenced by hash_inner_and_outer(), paraminfo_get_equal_hashops(), and select_mergejoin_clauses().

◆ consider_parallel_mergejoin()

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

1851 {
1852  ListCell *lc1;
1853 
1854  /* generate merge join path for each partial outer path */
1855  foreach(lc1, outerrel->partial_pathlist)
1856  {
1857  Path *outerpath = (Path *) lfirst(lc1);
1858  List *merge_pathkeys;
1859 
1860  /*
1861  * Figure out what useful ordering any paths we create will have.
1862  */
1863  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1864  outerpath->pathkeys);
1865 
1866  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1867  extra, false, inner_cheapest_total,
1868  merge_pathkeys, true);
1869  }
1870 }
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:1346
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1109
Definition: pg_list.h:52
List * pathkeys
Definition: pathnodes.h:1552
List * partial_pathlist
Definition: pathnodes.h:853

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

Referenced by match_unsorted_outer().

◆ consider_parallel_nestloop()

static void consider_parallel_nestloop ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1884 of file joinpath.c.

1890 {
1891  JoinType save_jointype = jointype;
1892  ListCell *lc1;
1893 
1894  if (jointype == JOIN_UNIQUE_INNER)
1895  jointype = JOIN_INNER;
1896 
1897  foreach(lc1, outerrel->partial_pathlist)
1898  {
1899  Path *outerpath = (Path *) lfirst(lc1);
1900  List *pathkeys;
1901  ListCell *lc2;
1902 
1903  /* Figure out what useful ordering any paths we create will have. */
1904  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1905  outerpath->pathkeys);
1906 
1907  /*
1908  * Try the cheapest parameterized paths; only those which will produce
1909  * an unparameterized path when joined to this outerrel will survive
1910  * try_partial_nestloop_path. The cheapest unparameterized path is
1911  * also in this list.
1912  */
1913  foreach(lc2, innerrel->cheapest_parameterized_paths)
1914  {
1915  Path *innerpath = (Path *) lfirst(lc2);
1916  Path *mpath;
1917 
1918  /* Can't join to an inner path that is not parallel-safe */
1919  if (!innerpath->parallel_safe)
1920  continue;
1921 
1922  /*
1923  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1924  * cheapest_total_path, and we have to unique-ify it. (We might
1925  * be able to relax this to allow other safe, unparameterized
1926  * inner paths, but right now create_unique_path is not on board
1927  * with that.)
1928  */
1929  if (save_jointype == JOIN_UNIQUE_INNER)
1930  {
1931  if (innerpath != innerrel->cheapest_total_path)
1932  continue;
1933  innerpath = (Path *) create_unique_path(root, innerrel,
1934  innerpath,
1935  extra->sjinfo);
1936  Assert(innerpath);
1937  }
1938 
1939  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1940  pathkeys, jointype, extra);
1941 
1942  /*
1943  * Try generating a memoize path and see if that makes the nested
1944  * loop any cheaper.
1945  */
1946  mpath = get_memoize_path(root, innerrel, outerrel,
1947  innerpath, outerpath, jointype,
1948  extra);
1949  if (mpath != NULL)
1950  try_partial_nestloop_path(root, joinrel, outerpath, mpath,
1951  pathkeys, jointype, extra);
1952  }
1953  }
1954 }
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:503
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:738
Assert(fmt[strlen(fmt) - 1] !='\n')
JoinType
Definition: nodes.h:288
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1652
bool parallel_safe
Definition: pathnodes.h:1542
List * cheapest_parameterized_paths
Definition: pathnodes.h:857
struct Path * cheapest_total_path
Definition: pathnodes.h:855

References Assert(), build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, create_unique_path(), get_memoize_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().

◆ generate_mergejoin_paths()

static void generate_mergejoin_paths ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo innerrel,
Path outerpath,
JoinType  jointype,
JoinPathExtraData extra,
bool  useallclauses,
Path inner_cheapest_total,
List merge_pathkeys,
bool  is_partial 
)
static

Definition at line 1346 of file joinpath.c.

1356 {
1357  List *mergeclauses;
1358  List *innersortkeys;
1359  List *trialsortkeys;
1360  Path *cheapest_startup_inner;
1361  Path *cheapest_total_inner;
1362  JoinType save_jointype = jointype;
1363  int num_sortkeys;
1364  int sortkeycnt;
1365 
1366  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1367  jointype = JOIN_INNER;
1368 
1369  /* Look for useful mergeclauses (if any) */
1370  mergeclauses =
1372  outerpath->pathkeys,
1373  extra->mergeclause_list);
1374 
1375  /*
1376  * Done with this outer path if no chance for a mergejoin.
1377  *
1378  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1379  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1380  * but since mergejoin is our only join type that supports FULL JOIN
1381  * without any join clauses, it's necessary to generate a clauseless
1382  * mergejoin path instead.
1383  */
1384  if (mergeclauses == NIL)
1385  {
1386  if (jointype == JOIN_FULL)
1387  /* okay to try for mergejoin */ ;
1388  else
1389  return;
1390  }
1391  if (useallclauses &&
1392  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1393  return;
1394 
1395  /* Compute the required ordering of the inner path */
1396  innersortkeys = make_inner_pathkeys_for_merge(root,
1397  mergeclauses,
1398  outerpath->pathkeys);
1399 
1400  /*
1401  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1402  * a sort will be needed, only cheapest total cost matters. (But
1403  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1404  * already correctly sorted.)
1405  */
1406  try_mergejoin_path(root,
1407  joinrel,
1408  outerpath,
1409  inner_cheapest_total,
1410  merge_pathkeys,
1411  mergeclauses,
1412  NIL,
1413  innersortkeys,
1414  jointype,
1415  extra,
1416  is_partial);
1417 
1418  /* Can't do anything else if inner path needs to be unique'd */
1419  if (save_jointype == JOIN_UNIQUE_INNER)
1420  return;
1421 
1422  /*
1423  * Look for presorted inner paths that satisfy the innersortkey list ---
1424  * or any truncation thereof, if we are allowed to build a mergejoin using
1425  * a subset of the merge clauses. Here, we consider both cheap startup
1426  * cost and cheap total cost.
1427  *
1428  * Currently we do not consider parameterized inner paths here. This
1429  * interacts with decisions elsewhere that also discriminate against
1430  * mergejoins with parameterized inputs; see comments in
1431  * src/backend/optimizer/README.
1432  *
1433  * As we shorten the sortkey list, we should consider only paths that are
1434  * strictly cheaper than (in particular, not the same as) any path found
1435  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1436  * merge keys than a given path allows (treating the rest as plain
1437  * joinquals), which is unlikely to be a good idea. Also, eliminating
1438  * paths here on the basis of compare_path_costs is a lot cheaper than
1439  * building the mergejoin path only to throw it away.
1440  *
1441  * If inner_cheapest_total is well enough sorted to have not required a
1442  * sort in the path made above, we shouldn't make a duplicate path with
1443  * it, either. We handle that case with the same logic that handles the
1444  * previous consideration, by initializing the variables that track
1445  * cheapest-so-far properly. Note that we do NOT reject
1446  * inner_cheapest_total if we find it matches some shorter set of
1447  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1448  * sorting inner_cheapest_total, whereas we did sort it above, so the
1449  * plans being considered are different.
1450  */
1451  if (pathkeys_contained_in(innersortkeys,
1452  inner_cheapest_total->pathkeys))
1453  {
1454  /* inner_cheapest_total didn't require a sort */
1455  cheapest_startup_inner = inner_cheapest_total;
1456  cheapest_total_inner = inner_cheapest_total;
1457  }
1458  else
1459  {
1460  /* it did require a sort, at least for the full set of keys */
1461  cheapest_startup_inner = NULL;
1462  cheapest_total_inner = NULL;
1463  }
1464  num_sortkeys = list_length(innersortkeys);
1465  if (num_sortkeys > 1 && !useallclauses)
1466  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1467  else
1468  trialsortkeys = innersortkeys; /* won't really truncate */
1469 
1470  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1471  {
1472  Path *innerpath;
1473  List *newclauses = NIL;
1474 
1475  /*
1476  * Look for an inner path ordered well enough for the first
1477  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1478  * destructively, which is why we made a copy...
1479  */
1480  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1481  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1482  trialsortkeys,
1483  NULL,
1484  TOTAL_COST,
1485  is_partial);
1486  if (innerpath != NULL &&
1487  (cheapest_total_inner == NULL ||
1488  compare_path_costs(innerpath, cheapest_total_inner,
1489  TOTAL_COST) < 0))
1490  {
1491  /* Found a cheap (or even-cheaper) sorted path */
1492  /* Select the right mergeclauses, if we didn't already */
1493  if (sortkeycnt < num_sortkeys)
1494  {
1495  newclauses =
1497  mergeclauses,
1498  trialsortkeys);
1499  Assert(newclauses != NIL);
1500  }
1501  else
1502  newclauses = mergeclauses;
1503  try_mergejoin_path(root,
1504  joinrel,
1505  outerpath,
1506  innerpath,
1507  merge_pathkeys,
1508  newclauses,
1509  NIL,
1510  NIL,
1511  jointype,
1512  extra,
1513  is_partial);
1514  cheapest_total_inner = innerpath;
1515  }
1516  /* Same on the basis of cheapest startup cost ... */
1517  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1518  trialsortkeys,
1519  NULL,
1520  STARTUP_COST,
1521  is_partial);
1522  if (innerpath != NULL &&
1523  (cheapest_startup_inner == NULL ||
1524  compare_path_costs(innerpath, cheapest_startup_inner,
1525  STARTUP_COST) < 0))
1526  {
1527  /* Found a cheap (or even-cheaper) sorted path */
1528  if (innerpath != cheapest_total_inner)
1529  {
1530  /*
1531  * Avoid rebuilding clause list if we already made one; saves
1532  * memory in big join trees...
1533  */
1534  if (newclauses == NIL)
1535  {
1536  if (sortkeycnt < num_sortkeys)
1537  {
1538  newclauses =
1540  mergeclauses,
1541  trialsortkeys);
1542  Assert(newclauses != NIL);
1543  }
1544  else
1545  newclauses = mergeclauses;
1546  }
1547  try_mergejoin_path(root,
1548  joinrel,
1549  outerpath,
1550  innerpath,
1551  merge_pathkeys,
1552  newclauses,
1553  NIL,
1554  NIL,
1555  jointype,
1556  extra,
1557  is_partial);
1558  }
1559  cheapest_startup_inner = innerpath;
1560  }
1561 
1562  /*
1563  * Don't consider truncated sortkeys if we need all clauses.
1564  */
1565  if (useallclauses)
1566  break;
1567  }
1568 }
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:820
List * list_truncate(List *list, int new_size)
Definition: list.c:630
List * list_copy(const List *oldlist)
Definition: list.c:1572
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1600
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:426
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1289
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1703
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:346
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71
@ TOTAL_COST
Definition: pathnodes.h:38
@ STARTUP_COST
Definition: pathnodes.h:38
static int list_length(const List *l)
Definition: pg_list.h:150
List * pathlist
Definition: pathnodes.h:851

References Assert(), compare_path_costs(), find_mergeclauses_for_outer_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, Path::pathkeys, pathkeys_contained_in(), RelOptInfo::pathlist, STARTUP_COST, TOTAL_COST, trim_mergeclauses_for_inner_pathkeys(), and try_mergejoin_path().

Referenced by consider_parallel_mergejoin(), and match_unsorted_outer().

◆ get_memoize_path()

static Path* get_memoize_path ( PlannerInfo root,
RelOptInfo innerrel,
RelOptInfo outerrel,
Path inner_path,
Path outer_path,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 503 of file joinpath.c.

507 {
508  List *param_exprs;
509  List *hash_operators;
510  ListCell *lc;
511  bool binary_mode;
512 
513  /* Obviously not if it's disabled */
514  if (!enable_memoize)
515  return NULL;
516 
517  /*
518  * We can safely not bother with all this unless we expect to perform more
519  * than one inner scan. The first scan is always going to be a cache
520  * miss. This would likely fail later anyway based on costs, so this is
521  * really just to save some wasted effort.
522  */
523  if (outer_path->parent->rows < 2)
524  return NULL;
525 
526  /*
527  * We can only have a memoize node when there's some kind of cache key,
528  * either parameterized path clauses or lateral Vars. No cache key sounds
529  * more like something a Materialize node might be more useful for.
530  */
531  if ((inner_path->param_info == NULL ||
532  inner_path->param_info->ppi_clauses == NIL) &&
533  innerrel->lateral_vars == NIL)
534  return NULL;
535 
536  /*
537  * Currently we don't do this for SEMI and ANTI joins unless they're
538  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
539  * don't scan the inner node to completion, which will mean memoize cannot
540  * mark the cache entry as complete.
541  *
542  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
543  * = true. Should we? See add_paths_to_joinrel()
544  */
545  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
546  jointype == JOIN_ANTI))
547  return NULL;
548 
549  /*
550  * Memoize normally marks cache entries as complete when it runs out of
551  * tuples to read from its subplan. However, with unique joins, Nested
552  * Loop will skip to the next outer tuple after finding the first matching
553  * inner tuple. This means that we may not read the inner side of the
554  * join to completion which leaves no opportunity to mark the cache entry
555  * as complete. To work around that, when the join is unique we
556  * automatically mark cache entries as complete after fetching the first
557  * tuple. This works when the entire join condition is parameterized.
558  * Otherwise, when the parameterization is only a subset of the join
559  * condition, we can't be sure which part of it causes the join to be
560  * unique. This means there are no guarantees that only 1 tuple will be
561  * read. We cannot mark the cache entry as complete after reading the
562  * first tuple without that guarantee. This means the scope of Memoize
563  * node's usefulness is limited to only outer rows that have no join
564  * partner as this is the only case where Nested Loop would exhaust the
565  * inner scan of a unique join. Since the scope is limited to that, we
566  * just don't bother making a memoize path in this case.
567  *
568  * Lateral vars needn't be considered here as they're not considered when
569  * determining if the join is unique.
570  *
571  * XXX this could be enabled if the remaining join quals were made part of
572  * the inner scan's filter instead of the join filter. Maybe it's worth
573  * considering doing that?
574  */
575  if (extra->inner_unique &&
576  (inner_path->param_info == NULL ||
577  list_length(inner_path->param_info->ppi_clauses) <
578  list_length(extra->restrictlist)))
579  return NULL;
580 
581  /*
582  * We can't use a memoize node if there are volatile functions in the
583  * inner rel's target list or restrict list. A cache hit could reduce the
584  * number of calls to these functions.
585  */
586  if (contain_volatile_functions((Node *) innerrel->reltarget))
587  return NULL;
588 
589  foreach(lc, innerrel->baserestrictinfo)
590  {
591  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
592 
593  if (contain_volatile_functions((Node *) rinfo))
594  return NULL;
595  }
596 
597  /* Check if we have hash ops for each parameter to the path */
599  inner_path->param_info,
600  outerrel->top_parent ?
601  outerrel->top_parent : outerrel,
602  innerrel,
603  &param_exprs,
604  &hash_operators,
605  &binary_mode))
606  {
607  return (Path *) create_memoize_path(root,
608  innerrel,
609  inner_path,
610  param_exprs,
611  hash_operators,
612  extra->inner_unique,
613  binary_mode,
614  outer_path->rows);
615  }
616 
617  return NULL;
618 }
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:448
bool enable_memoize
Definition: costsize.c:145
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List **param_exprs, List **operators, bool *binary_mode)
Definition: joinpath.c:378
MemoizePath * create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, bool binary_mode, double calls)
Definition: pathnode.c:1596
Definition: nodes.h:118
Cardinality rows
Definition: pathnodes.h:1547
List * baserestrictinfo
Definition: pathnodes.h:933
struct PathTarget * reltarget
Definition: pathnodes.h:846
List * lateral_vars
Definition: pathnodes.h:885

References RelOptInfo::baserestrictinfo, contain_volatile_functions(), create_memoize_path(), enable_memoize, JoinPathExtraData::inner_unique, JOIN_ANTI, JOIN_SEMI, RelOptInfo::lateral_vars, lfirst, list_length(), NIL, paraminfo_get_equal_hashops(), RelOptInfo::reltarget, JoinPathExtraData::restrictlist, and Path::rows.

Referenced by consider_parallel_nestloop(), and match_unsorted_outer().

◆ hash_inner_and_outer()

static void hash_inner_and_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1968 of file joinpath.c.

1974 {
1975  JoinType save_jointype = jointype;
1976  bool isouterjoin = IS_OUTER_JOIN(jointype);
1977  List *hashclauses;
1978  ListCell *l;
1979 
1980  /*
1981  * We need to build only one hashclauses list for any given pair of outer
1982  * and inner relations; all of the hashable clauses will be used as keys.
1983  *
1984  * Scan the join's restrictinfo list to find hashjoinable clauses that are
1985  * usable with this pair of sub-relations.
1986  */
1987  hashclauses = NIL;
1988  foreach(l, extra->restrictlist)
1989  {
1990  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1991 
1992  /*
1993  * If processing an outer join, only use its own join clauses for
1994  * hashing. For inner joins we need not be so picky.
1995  */
1996  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
1997  continue;
1998 
1999  if (!restrictinfo->can_join ||
2000  restrictinfo->hashjoinoperator == InvalidOid)
2001  continue; /* not hashjoinable */
2002 
2003  /*
2004  * Check if clause has the form "outer op inner" or "inner op outer".
2005  */
2006  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2007  continue; /* no good for these input relations */
2008 
2009  hashclauses = lappend(hashclauses, restrictinfo);
2010  }
2011 
2012  /* If we found any usable hashclauses, make paths */
2013  if (hashclauses)
2014  {
2015  /*
2016  * We consider both the cheapest-total-cost and cheapest-startup-cost
2017  * outer paths. There's no need to consider any but the
2018  * cheapest-total-cost inner path, however.
2019  */
2020  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2021  Path *cheapest_total_outer = outerrel->cheapest_total_path;
2022  Path *cheapest_total_inner = innerrel->cheapest_total_path;
2023 
2024  /*
2025  * If either cheapest-total path is parameterized by the other rel, we
2026  * can't use a hashjoin. (There's no use looking for alternative
2027  * input paths, since these should already be the least-parameterized
2028  * available paths.)
2029  */
2030  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2031  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2032  return;
2033 
2034  /* Unique-ify if need be; we ignore parameterized possibilities */
2035  if (jointype == JOIN_UNIQUE_OUTER)
2036  {
2037  cheapest_total_outer = (Path *)
2038  create_unique_path(root, outerrel,
2039  cheapest_total_outer, extra->sjinfo);
2040  Assert(cheapest_total_outer);
2041  jointype = JOIN_INNER;
2042  try_hashjoin_path(root,
2043  joinrel,
2044  cheapest_total_outer,
2045  cheapest_total_inner,
2046  hashclauses,
2047  jointype,
2048  extra);
2049  /* no possibility of cheap startup here */
2050  }
2051  else if (jointype == JOIN_UNIQUE_INNER)
2052  {
2053  cheapest_total_inner = (Path *)
2054  create_unique_path(root, innerrel,
2055  cheapest_total_inner, extra->sjinfo);
2056  Assert(cheapest_total_inner);
2057  jointype = JOIN_INNER;
2058  try_hashjoin_path(root,
2059  joinrel,
2060  cheapest_total_outer,
2061  cheapest_total_inner,
2062  hashclauses,
2063  jointype,
2064  extra);
2065  if (cheapest_startup_outer != NULL &&
2066  cheapest_startup_outer != cheapest_total_outer)
2067  try_hashjoin_path(root,
2068  joinrel,
2069  cheapest_startup_outer,
2070  cheapest_total_inner,
2071  hashclauses,
2072  jointype,
2073  extra);
2074  }
2075  else
2076  {
2077  /*
2078  * For other jointypes, we consider the cheapest startup outer
2079  * together with the cheapest total inner, and then consider
2080  * pairings of cheapest-total paths including parameterized ones.
2081  * There is no use in generating parameterized paths on the basis
2082  * of possibly cheap startup cost, so this is sufficient.
2083  */
2084  ListCell *lc1;
2085  ListCell *lc2;
2086 
2087  if (cheapest_startup_outer != NULL)
2088  try_hashjoin_path(root,
2089  joinrel,
2090  cheapest_startup_outer,
2091  cheapest_total_inner,
2092  hashclauses,
2093  jointype,
2094  extra);
2095 
2096  foreach(lc1, outerrel->cheapest_parameterized_paths)
2097  {
2098  Path *outerpath = (Path *) lfirst(lc1);
2099 
2100  /*
2101  * We cannot use an outer path that is parameterized by the
2102  * inner rel.
2103  */
2104  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2105  continue;
2106 
2107  foreach(lc2, innerrel->cheapest_parameterized_paths)
2108  {
2109  Path *innerpath = (Path *) lfirst(lc2);
2110 
2111  /*
2112  * We cannot use an inner path that is parameterized by
2113  * the outer rel, either.
2114  */
2115  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2116  continue;
2117 
2118  if (outerpath == cheapest_startup_outer &&
2119  innerpath == cheapest_total_inner)
2120  continue; /* already tried it */
2121 
2122  try_hashjoin_path(root,
2123  joinrel,
2124  outerpath,
2125  innerpath,
2126  hashclauses,
2127  jointype,
2128  extra);
2129  }
2130  }
2131  }
2132 
2133  /*
2134  * If the joinrel is parallel-safe, we may be able to consider a
2135  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2136  * because the outer path will be partial, and therefore we won't be
2137  * able to properly guarantee uniqueness. Similarly, we can't handle
2138  * JOIN_FULL and JOIN_RIGHT, because they can produce false null
2139  * extended rows. Also, the resulting path must not be parameterized.
2140  * We would be able to support JOIN_FULL and JOIN_RIGHT for Parallel
2141  * Hash, since in that case we're back to a single hash table with a
2142  * single set of match bits for each batch, but that will require
2143  * figuring out a deadlock-free way to wait for the probe to finish.
2144  */
2145  if (joinrel->consider_parallel &&
2146  save_jointype != JOIN_UNIQUE_OUTER &&
2147  save_jointype != JOIN_FULL &&
2148  save_jointype != JOIN_RIGHT &&
2149  outerrel->partial_pathlist != NIL &&
2150  bms_is_empty(joinrel->lateral_relids))
2151  {
2152  Path *cheapest_partial_outer;
2153  Path *cheapest_partial_inner = NULL;
2154  Path *cheapest_safe_inner = NULL;
2155 
2156  cheapest_partial_outer =
2157  (Path *) linitial(outerrel->partial_pathlist);
2158 
2159  /*
2160  * Can we use a partial inner plan too, so that we can build a
2161  * shared hash table in parallel? We can't handle
2162  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2163  */
2164  if (innerrel->partial_pathlist != NIL &&
2165  save_jointype != JOIN_UNIQUE_INNER &&
2167  {
2168  cheapest_partial_inner =
2169  (Path *) linitial(innerrel->partial_pathlist);
2170  try_partial_hashjoin_path(root, joinrel,
2171  cheapest_partial_outer,
2172  cheapest_partial_inner,
2173  hashclauses, jointype, extra,
2174  true /* parallel_hash */ );
2175  }
2176 
2177  /*
2178  * Normally, given that the joinrel is parallel-safe, the cheapest
2179  * total inner path will also be parallel-safe, but if not, we'll
2180  * have to search for the cheapest safe, unparameterized inner
2181  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2182  * inner path.
2183  */
2184  if (cheapest_total_inner->parallel_safe)
2185  cheapest_safe_inner = cheapest_total_inner;
2186  else if (save_jointype != JOIN_UNIQUE_INNER)
2187  cheapest_safe_inner =
2189 
2190  if (cheapest_safe_inner != NULL)
2191  try_partial_hashjoin_path(root, joinrel,
2192  cheapest_partial_outer,
2193  cheapest_safe_inner,
2194  hashclauses, jointype, extra,
2195  false /* parallel_hash */ );
2196  }
2197  }
2198 }
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
bool enable_parallel_hash
Definition: costsize.c:152
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:985
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1112
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:42
static void try_partial_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra, bool parallel_hash)
Definition: joinpath.c:1051
List * lappend(List *list, void *datum)
Definition: list.c:338
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:336
@ JOIN_RIGHT
Definition: nodes.h:296
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:504
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2569
#define linitial(l)
Definition: pg_list.h:176
#define InvalidOid
Definition: postgres_ext.h:36
bool consider_parallel
Definition: pathnodes.h:840
struct Path * cheapest_startup_path
Definition: pathnodes.h:854

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

Referenced by add_paths_to_joinrel().

◆ match_unsorted_outer()

static void match_unsorted_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1594 of file joinpath.c.

1600 {
1601  JoinType save_jointype = jointype;
1602  bool nestjoinOK;
1603  bool useallclauses;
1604  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1605  Path *matpath = NULL;
1606  ListCell *lc1;
1607 
1608  /*
1609  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1610  * are doing a right or full mergejoin, we must use *all* the mergeclauses
1611  * as join clauses, else we will not have a valid plan. (Although these
1612  * two flags are currently inverses, keep them separate for clarity and
1613  * possible future changes.)
1614  */
1615  switch (jointype)
1616  {
1617  case JOIN_INNER:
1618  case JOIN_LEFT:
1619  case JOIN_SEMI:
1620  case JOIN_ANTI:
1621  nestjoinOK = true;
1622  useallclauses = false;
1623  break;
1624  case JOIN_RIGHT:
1625  case JOIN_FULL:
1626  nestjoinOK = false;
1627  useallclauses = true;
1628  break;
1629  case JOIN_UNIQUE_OUTER:
1630  case JOIN_UNIQUE_INNER:
1631  jointype = JOIN_INNER;
1632  nestjoinOK = true;
1633  useallclauses = false;
1634  break;
1635  default:
1636  elog(ERROR, "unrecognized join type: %d",
1637  (int) jointype);
1638  nestjoinOK = false; /* keep compiler quiet */
1639  useallclauses = false;
1640  break;
1641  }
1642 
1643  /*
1644  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1645  * we will consider it below as a member of cheapest_parameterized_paths,
1646  * but the other possibilities considered in this routine aren't usable.
1647  */
1648  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1649  inner_cheapest_total = NULL;
1650 
1651  /*
1652  * If we need to unique-ify the inner path, we will consider only the
1653  * cheapest-total inner.
1654  */
1655  if (save_jointype == JOIN_UNIQUE_INNER)
1656  {
1657  /* No way to do this with an inner path parameterized by outer rel */
1658  if (inner_cheapest_total == NULL)
1659  return;
1660  inner_cheapest_total = (Path *)
1661  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1662  Assert(inner_cheapest_total);
1663  }
1664  else if (nestjoinOK)
1665  {
1666  /*
1667  * Consider materializing the cheapest inner path, unless
1668  * enable_material is off or the path in question materializes its
1669  * output anyway.
1670  */
1671  if (enable_material && inner_cheapest_total != NULL &&
1672  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1673  matpath = (Path *)
1674  create_material_path(innerrel, inner_cheapest_total);
1675  }
1676 
1677  foreach(lc1, outerrel->pathlist)
1678  {
1679  Path *outerpath = (Path *) lfirst(lc1);
1680  List *merge_pathkeys;
1681 
1682  /*
1683  * We cannot use an outer path that is parameterized by the inner rel.
1684  */
1685  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1686  continue;
1687 
1688  /*
1689  * If we need to unique-ify the outer path, it's pointless to consider
1690  * any but the cheapest outer. (XXX we don't consider parameterized
1691  * outers, nor inners, for unique-ified cases. Should we?)
1692  */
1693  if (save_jointype == JOIN_UNIQUE_OUTER)
1694  {
1695  if (outerpath != outerrel->cheapest_total_path)
1696  continue;
1697  outerpath = (Path *) create_unique_path(root, outerrel,
1698  outerpath, extra->sjinfo);
1699  Assert(outerpath);
1700  }
1701 
1702  /*
1703  * The result will have this sort order (even if it is implemented as
1704  * a nestloop, and even if some of the mergeclauses are implemented by
1705  * qpquals rather than as true mergeclauses):
1706  */
1707  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1708  outerpath->pathkeys);
1709 
1710  if (save_jointype == JOIN_UNIQUE_INNER)
1711  {
1712  /*
1713  * Consider nestloop join, but only with the unique-ified cheapest
1714  * inner path
1715  */
1716  try_nestloop_path(root,
1717  joinrel,
1718  outerpath,
1719  inner_cheapest_total,
1720  merge_pathkeys,
1721  jointype,
1722  extra);
1723  }
1724  else if (nestjoinOK)
1725  {
1726  /*
1727  * Consider nestloop joins using this outer path and various
1728  * available paths for the inner relation. We consider the
1729  * cheapest-total paths for each available parameterization of the
1730  * inner relation, including the unparameterized case.
1731  */
1732  ListCell *lc2;
1733 
1734  foreach(lc2, innerrel->cheapest_parameterized_paths)
1735  {
1736  Path *innerpath = (Path *) lfirst(lc2);
1737  Path *mpath;
1738 
1739  try_nestloop_path(root,
1740  joinrel,
1741  outerpath,
1742  innerpath,
1743  merge_pathkeys,
1744  jointype,
1745  extra);
1746 
1747  /*
1748  * Try generating a memoize path and see if that makes the
1749  * nested loop any cheaper.
1750  */
1751  mpath = get_memoize_path(root, innerrel, outerrel,
1752  innerpath, outerpath, jointype,
1753  extra);
1754  if (mpath != NULL)
1755  try_nestloop_path(root,
1756  joinrel,
1757  outerpath,
1758  mpath,
1759  merge_pathkeys,
1760  jointype,
1761  extra);
1762  }
1763 
1764  /* Also consider materialized form of the cheapest inner path */
1765  if (matpath != NULL)
1766  try_nestloop_path(root,
1767  joinrel,
1768  outerpath,
1769  matpath,
1770  merge_pathkeys,
1771  jointype,
1772  extra);
1773  }
1774 
1775  /* Can't do anything else if outer path needs to be unique'd */
1776  if (save_jointype == JOIN_UNIQUE_OUTER)
1777  continue;
1778 
1779  /* Can't do anything else if inner rel is parameterized by outer */
1780  if (inner_cheapest_total == NULL)
1781  continue;
1782 
1783  /* Generate merge join paths */
1784  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1785  save_jointype, extra, useallclauses,
1786  inner_cheapest_total, merge_pathkeys,
1787  false);
1788  }
1789 
1790  /*
1791  * Consider partial nestloop and mergejoin plan if outerrel has any
1792  * partial path and the joinrel is parallel-safe. However, we can't
1793  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1794  * therefore we won't be able to properly guarantee uniqueness. Nor can
1795  * we handle joins needing lateral rels, since partial paths must not be
1796  * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1797  * because they can produce false null extended rows.
1798  */
1799  if (joinrel->consider_parallel &&
1800  save_jointype != JOIN_UNIQUE_OUTER &&
1801  save_jointype != JOIN_FULL &&
1802  save_jointype != JOIN_RIGHT &&
1803  outerrel->partial_pathlist != NIL &&
1804  bms_is_empty(joinrel->lateral_relids))
1805  {
1806  if (nestjoinOK)
1807  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1808  save_jointype, extra);
1809 
1810  /*
1811  * If inner_cheapest_total is NULL or non parallel-safe then find the
1812  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1813  * can't use any alternative inner path.
1814  */
1815  if (inner_cheapest_total == NULL ||
1816  !inner_cheapest_total->parallel_safe)
1817  {
1818  if (save_jointype == JOIN_UNIQUE_INNER)
1819  return;
1820 
1821  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1822  }
1823 
1824  if (inner_cheapest_total)
1825  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1826  save_jointype, extra,
1827  inner_cheapest_total);
1828  }
1829 }
bool enable_material
Definition: costsize.c:144
#define ERROR
Definition: elog.h:39
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:637
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:626
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1884
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1844
@ JOIN_LEFT
Definition: nodes.h:294
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1564
NodeTag pathtype
Definition: pathnodes.h:1513

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(), get_memoize_path(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_LEFT, JOIN_RIGHT, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lfirst, NIL, 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().

◆ paraminfo_get_equal_hashops()

static bool paraminfo_get_equal_hashops ( PlannerInfo root,
ParamPathInfo param_info,
RelOptInfo outerrel,
RelOptInfo innerrel,
List **  param_exprs,
List **  operators,
bool binary_mode 
)
static

Definition at line 378 of file joinpath.c.

383 {
384  ListCell *lc;
385 
386  *param_exprs = NIL;
387  *operators = NIL;
388  *binary_mode = false;
389 
390  if (param_info != NULL)
391  {
392  List *clauses = param_info->ppi_clauses;
393 
394  foreach(lc, clauses)
395  {
396  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
397  OpExpr *opexpr;
398  Node *expr;
399  Oid hasheqoperator;
400 
401  opexpr = (OpExpr *) rinfo->clause;
402 
403  /*
404  * Bail if the rinfo is not compatible. We need a join OpExpr
405  * with 2 args.
406  */
407  if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
408  !clause_sides_match_join(rinfo, outerrel, innerrel))
409  {
410  list_free(*operators);
411  list_free(*param_exprs);
412  return false;
413  }
414 
415  if (rinfo->outer_is_left)
416  {
417  expr = (Node *) linitial(opexpr->args);
418  hasheqoperator = rinfo->left_hasheqoperator;
419  }
420  else
421  {
422  expr = (Node *) lsecond(opexpr->args);
423  hasheqoperator = rinfo->right_hasheqoperator;
424  }
425 
426  /* can't do memoize if we can't hash the outer type */
427  if (!OidIsValid(hasheqoperator))
428  {
429  list_free(*operators);
430  list_free(*param_exprs);
431  return false;
432  }
433 
434  *operators = lappend_oid(*operators, hasheqoperator);
435  *param_exprs = lappend(*param_exprs, expr);
436 
437  /*
438  * When the join operator is not hashable then it's possible that
439  * the operator will be able to distinguish something that the
440  * hash equality operator could not. For example with floating
441  * point types -0.0 and +0.0 are classed as equal by the hash
442  * function and equality function, but some other operator may be
443  * able to tell those values apart. This means that we must put
444  * memoize into binary comparison mode so that it does bit-by-bit
445  * comparisons rather than a "logical" comparison as it would
446  * using the hash equality operator.
447  */
448  if (!OidIsValid(rinfo->hashjoinoperator))
449  *binary_mode = true;
450  }
451  }
452 
453  /* Now add any lateral vars to the cache key too */
454  foreach(lc, innerrel->lateral_vars)
455  {
456  Node *expr = (Node *) lfirst(lc);
457  TypeCacheEntry *typentry;
458 
459  /* Reject if there are any volatile functions */
460  if (contain_volatile_functions(expr))
461  {
462  list_free(*operators);
463  list_free(*param_exprs);
464  return false;
465  }
466 
467  typentry = lookup_type_cache(exprType(expr),
469 
470  /* can't use a memoize node without a valid hash equals operator */
471  if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
472  {
473  list_free(*operators);
474  list_free(*param_exprs);
475  return false;
476  }
477 
478  *operators = lappend_oid(*operators, typentry->eq_opr);
479  *param_exprs = lappend(*param_exprs, expr);
480 
481  /*
482  * We must go into binary mode as we don't have too much of an idea of
483  * how these lateral Vars are being used. See comment above when we
484  * set *binary_mode for the non-lateral Var case. This could be
485  * relaxed a bit if we had the RestrictInfos and knew the operators
486  * being used, however for cases like Vars that are arguments to
487  * functions we must operate in binary mode as we don't have
488  * visibility into what the function is doing with the Vars.
489  */
490  *binary_mode = true;
491  }
492 
493  /* We're okay to use memoize */
494  return true;
495 }
#define OidIsValid(objectId)
Definition: c.h:711
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
List * lappend_oid(List *list, Oid datum)
Definition: list.c:374
void list_free(List *list)
Definition: list.c:1545
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:43
#define IsA(nodeptr, _type_)
Definition: nodes.h:168
#define lsecond(l)
Definition: pg_list.h:181
unsigned int Oid
Definition: postgres_ext.h:31
List * args
Definition: primnodes.h:666
List * ppi_clauses
Definition: pathnodes.h:1469
Expr * clause
Definition: pathnodes.h:2435
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:339
#define TYPECACHE_EQ_OPR
Definition: typcache.h:136
#define TYPECACHE_HASH_PROC
Definition: typcache.h:140

References OpExpr::args, RestrictInfo::clause, clause_sides_match_join(), contain_volatile_functions(), TypeCacheEntry::eq_opr, exprType(), TypeCacheEntry::hash_proc, if(), IsA, lappend(), lappend_oid(), RelOptInfo::lateral_vars, lfirst, linitial, list_free(), list_length(), lookup_type_cache(), lsecond, NIL, OidIsValid, ParamPathInfo::ppi_clauses, TYPECACHE_EQ_OPR, and TYPECACHE_HASH_PROC.

Referenced by get_memoize_path().

◆ select_mergejoin_clauses()

static List * select_mergejoin_clauses ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
List restrictlist,
JoinType  jointype,
bool mergejoin_allowed 
)
static

Definition at line 2223 of file joinpath.c.

2230 {
2231  List *result_list = NIL;
2232  bool isouterjoin = IS_OUTER_JOIN(jointype);
2233  bool have_nonmergeable_joinclause = false;
2234  ListCell *l;
2235 
2236  foreach(l, restrictlist)
2237  {
2238  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2239 
2240  /*
2241  * If processing an outer join, only use its own join clauses in the
2242  * merge. For inner joins we can use pushed-down clauses too. (Note:
2243  * we don't set have_nonmergeable_joinclause here because pushed-down
2244  * clauses will become otherquals not joinquals.)
2245  */
2246  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2247  continue;
2248 
2249  /* Check that clause is a mergeable operator clause */
2250  if (!restrictinfo->can_join ||
2251  restrictinfo->mergeopfamilies == NIL)
2252  {
2253  /*
2254  * The executor can handle extra joinquals that are constants, but
2255  * not anything else, when doing right/full merge join. (The
2256  * reason to support constants is so we can do FULL JOIN ON
2257  * FALSE.)
2258  */
2259  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2260  have_nonmergeable_joinclause = true;
2261  continue; /* not mergejoinable */
2262  }
2263 
2264  /*
2265  * Check if clause has the form "outer op inner" or "inner op outer".
2266  */
2267  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2268  {
2269  have_nonmergeable_joinclause = true;
2270  continue; /* no good for these input relations */
2271  }
2272 
2273  /*
2274  * Insist that each side have a non-redundant eclass. This
2275  * restriction is needed because various bits of the planner expect
2276  * that each clause in a merge be associable with some pathkey in a
2277  * canonical pathkey list, but redundant eclasses can't appear in
2278  * canonical sort orderings. (XXX it might be worth relaxing this,
2279  * but not enough time to address it for 8.3.)
2280  *
2281  * Note: it would be bad if this condition failed for an otherwise
2282  * mergejoinable FULL JOIN clause, since that would result in
2283  * undesirable planner failure. I believe that is not possible
2284  * however; a variable involved in a full join could only appear in
2285  * below_outer_join eclasses, which aren't considered redundant.
2286  *
2287  * This case *can* happen for left/right join clauses: the outer-side
2288  * variable could be equated to a constant. Because we will propagate
2289  * that constant across the join clause, the loss of ability to do a
2290  * mergejoin is not really all that big a deal, and so it's not clear
2291  * that improving this is important.
2292  */
2293  update_mergeclause_eclasses(root, restrictinfo);
2294 
2295  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2296  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2297  {
2298  have_nonmergeable_joinclause = true;
2299  continue; /* can't handle redundant eclasses */
2300  }
2301 
2302  result_list = lappend(result_list, restrictinfo);
2303  }
2304 
2305  /*
2306  * Report whether mergejoin is allowed (see comment at top of function).
2307  */
2308  switch (jointype)
2309  {
2310  case JOIN_RIGHT:
2311  case JOIN_FULL:
2312  *mergejoin_allowed = !have_nonmergeable_joinclause;
2313  break;
2314  default:
2315  *mergejoin_allowed = true;
2316  break;
2317  }
2318 
2319  return result_list;
2320 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1255
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1316

References RestrictInfo::clause, clause_sides_match_join(), EC_MUST_BE_REDUNDANT, IS_OUTER_JOIN, IsA, JOIN_FULL, JOIN_RIGHT, lappend(), lfirst, NIL, RelOptInfo::relids, RINFO_IS_PUSHED_DOWN, and update_mergeclause_eclasses().

Referenced by add_paths_to_joinrel().

◆ sort_inner_and_outer()

static void sort_inner_and_outer ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 1144 of file joinpath.c.

1150 {
1151  JoinType save_jointype = jointype;
1152  Path *outer_path;
1153  Path *inner_path;
1154  Path *cheapest_partial_outer = NULL;
1155  Path *cheapest_safe_inner = NULL;
1156  List *all_pathkeys;
1157  ListCell *l;
1158 
1159  /*
1160  * We only consider the cheapest-total-cost input paths, since we are
1161  * assuming here that a sort is required. We will consider
1162  * cheapest-startup-cost input paths later, and only if they don't need a
1163  * sort.
1164  *
1165  * This function intentionally does not consider parameterized input
1166  * paths, except when the cheapest-total is parameterized. If we did so,
1167  * we'd have a combinatorial explosion of mergejoin paths of dubious
1168  * value. This interacts with decisions elsewhere that also discriminate
1169  * against mergejoins with parameterized inputs; see comments in
1170  * src/backend/optimizer/README.
1171  */
1172  outer_path = outerrel->cheapest_total_path;
1173  inner_path = innerrel->cheapest_total_path;
1174 
1175  /*
1176  * If either cheapest-total path is parameterized by the other rel, we
1177  * can't use a mergejoin. (There's no use looking for alternative input
1178  * paths, since these should already be the least-parameterized available
1179  * paths.)
1180  */
1181  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1182  PATH_PARAM_BY_REL(inner_path, outerrel))
1183  return;
1184 
1185  /*
1186  * If unique-ification is requested, do it and then handle as a plain
1187  * inner join.
1188  */
1189  if (jointype == JOIN_UNIQUE_OUTER)
1190  {
1191  outer_path = (Path *) create_unique_path(root, outerrel,
1192  outer_path, extra->sjinfo);
1193  Assert(outer_path);
1194  jointype = JOIN_INNER;
1195  }
1196  else if (jointype == JOIN_UNIQUE_INNER)
1197  {
1198  inner_path = (Path *) create_unique_path(root, innerrel,
1199  inner_path, extra->sjinfo);
1200  Assert(inner_path);
1201  jointype = JOIN_INNER;
1202  }
1203 
1204  /*
1205  * If the joinrel is parallel-safe, we may be able to consider a partial
1206  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1207  * outer path will be partial, and therefore we won't be able to properly
1208  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
1209  * JOIN_RIGHT, because they can produce false null extended rows. Also,
1210  * the resulting path must not be parameterized.
1211  */
1212  if (joinrel->consider_parallel &&
1213  save_jointype != JOIN_UNIQUE_OUTER &&
1214  save_jointype != JOIN_FULL &&
1215  save_jointype != JOIN_RIGHT &&
1216  outerrel->partial_pathlist != NIL &&
1217  bms_is_empty(joinrel->lateral_relids))
1218  {
1219  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1220 
1221  if (inner_path->parallel_safe)
1222  cheapest_safe_inner = inner_path;
1223  else if (save_jointype != JOIN_UNIQUE_INNER)
1224  cheapest_safe_inner =
1226  }
1227 
1228  /*
1229  * Each possible ordering of the available mergejoin clauses will generate
1230  * a differently-sorted result path at essentially the same cost. We have
1231  * no basis for choosing one over another at this level of joining, but
1232  * some sort orders may be more useful than others for higher-level
1233  * mergejoins, so it's worth considering multiple orderings.
1234  *
1235  * Actually, it's not quite true that every mergeclause ordering will
1236  * generate a different path order, because some of the clauses may be
1237  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1238  * what we do is convert the mergeclause list to a list of canonical
1239  * pathkeys, and then consider different orderings of the pathkeys.
1240  *
1241  * Generating a path for *every* permutation of the pathkeys doesn't seem
1242  * like a winning strategy; the cost in planning time is too high. For
1243  * now, we generate one path for each pathkey, listing that pathkey first
1244  * and the rest in random order. This should allow at least a one-clause
1245  * mergejoin without re-sorting against any other possible mergejoin
1246  * partner path. But if we've not guessed the right ordering of secondary
1247  * keys, we may end up evaluating clauses as qpquals when they could have
1248  * been done as mergeclauses. (In practice, it's rare that there's more
1249  * than two or three mergeclauses, so expending a huge amount of thought
1250  * on that is probably not worth it.)
1251  *
1252  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1253  * some heuristics behind it (see that function), so be sure to try it
1254  * exactly as-is as well as making variants.
1255  */
1256  all_pathkeys = select_outer_pathkeys_for_merge(root,
1257  extra->mergeclause_list,
1258  joinrel);
1259 
1260  foreach(l, all_pathkeys)
1261  {
1262  PathKey *front_pathkey = (PathKey *) lfirst(l);
1263  List *cur_mergeclauses;
1264  List *outerkeys;
1265  List *innerkeys;
1266  List *merge_pathkeys;
1267 
1268  /* Make a pathkey list with this guy first */
1269  if (l != list_head(all_pathkeys))
1270  outerkeys = lcons(front_pathkey,
1271  list_delete_nth_cell(list_copy(all_pathkeys),
1272  foreach_current_index(l)));
1273  else
1274  outerkeys = all_pathkeys; /* no work at first one... */
1275 
1276  /* Sort the mergeclauses into the corresponding ordering */
1277  cur_mergeclauses =
1279  outerkeys,
1280  extra->mergeclause_list);
1281 
1282  /* Should have used them all... */
1283  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1284 
1285  /* Build sort pathkeys for the inner side */
1286  innerkeys = make_inner_pathkeys_for_merge(root,
1287  cur_mergeclauses,
1288  outerkeys);
1289 
1290  /* Build pathkeys representing output sort order */
1291  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1292  outerkeys);
1293 
1294  /*
1295  * And now we can make the path.
1296  *
1297  * Note: it's possible that the cheapest paths will already be sorted
1298  * properly. try_mergejoin_path will detect that case and suppress an
1299  * explicit sort step, so we needn't do so here.
1300  */
1301  try_mergejoin_path(root,
1302  joinrel,
1303  outer_path,
1304  inner_path,
1305  merge_pathkeys,
1306  cur_mergeclauses,
1307  outerkeys,
1308  innerkeys,
1309  jointype,
1310  extra,
1311  false);
1312 
1313  /*
1314  * If we have partial outer and parallel safe inner path then try
1315  * partial mergejoin path.
1316  */
1317  if (cheapest_partial_outer && cheapest_safe_inner)
1319  joinrel,
1320  cheapest_partial_outer,
1321  cheapest_safe_inner,
1322  merge_pathkeys,
1323  cur_mergeclauses,
1324  outerkeys,
1325  innerkeys,
1326  jointype,
1327  extra);
1328  }
1329 }
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:915
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:766
List * lcons(void *datum, List *list)
Definition: list.c:494
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1404
static ListCell * list_head(const List *l)
Definition: pg_list.h:126
#define foreach_current_index(cell)
Definition: pg_list.h:401

References Assert(), bms_is_empty(), build_join_pathkeys(), RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, create_unique_path(), find_mergeclauses_for_outer_pathkeys(), foreach_current_index, 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_nth_cell(), list_head(), list_length(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, 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().

◆ try_hashjoin_path()

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

992 {
993  Relids required_outer;
994  JoinCostWorkspace workspace;
995 
996  /*
997  * Check to see if proposed path is still parameterized, and reject if the
998  * parameterization wouldn't be sensible.
999  */
1000  required_outer = calc_non_nestloop_required_outer(outer_path,
1001  inner_path);
1002  if (required_outer &&
1003  !bms_overlap(required_outer, extra->param_source_rels))
1004  {
1005  /* Waste no memory when we reject a path here */
1006  bms_free(required_outer);
1007  return;
1008  }
1009 
1010  /*
1011  * See comments in try_nestloop_path(). Also note that hashjoin paths
1012  * never have any output pathkeys, per comments in create_hashjoin_path.
1013  */
1014  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1015  outer_path, inner_path, extra, false);
1016 
1017  if (add_path_precheck(joinrel,
1018  workspace.startup_cost, workspace.total_cost,
1019  NIL, required_outer))
1020  {
1021  add_path(joinrel, (Path *)
1022  create_hashjoin_path(root,
1023  joinrel,
1024  jointype,
1025  &workspace,
1026  extra,
1027  outer_path,
1028  inner_path,
1029  false, /* parallel_hash */
1030  extra->restrictlist,
1031  required_outer,
1032  hashclauses));
1033  }
1034  else
1035  {
1036  /* Waste no memory when we reject a path here */
1037  bms_free(required_outer);
1038  }
1039 }
void bms_free(Bitmapset *a)
Definition: bitmapset.c:209
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra, bool parallel_hash)
Definition: costsize.c:3801
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2393
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, bool parallel_hash, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition: pathnode.c:2580
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:644

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().

◆ try_mergejoin_path()

static void try_mergejoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
List mergeclauses,
List outersortkeys,
List innersortkeys,
JoinType  jointype,
JoinPathExtraData extra,
bool  is_partial 
)
static

Definition at line 820 of file joinpath.c.

831 {
832  Relids required_outer;
833  JoinCostWorkspace workspace;
834 
835  if (is_partial)
836  {
838  joinrel,
839  outer_path,
840  inner_path,
841  pathkeys,
842  mergeclauses,
843  outersortkeys,
844  innersortkeys,
845  jointype,
846  extra);
847  return;
848  }
849 
850  /*
851  * Check to see if proposed path is still parameterized, and reject if the
852  * parameterization wouldn't be sensible.
853  */
854  required_outer = calc_non_nestloop_required_outer(outer_path,
855  inner_path);
856  if (required_outer &&
857  !bms_overlap(required_outer, extra->param_source_rels))
858  {
859  /* Waste no memory when we reject a path here */
860  bms_free(required_outer);
861  return;
862  }
863 
864  /*
865  * If the given paths are already well enough ordered, we can skip doing
866  * an explicit sort.
867  */
868  if (outersortkeys &&
869  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
870  outersortkeys = NIL;
871  if (innersortkeys &&
872  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
873  innersortkeys = NIL;
874 
875  /*
876  * See comments in try_nestloop_path().
877  */
878  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
879  outer_path, inner_path,
880  outersortkeys, innersortkeys,
881  extra);
882 
883  if (add_path_precheck(joinrel,
884  workspace.startup_cost, workspace.total_cost,
885  pathkeys, required_outer))
886  {
887  add_path(joinrel, (Path *)
889  joinrel,
890  jointype,
891  &workspace,
892  extra,
893  outer_path,
894  inner_path,
895  extra->restrictlist,
896  pathkeys,
897  required_outer,
898  mergeclauses,
899  outersortkeys,
900  innersortkeys));
901  }
902  else
903  {
904  /* Waste no memory when we reject a path here */
905  bms_free(required_outer);
906  }
907 }
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:3243
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:2514

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().

◆ try_nestloop_path()

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

633 {
634  Relids required_outer;
635  JoinCostWorkspace workspace;
636  RelOptInfo *innerrel = inner_path->parent;
637  RelOptInfo *outerrel = outer_path->parent;
638  Relids innerrelids;
639  Relids outerrelids;
640  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
641  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
642 
643  /*
644  * Paths are parameterized by top-level parents, so run parameterization
645  * tests on the parent relids.
646  */
647  if (innerrel->top_parent_relids)
648  innerrelids = innerrel->top_parent_relids;
649  else
650  innerrelids = innerrel->relids;
651 
652  if (outerrel->top_parent_relids)
653  outerrelids = outerrel->top_parent_relids;
654  else
655  outerrelids = outerrel->relids;
656 
657  /*
658  * Check to see if proposed path is still parameterized, and reject if the
659  * parameterization wouldn't be sensible --- unless allow_star_schema_join
660  * says to allow it anyway. Also, we must reject if have_dangerous_phv
661  * doesn't like the look of it, which could only happen if the nestloop is
662  * still parameterized.
663  */
664  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
665  innerrelids, inner_paramrels);
666  if (required_outer &&
667  ((!bms_overlap(required_outer, extra->param_source_rels) &&
668  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
669  have_dangerous_phv(root, outerrelids, inner_paramrels)))
670  {
671  /* Waste no memory when we reject a path here */
672  bms_free(required_outer);
673  return;
674  }
675 
676  /*
677  * Do a precheck to quickly eliminate obviously-inferior paths. We
678  * calculate a cheap lower bound on the path's cost and then use
679  * add_path_precheck() to see if the path is clearly going to be dominated
680  * by some existing path for the joinrel. If not, do the full pushup with
681  * creating a fully valid path structure and submitting it to add_path().
682  * The latter two steps are expensive enough to make this two-phase
683  * methodology worthwhile.
684  */
685  initial_cost_nestloop(root, &workspace, jointype,
686  outer_path, inner_path, extra);
687 
688  if (add_path_precheck(joinrel,
689  workspace.startup_cost, workspace.total_cost,
690  pathkeys, required_outer))
691  {
692  /*
693  * If the inner path is parameterized, it is parameterized by the
694  * topmost parent of the outer rel, not the outer rel itself. Fix
695  * that.
696  */
697  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
698  {
699  inner_path = reparameterize_path_by_child(root, inner_path,
700  outer_path->parent);
701 
702  /*
703  * If we could not translate the path, we can't create nest loop
704  * path.
705  */
706  if (!inner_path)
707  {
708  bms_free(required_outer);
709  return;
710  }
711  }
712 
713  add_path(joinrel, (Path *)
715  joinrel,
716  jointype,
717  &workspace,
718  extra,
719  outer_path,
720  inner_path,
721  extra->restrictlist,
722  pathkeys,
723  required_outer));
724  }
725  else
726  {
727  /* Waste no memory when we reject a path here */
728  bms_free(required_outer);
729  }
730 }
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2962
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:36
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:356
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1184
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:2426
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2360
Path * reparameterize_path_by_child(PlannerInfo *root, Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:4038

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_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, reparameterize_path_by_child(), JoinPathExtraData::restrictlist, JoinCostWorkspace::startup_cost, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.

Referenced by match_unsorted_outer().

◆ try_partial_hashjoin_path()

static void try_partial_hashjoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List hashclauses,
JoinType  jointype,
JoinPathExtraData extra,
bool  parallel_hash 
)
static

Definition at line 1051 of file joinpath.c.

1059 {
1060  JoinCostWorkspace workspace;
1061 
1062  /*
1063  * If the inner path is parameterized, the parameterization must be fully
1064  * satisfied by the proposed outer path. Parameterized partial paths are
1065  * not supported. The caller should already have verified that no lateral
1066  * rels are required here.
1067  */
1068  Assert(bms_is_empty(joinrel->lateral_relids));
1069  if (inner_path->param_info != NULL)
1070  {
1071  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1072 
1073  if (!bms_is_empty(inner_paramrels))
1074  return;
1075  }
1076 
1077  /*
1078  * Before creating a path, get a quick lower bound on what it is likely to
1079  * cost. Bail out right away if it looks terrible.
1080  */
1081  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1082  outer_path, inner_path, extra, parallel_hash);
1083  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
1084  return;
1085 
1086  /* Might be good enough to be worth trying, so let's try it. */
1087  add_partial_path(joinrel, (Path *)
1088  create_hashjoin_path(root,
1089  joinrel,
1090  jointype,
1091  &workspace,
1092  extra,
1093  outer_path,
1094  inner_path,
1095  parallel_hash,
1096  extra->restrictlist,
1097  NULL,
1098  hashclauses));
1099 }
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:867

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

Referenced by hash_inner_and_outer().

◆ try_partial_mergejoin_path()

static void try_partial_mergejoin_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
List mergeclauses,
List outersortkeys,
List innersortkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 915 of file joinpath.c.

925 {
926  JoinCostWorkspace workspace;
927 
928  /*
929  * See comments in try_partial_hashjoin_path().
930  */
932  if (inner_path->param_info != NULL)
933  {
934  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
935 
936  if (!bms_is_empty(inner_paramrels))
937  return;
938  }
939 
940  /*
941  * If the given paths are already well enough ordered, we can skip doing
942  * an explicit sort.
943  */
944  if (outersortkeys &&
945  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
946  outersortkeys = NIL;
947  if (innersortkeys &&
948  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
949  innersortkeys = NIL;
950 
951  /*
952  * See comments in try_partial_nestloop_path().
953  */
954  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
955  outer_path, inner_path,
956  outersortkeys, innersortkeys,
957  extra);
958 
959  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
960  return;
961 
962  /* Might be good enough to be worth trying, so let's try it. */
963  add_partial_path(joinrel, (Path *)
965  joinrel,
966  jointype,
967  &workspace,
968  extra,
969  outer_path,
970  inner_path,
971  extra->restrictlist,
972  pathkeys,
973  NULL,
974  mergeclauses,
975  outersortkeys,
976  innersortkeys));
977 }

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

Referenced by sort_inner_and_outer(), and try_mergejoin_path().

◆ try_partial_nestloop_path()

static void try_partial_nestloop_path ( PlannerInfo root,
RelOptInfo joinrel,
Path outer_path,
Path inner_path,
List pathkeys,
JoinType  jointype,
JoinPathExtraData extra 
)
static

Definition at line 738 of file joinpath.c.

745 {
746  JoinCostWorkspace workspace;
747 
748  /*
749  * If the inner path is parameterized, the parameterization must be fully
750  * satisfied by the proposed outer path. Parameterized partial paths are
751  * not supported. The caller should already have verified that no lateral
752  * rels are required here.
753  */
755  if (inner_path->param_info != NULL)
756  {
757  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
758  RelOptInfo *outerrel = outer_path->parent;
759  Relids outerrelids;
760 
761  /*
762  * The inner and outer paths are parameterized, if at all, by the top
763  * level parents, not the child relations, so we must use those relids
764  * for our parameterization tests.
765  */
766  if (outerrel->top_parent_relids)
767  outerrelids = outerrel->top_parent_relids;
768  else
769  outerrelids = outerrel->relids;
770 
771  if (!bms_is_subset(inner_paramrels, outerrelids))
772  return;
773  }
774 
775  /*
776  * Before creating a path, get a quick lower bound on what it is likely to
777  * cost. Bail out right away if it looks terrible.
778  */
779  initial_cost_nestloop(root, &workspace, jointype,
780  outer_path, inner_path, extra);
781  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
782  return;
783 
784  /*
785  * If the inner path is parameterized, it is parameterized by the topmost
786  * parent of the outer rel, not the outer rel itself. Fix that.
787  */
788  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
789  {
790  inner_path = reparameterize_path_by_child(root, inner_path,
791  outer_path->parent);
792 
793  /*
794  * If we could not translate the path, we can't create nest loop path.
795  */
796  if (!inner_path)
797  return;
798  }
799 
800  /* Might be good enough to be worth trying, so let's try it. */
801  add_partial_path(joinrel, (Path *)
803  joinrel,
804  jointype,
805  &workspace,
806  extra,
807  outer_path,
808  inner_path,
809  extra->restrictlist,
810  pathkeys,
811  NULL));
812 }

References add_partial_path(), add_partial_path_precheck(), Assert(), bms_is_empty(), bms_is_subset(), create_nestloop_path(), initial_cost_nestloop(), RelOptInfo::lateral_relids, PATH_PARAM_BY_PARENT, RelOptInfo::relids, reparameterize_path_by_child(), JoinPathExtraData::restrictlist, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.

Referenced by consider_parallel_nestloop().

Variable Documentation

◆ set_join_pathlist_hook

set_join_pathlist_hook_type set_join_pathlist_hook = NULL

Definition at line 30 of file joinpath.c.

Referenced by add_paths_to_joinrel().