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:511
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1637

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. Note: param_source_rels
238  * should contain only baserels, not OJ relids, so starting from
239  * all_baserels not all_query_rels is correct.
240  */
241  foreach(lc, root->join_info_list)
242  {
243  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
244 
245  /*
246  * SJ is relevant to this join if we have some part of its RHS
247  * (possibly not all of it), and haven't yet joined to its LHS. (This
248  * test is pretty simplistic, but should be sufficient considering the
249  * join has already been proven legal.) If the SJ is relevant, it
250  * presents constraints for joining to anything not in its RHS.
251  */
252  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
253  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
256  sjinfo2->min_righthand));
257 
258  /* full joins constrain both sides symmetrically */
259  if (sjinfo2->jointype == JOIN_FULL &&
260  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
261  !bms_overlap(joinrelids, sjinfo2->min_righthand))
264  sjinfo2->min_lefthand));
265  }
266 
267  /*
268  * However, when a LATERAL subquery is involved, there will simply not be
269  * any paths for the joinrel that aren't parameterized by whatever the
270  * subquery is parameterized by, unless its parameterization is resolved
271  * within the joinrel. So we might as well allow additional dependencies
272  * on whatever residual lateral dependencies the joinrel will have.
273  */
275  joinrel->lateral_relids);
276 
277  /*
278  * 1. Consider mergejoin paths where both relations must be explicitly
279  * sorted. Skip this if we can't mergejoin.
280  */
281  if (mergejoin_allowed)
282  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
283  jointype, &extra);
284 
285  /*
286  * 2. Consider paths where the outer relation need not be explicitly
287  * sorted. This includes both nestloops and mergejoins where the outer
288  * path is already ordered. Again, skip this if we can't mergejoin.
289  * (That's okay because we know that nestloop can't handle
290  * right/right-anti/full joins at all, so it wouldn't work in the
291  * prohibited cases either.)
292  */
293  if (mergejoin_allowed)
294  match_unsorted_outer(root, joinrel, outerrel, innerrel,
295  jointype, &extra);
296 
297 #ifdef NOT_USED
298 
299  /*
300  * 3. Consider paths where the inner relation need not be explicitly
301  * sorted. This includes mergejoins only (nestloops were already built in
302  * match_unsorted_outer).
303  *
304  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
305  * significant difference between the inner and outer side of a mergejoin,
306  * so match_unsorted_inner creates no paths that aren't equivalent to
307  * those made by match_unsorted_outer when add_paths_to_joinrel() is
308  * invoked with the two rels given in the other order.
309  */
310  if (mergejoin_allowed)
311  match_unsorted_inner(root, joinrel, outerrel, innerrel,
312  jointype, &extra);
313 #endif
314 
315  /*
316  * 4. Consider paths where both outer and inner relations must be hashed
317  * before being joined. As above, disregard enable_hashjoin for full
318  * joins, because there may be no other alternative.
319  */
320  if (enable_hashjoin || jointype == JOIN_FULL)
321  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
322  jointype, &extra);
323 
324  /*
325  * 5. If inner and outer relations are foreign tables (or joins) belonging
326  * to the same server and assigned to the same user to check access
327  * permissions as, give the FDW a chance to push down joins.
328  */
329  if (joinrel->fdwroutine &&
330  joinrel->fdwroutine->GetForeignJoinPaths)
331  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
332  outerrel, innerrel,
333  jointype, &extra);
334 
335  /*
336  * 6. Finally, give extensions a chance to manipulate the path list.
337  */
339  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
340  jointype, &extra);
341 }
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:987
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:332
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:298
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:818
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:4734
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:2282
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1201
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:2028
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1652
@ JOIN_SEMI
Definition: nodes.h:318
@ JOIN_FULL
Definition: nodes.h:306
@ JOIN_INNER
Definition: nodes.h:304
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:326
@ JOIN_UNIQUE_INNER
Definition: nodes.h:327
@ JOIN_ANTI
Definition: nodes.h:319
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:815
#define lfirst(lc)
Definition: pg_list.h:172
#define NIL
Definition: pg_list.h:68
List * mergeclause_list
Definition: pathnodes.h:3177
Relids param_source_rels
Definition: pathnodes.h:3181
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3180
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3179
List * join_info_list
Definition: pathnodes.h:337
Relids all_baserels
Definition: pathnodes.h:252
Relids relids
Definition: pathnodes.h:856
Relids top_parent_relids
Definition: pathnodes.h:988
Relids lateral_relids
Definition: pathnodes.h:898
RelOptKind reloptkind
Definition: pathnodes.h:850
Relids min_righthand
Definition: pathnodes.h:2841
JoinType jointype
Definition: pathnodes.h:2844
Relids min_lefthand
Definition: pathnodes.h:2840

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

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

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

1171 {
1172  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
1173  bms_is_subset(rinfo->right_relids, innerrel->relids))
1174  {
1175  /* lefthand side is outer */
1176  rinfo->outer_is_left = true;
1177  return true;
1178  }
1179  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
1180  bms_is_subset(rinfo->right_relids, outerrel->relids))
1181  {
1182  /* righthand side is outer */
1183  rinfo->outer_is_left = false;
1184  return true;
1185  }
1186  return false; /* no good for these input relations */
1187 }

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

1911 {
1912  ListCell *lc1;
1913 
1914  /* generate merge join path for each partial outer path */
1915  foreach(lc1, outerrel->partial_pathlist)
1916  {
1917  Path *outerpath = (Path *) lfirst(lc1);
1918  List *merge_pathkeys;
1919 
1920  /*
1921  * Figure out what useful ordering any paths we create will have.
1922  */
1923  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1924  outerpath->pathkeys);
1925 
1926  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1927  extra, false, inner_cheapest_total,
1928  merge_pathkeys, true);
1929  }
1930 }
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:1404
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1093
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1633
List * partial_pathlist
Definition: pathnodes.h:885

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

1950 {
1951  JoinType save_jointype = jointype;
1952  ListCell *lc1;
1953 
1954  if (jointype == JOIN_UNIQUE_INNER)
1955  jointype = JOIN_INNER;
1956 
1957  foreach(lc1, outerrel->partial_pathlist)
1958  {
1959  Path *outerpath = (Path *) lfirst(lc1);
1960  List *pathkeys;
1961  ListCell *lc2;
1962 
1963  /* Figure out what useful ordering any paths we create will have. */
1964  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1965  outerpath->pathkeys);
1966 
1967  /*
1968  * Try the cheapest parameterized paths; only those which will produce
1969  * an unparameterized path when joined to this outerrel will survive
1970  * try_partial_nestloop_path. The cheapest unparameterized path is
1971  * also in this list.
1972  */
1973  foreach(lc2, innerrel->cheapest_parameterized_paths)
1974  {
1975  Path *innerpath = (Path *) lfirst(lc2);
1976  Path *mpath;
1977 
1978  /* Can't join to an inner path that is not parallel-safe */
1979  if (!innerpath->parallel_safe)
1980  continue;
1981 
1982  /*
1983  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1984  * cheapest_total_path, and we have to unique-ify it. (We might
1985  * be able to relax this to allow other safe, unparameterized
1986  * inner paths, but right now create_unique_path is not on board
1987  * with that.)
1988  */
1989  if (save_jointype == JOIN_UNIQUE_INNER)
1990  {
1991  if (innerpath != innerrel->cheapest_total_path)
1992  continue;
1993  innerpath = (Path *) create_unique_path(root, innerrel,
1994  innerpath,
1995  extra->sjinfo);
1996  Assert(innerpath);
1997  }
1998 
1999  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
2000  pathkeys, jointype, extra);
2001 
2002  /*
2003  * Try generating a memoize path and see if that makes the nested
2004  * loop any cheaper.
2005  */
2006  mpath = get_memoize_path(root, innerrel, outerrel,
2007  innerpath, outerpath, jointype,
2008  extra);
2009  if (mpath != NULL)
2010  try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2011  pathkeys, jointype, extra);
2012  }
2013  }
2014 }
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:557
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:795
Assert(fmt[strlen(fmt) - 1] !='\n')
JoinType
Definition: nodes.h:299
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1652
bool parallel_safe
Definition: pathnodes.h:1623
List * cheapest_parameterized_paths
Definition: pathnodes.h:889
struct Path * cheapest_total_path
Definition: pathnodes.h:887

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

1414 {
1415  List *mergeclauses;
1416  List *innersortkeys;
1417  List *trialsortkeys;
1418  Path *cheapest_startup_inner;
1419  Path *cheapest_total_inner;
1420  JoinType save_jointype = jointype;
1421  int num_sortkeys;
1422  int sortkeycnt;
1423 
1424  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1425  jointype = JOIN_INNER;
1426 
1427  /* Look for useful mergeclauses (if any) */
1428  mergeclauses =
1430  outerpath->pathkeys,
1431  extra->mergeclause_list);
1432 
1433  /*
1434  * Done with this outer path if no chance for a mergejoin.
1435  *
1436  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1437  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1438  * but since mergejoin is our only join type that supports FULL JOIN
1439  * without any join clauses, it's necessary to generate a clauseless
1440  * mergejoin path instead.
1441  */
1442  if (mergeclauses == NIL)
1443  {
1444  if (jointype == JOIN_FULL)
1445  /* okay to try for mergejoin */ ;
1446  else
1447  return;
1448  }
1449  if (useallclauses &&
1450  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1451  return;
1452 
1453  /* Compute the required ordering of the inner path */
1454  innersortkeys = make_inner_pathkeys_for_merge(root,
1455  mergeclauses,
1456  outerpath->pathkeys);
1457 
1458  /*
1459  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1460  * a sort will be needed, only cheapest total cost matters. (But
1461  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1462  * already correctly sorted.)
1463  */
1464  try_mergejoin_path(root,
1465  joinrel,
1466  outerpath,
1467  inner_cheapest_total,
1468  merge_pathkeys,
1469  mergeclauses,
1470  NIL,
1471  innersortkeys,
1472  jointype,
1473  extra,
1474  is_partial);
1475 
1476  /* Can't do anything else if inner path needs to be unique'd */
1477  if (save_jointype == JOIN_UNIQUE_INNER)
1478  return;
1479 
1480  /*
1481  * Look for presorted inner paths that satisfy the innersortkey list ---
1482  * or any truncation thereof, if we are allowed to build a mergejoin using
1483  * a subset of the merge clauses. Here, we consider both cheap startup
1484  * cost and cheap total cost.
1485  *
1486  * Currently we do not consider parameterized inner paths here. This
1487  * interacts with decisions elsewhere that also discriminate against
1488  * mergejoins with parameterized inputs; see comments in
1489  * src/backend/optimizer/README.
1490  *
1491  * As we shorten the sortkey list, we should consider only paths that are
1492  * strictly cheaper than (in particular, not the same as) any path found
1493  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1494  * merge keys than a given path allows (treating the rest as plain
1495  * joinquals), which is unlikely to be a good idea. Also, eliminating
1496  * paths here on the basis of compare_path_costs is a lot cheaper than
1497  * building the mergejoin path only to throw it away.
1498  *
1499  * If inner_cheapest_total is well enough sorted to have not required a
1500  * sort in the path made above, we shouldn't make a duplicate path with
1501  * it, either. We handle that case with the same logic that handles the
1502  * previous consideration, by initializing the variables that track
1503  * cheapest-so-far properly. Note that we do NOT reject
1504  * inner_cheapest_total if we find it matches some shorter set of
1505  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1506  * sorting inner_cheapest_total, whereas we did sort it above, so the
1507  * plans being considered are different.
1508  */
1509  if (pathkeys_contained_in(innersortkeys,
1510  inner_cheapest_total->pathkeys))
1511  {
1512  /* inner_cheapest_total didn't require a sort */
1513  cheapest_startup_inner = inner_cheapest_total;
1514  cheapest_total_inner = inner_cheapest_total;
1515  }
1516  else
1517  {
1518  /* it did require a sort, at least for the full set of keys */
1519  cheapest_startup_inner = NULL;
1520  cheapest_total_inner = NULL;
1521  }
1522  num_sortkeys = list_length(innersortkeys);
1523  if (num_sortkeys > 1 && !useallclauses)
1524  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1525  else
1526  trialsortkeys = innersortkeys; /* won't really truncate */
1527 
1528  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1529  {
1530  Path *innerpath;
1531  List *newclauses = NIL;
1532 
1533  /*
1534  * Look for an inner path ordered well enough for the first
1535  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1536  * destructively, which is why we made a copy...
1537  */
1538  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1539  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1540  trialsortkeys,
1541  NULL,
1542  TOTAL_COST,
1543  is_partial);
1544  if (innerpath != NULL &&
1545  (cheapest_total_inner == NULL ||
1546  compare_path_costs(innerpath, cheapest_total_inner,
1547  TOTAL_COST) < 0))
1548  {
1549  /* Found a cheap (or even-cheaper) sorted path */
1550  /* Select the right mergeclauses, if we didn't already */
1551  if (sortkeycnt < num_sortkeys)
1552  {
1553  newclauses =
1555  mergeclauses,
1556  trialsortkeys);
1557  Assert(newclauses != NIL);
1558  }
1559  else
1560  newclauses = mergeclauses;
1561  try_mergejoin_path(root,
1562  joinrel,
1563  outerpath,
1564  innerpath,
1565  merge_pathkeys,
1566  newclauses,
1567  NIL,
1568  NIL,
1569  jointype,
1570  extra,
1571  is_partial);
1572  cheapest_total_inner = innerpath;
1573  }
1574  /* Same on the basis of cheapest startup cost ... */
1575  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1576  trialsortkeys,
1577  NULL,
1578  STARTUP_COST,
1579  is_partial);
1580  if (innerpath != NULL &&
1581  (cheapest_startup_inner == NULL ||
1582  compare_path_costs(innerpath, cheapest_startup_inner,
1583  STARTUP_COST) < 0))
1584  {
1585  /* Found a cheap (or even-cheaper) sorted path */
1586  if (innerpath != cheapest_total_inner)
1587  {
1588  /*
1589  * Avoid rebuilding clause list if we already made one; saves
1590  * memory in big join trees...
1591  */
1592  if (newclauses == NIL)
1593  {
1594  if (sortkeycnt < num_sortkeys)
1595  {
1596  newclauses =
1598  mergeclauses,
1599  trialsortkeys);
1600  Assert(newclauses != NIL);
1601  }
1602  else
1603  newclauses = mergeclauses;
1604  }
1605  try_mergejoin_path(root,
1606  joinrel,
1607  outerpath,
1608  innerpath,
1609  merge_pathkeys,
1610  newclauses,
1611  NIL,
1612  NIL,
1613  jointype,
1614  extra,
1615  is_partial);
1616  }
1617  cheapest_startup_inner = innerpath;
1618  }
1619 
1620  /*
1621  * Don't consider truncated sortkeys if we need all clauses.
1622  */
1623  if (useallclauses)
1624  break;
1625  }
1626 }
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:877
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:1622
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:420
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1311
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1725
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:340
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:152
List * pathlist
Definition: pathnodes.h:883

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

561 {
562  List *param_exprs;
563  List *hash_operators;
564  ListCell *lc;
565  bool binary_mode;
566 
567  /* Obviously not if it's disabled */
568  if (!enable_memoize)
569  return NULL;
570 
571  /*
572  * We can safely not bother with all this unless we expect to perform more
573  * than one inner scan. The first scan is always going to be a cache
574  * miss. This would likely fail later anyway based on costs, so this is
575  * really just to save some wasted effort.
576  */
577  if (outer_path->parent->rows < 2)
578  return NULL;
579 
580  /*
581  * We can only have a memoize node when there's some kind of cache key,
582  * either parameterized path clauses or lateral Vars. No cache key sounds
583  * more like something a Materialize node might be more useful for.
584  */
585  if ((inner_path->param_info == NULL ||
586  inner_path->param_info->ppi_clauses == NIL) &&
587  innerrel->lateral_vars == NIL)
588  return NULL;
589 
590  /*
591  * Currently we don't do this for SEMI and ANTI joins unless they're
592  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
593  * don't scan the inner node to completion, which will mean memoize cannot
594  * mark the cache entry as complete.
595  *
596  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
597  * = true. Should we? See add_paths_to_joinrel()
598  */
599  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
600  jointype == JOIN_ANTI))
601  return NULL;
602 
603  /*
604  * Memoize normally marks cache entries as complete when it runs out of
605  * tuples to read from its subplan. However, with unique joins, Nested
606  * Loop will skip to the next outer tuple after finding the first matching
607  * inner tuple. This means that we may not read the inner side of the
608  * join to completion which leaves no opportunity to mark the cache entry
609  * as complete. To work around that, when the join is unique we
610  * automatically mark cache entries as complete after fetching the first
611  * tuple. This works when the entire join condition is parameterized.
612  * Otherwise, when the parameterization is only a subset of the join
613  * condition, we can't be sure which part of it causes the join to be
614  * unique. This means there are no guarantees that only 1 tuple will be
615  * read. We cannot mark the cache entry as complete after reading the
616  * first tuple without that guarantee. This means the scope of Memoize
617  * node's usefulness is limited to only outer rows that have no join
618  * partner as this is the only case where Nested Loop would exhaust the
619  * inner scan of a unique join. Since the scope is limited to that, we
620  * just don't bother making a memoize path in this case.
621  *
622  * Lateral vars needn't be considered here as they're not considered when
623  * determining if the join is unique.
624  *
625  * XXX this could be enabled if the remaining join quals were made part of
626  * the inner scan's filter instead of the join filter. Maybe it's worth
627  * considering doing that?
628  */
629  if (extra->inner_unique &&
630  (inner_path->param_info == NULL ||
631  list_length(inner_path->param_info->ppi_clauses) <
632  list_length(extra->restrictlist)))
633  return NULL;
634 
635  /*
636  * We can't use a memoize node if there are volatile functions in the
637  * inner rel's target list or restrict list. A cache hit could reduce the
638  * number of calls to these functions.
639  */
640  if (contain_volatile_functions((Node *) innerrel->reltarget))
641  return NULL;
642 
643  foreach(lc, innerrel->baserestrictinfo)
644  {
645  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
646 
647  if (contain_volatile_functions((Node *) rinfo))
648  return NULL;
649  }
650 
651  /* Check if we have hash ops for each parameter to the path */
653  inner_path->param_info,
654  outerrel->top_parent ?
655  outerrel->top_parent : outerrel,
656  innerrel,
657  &param_exprs,
658  &hash_operators,
659  &binary_mode))
660  {
661  return (Path *) create_memoize_path(root,
662  innerrel,
663  inner_path,
664  param_exprs,
665  hash_operators,
666  extra->inner_unique,
667  binary_mode,
668  outer_path->rows);
669  }
670 
671  return NULL;
672 }
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:483
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:432
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:129
Cardinality rows
Definition: pathnodes.h:1628
List * baserestrictinfo
Definition: pathnodes.h:964
struct PathTarget * reltarget
Definition: pathnodes.h:878
List * lateral_vars
Definition: pathnodes.h:919

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

2034 {
2035  JoinType save_jointype = jointype;
2036  bool isouterjoin = IS_OUTER_JOIN(jointype);
2037  List *hashclauses;
2038  ListCell *l;
2039 
2040  /*
2041  * We need to build only one hashclauses list for any given pair of outer
2042  * and inner relations; all of the hashable clauses will be used as keys.
2043  *
2044  * Scan the join's restrictinfo list to find hashjoinable clauses that are
2045  * usable with this pair of sub-relations.
2046  */
2047  hashclauses = NIL;
2048  foreach(l, extra->restrictlist)
2049  {
2050  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2051 
2052  /*
2053  * If processing an outer join, only use its own join clauses for
2054  * hashing. For inner joins we need not be so picky.
2055  */
2056  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2057  continue;
2058 
2059  if (!restrictinfo->can_join ||
2060  restrictinfo->hashjoinoperator == InvalidOid)
2061  continue; /* not hashjoinable */
2062 
2063  /*
2064  * Check if clause has the form "outer op inner" or "inner op outer".
2065  */
2066  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2067  continue; /* no good for these input relations */
2068 
2069  hashclauses = lappend(hashclauses, restrictinfo);
2070  }
2071 
2072  /* If we found any usable hashclauses, make paths */
2073  if (hashclauses)
2074  {
2075  /*
2076  * We consider both the cheapest-total-cost and cheapest-startup-cost
2077  * outer paths. There's no need to consider any but the
2078  * cheapest-total-cost inner path, however.
2079  */
2080  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2081  Path *cheapest_total_outer = outerrel->cheapest_total_path;
2082  Path *cheapest_total_inner = innerrel->cheapest_total_path;
2083 
2084  /*
2085  * If either cheapest-total path is parameterized by the other rel, we
2086  * can't use a hashjoin. (There's no use looking for alternative
2087  * input paths, since these should already be the least-parameterized
2088  * available paths.)
2089  */
2090  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2091  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2092  return;
2093 
2094  /* Unique-ify if need be; we ignore parameterized possibilities */
2095  if (jointype == JOIN_UNIQUE_OUTER)
2096  {
2097  cheapest_total_outer = (Path *)
2098  create_unique_path(root, outerrel,
2099  cheapest_total_outer, extra->sjinfo);
2100  Assert(cheapest_total_outer);
2101  jointype = JOIN_INNER;
2102  try_hashjoin_path(root,
2103  joinrel,
2104  cheapest_total_outer,
2105  cheapest_total_inner,
2106  hashclauses,
2107  jointype,
2108  extra);
2109  /* no possibility of cheap startup here */
2110  }
2111  else if (jointype == JOIN_UNIQUE_INNER)
2112  {
2113  cheapest_total_inner = (Path *)
2114  create_unique_path(root, innerrel,
2115  cheapest_total_inner, extra->sjinfo);
2116  Assert(cheapest_total_inner);
2117  jointype = JOIN_INNER;
2118  try_hashjoin_path(root,
2119  joinrel,
2120  cheapest_total_outer,
2121  cheapest_total_inner,
2122  hashclauses,
2123  jointype,
2124  extra);
2125  if (cheapest_startup_outer != NULL &&
2126  cheapest_startup_outer != cheapest_total_outer)
2127  try_hashjoin_path(root,
2128  joinrel,
2129  cheapest_startup_outer,
2130  cheapest_total_inner,
2131  hashclauses,
2132  jointype,
2133  extra);
2134  }
2135  else
2136  {
2137  /*
2138  * For other jointypes, we consider the cheapest startup outer
2139  * together with the cheapest total inner, and then consider
2140  * pairings of cheapest-total paths including parameterized ones.
2141  * There is no use in generating parameterized paths on the basis
2142  * of possibly cheap startup cost, so this is sufficient.
2143  */
2144  ListCell *lc1;
2145  ListCell *lc2;
2146 
2147  if (cheapest_startup_outer != NULL)
2148  try_hashjoin_path(root,
2149  joinrel,
2150  cheapest_startup_outer,
2151  cheapest_total_inner,
2152  hashclauses,
2153  jointype,
2154  extra);
2155 
2156  foreach(lc1, outerrel->cheapest_parameterized_paths)
2157  {
2158  Path *outerpath = (Path *) lfirst(lc1);
2159 
2160  /*
2161  * We cannot use an outer path that is parameterized by the
2162  * inner rel.
2163  */
2164  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2165  continue;
2166 
2167  foreach(lc2, innerrel->cheapest_parameterized_paths)
2168  {
2169  Path *innerpath = (Path *) lfirst(lc2);
2170 
2171  /*
2172  * We cannot use an inner path that is parameterized by
2173  * the outer rel, either.
2174  */
2175  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2176  continue;
2177 
2178  if (outerpath == cheapest_startup_outer &&
2179  innerpath == cheapest_total_inner)
2180  continue; /* already tried it */
2181 
2182  try_hashjoin_path(root,
2183  joinrel,
2184  outerpath,
2185  innerpath,
2186  hashclauses,
2187  jointype,
2188  extra);
2189  }
2190  }
2191  }
2192 
2193  /*
2194  * If the joinrel is parallel-safe, we may be able to consider a
2195  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2196  * because the outer path will be partial, and therefore we won't be
2197  * able to properly guarantee uniqueness. Also, the resulting path
2198  * must not be parameterized.
2199  */
2200  if (joinrel->consider_parallel &&
2201  save_jointype != JOIN_UNIQUE_OUTER &&
2202  outerrel->partial_pathlist != NIL &&
2203  bms_is_empty(joinrel->lateral_relids))
2204  {
2205  Path *cheapest_partial_outer;
2206  Path *cheapest_partial_inner = NULL;
2207  Path *cheapest_safe_inner = NULL;
2208 
2209  cheapest_partial_outer =
2210  (Path *) linitial(outerrel->partial_pathlist);
2211 
2212  /*
2213  * Can we use a partial inner plan too, so that we can build a
2214  * shared hash table in parallel? We can't handle
2215  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2216  */
2217  if (innerrel->partial_pathlist != NIL &&
2218  save_jointype != JOIN_UNIQUE_INNER &&
2220  {
2221  cheapest_partial_inner =
2222  (Path *) linitial(innerrel->partial_pathlist);
2223  try_partial_hashjoin_path(root, joinrel,
2224  cheapest_partial_outer,
2225  cheapest_partial_inner,
2226  hashclauses, jointype, extra,
2227  true /* parallel_hash */ );
2228  }
2229 
2230  /*
2231  * Normally, given that the joinrel is parallel-safe, the cheapest
2232  * total inner path will also be parallel-safe, but if not, we'll
2233  * have to search for the cheapest safe, unparameterized inner
2234  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2235  * inner path. If full, right, or right-anti join, we can't use
2236  * parallelism (building the hash table in each backend) because
2237  * no one process has all the match bits.
2238  */
2239  if (save_jointype == JOIN_FULL ||
2240  save_jointype == JOIN_RIGHT ||
2241  save_jointype == JOIN_RIGHT_ANTI)
2242  cheapest_safe_inner = NULL;
2243  else if (cheapest_total_inner->parallel_safe)
2244  cheapest_safe_inner = cheapest_total_inner;
2245  else if (save_jointype != JOIN_UNIQUE_INNER)
2246  cheapest_safe_inner =
2248 
2249  if (cheapest_safe_inner != NULL)
2250  try_partial_hashjoin_path(root, joinrel,
2251  cheapest_partial_outer,
2252  cheapest_safe_inner,
2253  hashclauses, jointype, extra,
2254  false /* parallel_hash */ );
2255  }
2256  }
2257 }
#define bms_is_empty(a)
Definition: bitmapset.h:105
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:1042
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1169
#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:1108
List * lappend(List *list, void *datum)
Definition: list.c:338
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:348
@ JOIN_RIGHT
Definition: nodes.h:307
@ JOIN_RIGHT_ANTI
Definition: nodes.h:320
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:498
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2670
#define linitial(l)
Definition: pg_list.h:178
#define InvalidOid
Definition: postgres_ext.h:36
bool consider_parallel
Definition: pathnodes.h:872
struct Path * cheapest_startup_path
Definition: pathnodes.h:886

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_RIGHT_ANTI, 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 1652 of file joinpath.c.

1658 {
1659  JoinType save_jointype = jointype;
1660  bool nestjoinOK;
1661  bool useallclauses;
1662  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1663  Path *matpath = NULL;
1664  ListCell *lc1;
1665 
1666  /*
1667  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1668  * are doing a right, right-anti or full mergejoin, we must use *all* the
1669  * mergeclauses as join clauses, else we will not have a valid plan.
1670  * (Although these two flags are currently inverses, keep them separate
1671  * for clarity and possible future changes.)
1672  */
1673  switch (jointype)
1674  {
1675  case JOIN_INNER:
1676  case JOIN_LEFT:
1677  case JOIN_SEMI:
1678  case JOIN_ANTI:
1679  nestjoinOK = true;
1680  useallclauses = false;
1681  break;
1682  case JOIN_RIGHT:
1683  case JOIN_RIGHT_ANTI:
1684  case JOIN_FULL:
1685  nestjoinOK = false;
1686  useallclauses = true;
1687  break;
1688  case JOIN_UNIQUE_OUTER:
1689  case JOIN_UNIQUE_INNER:
1690  jointype = JOIN_INNER;
1691  nestjoinOK = true;
1692  useallclauses = false;
1693  break;
1694  default:
1695  elog(ERROR, "unrecognized join type: %d",
1696  (int) jointype);
1697  nestjoinOK = false; /* keep compiler quiet */
1698  useallclauses = false;
1699  break;
1700  }
1701 
1702  /*
1703  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1704  * we will consider it below as a member of cheapest_parameterized_paths,
1705  * but the other possibilities considered in this routine aren't usable.
1706  */
1707  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1708  inner_cheapest_total = NULL;
1709 
1710  /*
1711  * If we need to unique-ify the inner path, we will consider only the
1712  * cheapest-total inner.
1713  */
1714  if (save_jointype == JOIN_UNIQUE_INNER)
1715  {
1716  /* No way to do this with an inner path parameterized by outer rel */
1717  if (inner_cheapest_total == NULL)
1718  return;
1719  inner_cheapest_total = (Path *)
1720  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1721  Assert(inner_cheapest_total);
1722  }
1723  else if (nestjoinOK)
1724  {
1725  /*
1726  * Consider materializing the cheapest inner path, unless
1727  * enable_material is off or the path in question materializes its
1728  * output anyway.
1729  */
1730  if (enable_material && inner_cheapest_total != NULL &&
1731  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1732  matpath = (Path *)
1733  create_material_path(innerrel, inner_cheapest_total);
1734  }
1735 
1736  foreach(lc1, outerrel->pathlist)
1737  {
1738  Path *outerpath = (Path *) lfirst(lc1);
1739  List *merge_pathkeys;
1740 
1741  /*
1742  * We cannot use an outer path that is parameterized by the inner rel.
1743  */
1744  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1745  continue;
1746 
1747  /*
1748  * If we need to unique-ify the outer path, it's pointless to consider
1749  * any but the cheapest outer. (XXX we don't consider parameterized
1750  * outers, nor inners, for unique-ified cases. Should we?)
1751  */
1752  if (save_jointype == JOIN_UNIQUE_OUTER)
1753  {
1754  if (outerpath != outerrel->cheapest_total_path)
1755  continue;
1756  outerpath = (Path *) create_unique_path(root, outerrel,
1757  outerpath, extra->sjinfo);
1758  Assert(outerpath);
1759  }
1760 
1761  /*
1762  * The result will have this sort order (even if it is implemented as
1763  * a nestloop, and even if some of the mergeclauses are implemented by
1764  * qpquals rather than as true mergeclauses):
1765  */
1766  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1767  outerpath->pathkeys);
1768 
1769  if (save_jointype == JOIN_UNIQUE_INNER)
1770  {
1771  /*
1772  * Consider nestloop join, but only with the unique-ified cheapest
1773  * inner path
1774  */
1775  try_nestloop_path(root,
1776  joinrel,
1777  outerpath,
1778  inner_cheapest_total,
1779  merge_pathkeys,
1780  jointype,
1781  extra);
1782  }
1783  else if (nestjoinOK)
1784  {
1785  /*
1786  * Consider nestloop joins using this outer path and various
1787  * available paths for the inner relation. We consider the
1788  * cheapest-total paths for each available parameterization of the
1789  * inner relation, including the unparameterized case.
1790  */
1791  ListCell *lc2;
1792 
1793  foreach(lc2, innerrel->cheapest_parameterized_paths)
1794  {
1795  Path *innerpath = (Path *) lfirst(lc2);
1796  Path *mpath;
1797 
1798  try_nestloop_path(root,
1799  joinrel,
1800  outerpath,
1801  innerpath,
1802  merge_pathkeys,
1803  jointype,
1804  extra);
1805 
1806  /*
1807  * Try generating a memoize path and see if that makes the
1808  * nested loop any cheaper.
1809  */
1810  mpath = get_memoize_path(root, innerrel, outerrel,
1811  innerpath, outerpath, jointype,
1812  extra);
1813  if (mpath != NULL)
1814  try_nestloop_path(root,
1815  joinrel,
1816  outerpath,
1817  mpath,
1818  merge_pathkeys,
1819  jointype,
1820  extra);
1821  }
1822 
1823  /* Also consider materialized form of the cheapest inner path */
1824  if (matpath != NULL)
1825  try_nestloop_path(root,
1826  joinrel,
1827  outerpath,
1828  matpath,
1829  merge_pathkeys,
1830  jointype,
1831  extra);
1832  }
1833 
1834  /* Can't do anything else if outer path needs to be unique'd */
1835  if (save_jointype == JOIN_UNIQUE_OUTER)
1836  continue;
1837 
1838  /* Can't do anything else if inner rel is parameterized by outer */
1839  if (inner_cheapest_total == NULL)
1840  continue;
1841 
1842  /* Generate merge join paths */
1843  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1844  save_jointype, extra, useallclauses,
1845  inner_cheapest_total, merge_pathkeys,
1846  false);
1847  }
1848 
1849  /*
1850  * Consider partial nestloop and mergejoin plan if outerrel has any
1851  * partial path and the joinrel is parallel-safe. However, we can't
1852  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1853  * therefore we won't be able to properly guarantee uniqueness. Nor can
1854  * we handle joins needing lateral rels, since partial paths must not be
1855  * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
1856  * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1857  */
1858  if (joinrel->consider_parallel &&
1859  save_jointype != JOIN_UNIQUE_OUTER &&
1860  save_jointype != JOIN_FULL &&
1861  save_jointype != JOIN_RIGHT &&
1862  save_jointype != JOIN_RIGHT_ANTI &&
1863  outerrel->partial_pathlist != NIL &&
1864  bms_is_empty(joinrel->lateral_relids))
1865  {
1866  if (nestjoinOK)
1867  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1868  save_jointype, extra);
1869 
1870  /*
1871  * If inner_cheapest_total is NULL or non parallel-safe then find the
1872  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1873  * can't use any alternative inner path.
1874  */
1875  if (inner_cheapest_total == NULL ||
1876  !inner_cheapest_total->parallel_safe)
1877  {
1878  if (save_jointype == JOIN_UNIQUE_INNER)
1879  return;
1880 
1881  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1882  }
1883 
1884  if (inner_cheapest_total)
1885  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1886  save_jointype, extra,
1887  inner_cheapest_total);
1888  }
1889 }
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:680
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1944
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1904
@ JOIN_LEFT
Definition: nodes.h:305
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1564
NodeTag pathtype
Definition: pathnodes.h:1594

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_RIGHT_ANTI, 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 432 of file joinpath.c.

437 {
438  ListCell *lc;
439 
440  *param_exprs = NIL;
441  *operators = NIL;
442  *binary_mode = false;
443 
444  if (param_info != NULL)
445  {
446  List *clauses = param_info->ppi_clauses;
447 
448  foreach(lc, clauses)
449  {
450  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
451  OpExpr *opexpr;
452  Node *expr;
453  Oid hasheqoperator;
454 
455  opexpr = (OpExpr *) rinfo->clause;
456 
457  /*
458  * Bail if the rinfo is not compatible. We need a join OpExpr
459  * with 2 args.
460  */
461  if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
462  !clause_sides_match_join(rinfo, outerrel, innerrel))
463  {
464  list_free(*operators);
465  list_free(*param_exprs);
466  return false;
467  }
468 
469  if (rinfo->outer_is_left)
470  {
471  expr = (Node *) linitial(opexpr->args);
472  hasheqoperator = rinfo->left_hasheqoperator;
473  }
474  else
475  {
476  expr = (Node *) lsecond(opexpr->args);
477  hasheqoperator = rinfo->right_hasheqoperator;
478  }
479 
480  /* can't do memoize if we can't hash the outer type */
481  if (!OidIsValid(hasheqoperator))
482  {
483  list_free(*operators);
484  list_free(*param_exprs);
485  return false;
486  }
487 
488  *operators = lappend_oid(*operators, hasheqoperator);
489  *param_exprs = lappend(*param_exprs, expr);
490 
491  /*
492  * When the join operator is not hashable then it's possible that
493  * the operator will be able to distinguish something that the
494  * hash equality operator could not. For example with floating
495  * point types -0.0 and +0.0 are classed as equal by the hash
496  * function and equality function, but some other operator may be
497  * able to tell those values apart. This means that we must put
498  * memoize into binary comparison mode so that it does bit-by-bit
499  * comparisons rather than a "logical" comparison as it would
500  * using the hash equality operator.
501  */
502  if (!OidIsValid(rinfo->hashjoinoperator))
503  *binary_mode = true;
504  }
505  }
506 
507  /* Now add any lateral vars to the cache key too */
508  foreach(lc, innerrel->lateral_vars)
509  {
510  Node *expr = (Node *) lfirst(lc);
511  TypeCacheEntry *typentry;
512 
513  /* Reject if there are any volatile functions */
514  if (contain_volatile_functions(expr))
515  {
516  list_free(*operators);
517  list_free(*param_exprs);
518  return false;
519  }
520 
521  typentry = lookup_type_cache(exprType(expr),
523 
524  /* can't use a memoize node without a valid hash equals operator */
525  if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
526  {
527  list_free(*operators);
528  list_free(*param_exprs);
529  return false;
530  }
531 
532  *operators = lappend_oid(*operators, typentry->eq_opr);
533  *param_exprs = lappend(*param_exprs, expr);
534 
535  /*
536  * We must go into binary mode as we don't have too much of an idea of
537  * how these lateral Vars are being used. See comment above when we
538  * set *binary_mode for the non-lateral Var case. This could be
539  * relaxed a bit if we had the RestrictInfos and knew the operators
540  * being used, however for cases like Vars that are arguments to
541  * functions we must operate in binary mode as we don't have
542  * visibility into what the function is doing with the Vars.
543  */
544  *binary_mode = true;
545  }
546 
547  /* We're okay to use memoize */
548  return true;
549 }
#define OidIsValid(objectId)
Definition: c.h:759
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:179
#define lsecond(l)
Definition: pg_list.h:183
unsigned int Oid
Definition: postgres_ext.h:31
List * args
Definition: primnodes.h:763
List * ppi_clauses
Definition: pathnodes.h:1549
Expr * clause
Definition: pathnodes.h:2516
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 2282 of file joinpath.c.

2289 {
2290  List *result_list = NIL;
2291  bool isouterjoin = IS_OUTER_JOIN(jointype);
2292  bool have_nonmergeable_joinclause = false;
2293  ListCell *l;
2294 
2295  foreach(l, restrictlist)
2296  {
2297  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2298 
2299  /*
2300  * If processing an outer join, only use its own join clauses in the
2301  * merge. For inner joins we can use pushed-down clauses too. (Note:
2302  * we don't set have_nonmergeable_joinclause here because pushed-down
2303  * clauses will become otherquals not joinquals.)
2304  */
2305  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2306  continue;
2307 
2308  /* Check that clause is a mergeable operator clause */
2309  if (!restrictinfo->can_join ||
2310  restrictinfo->mergeopfamilies == NIL)
2311  {
2312  /*
2313  * The executor can handle extra joinquals that are constants, but
2314  * not anything else, when doing right/right-anti/full merge join.
2315  * (The reason to support constants is so we can do FULL JOIN ON
2316  * FALSE.)
2317  */
2318  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2319  have_nonmergeable_joinclause = true;
2320  continue; /* not mergejoinable */
2321  }
2322 
2323  /*
2324  * Check if clause has the form "outer op inner" or "inner op outer".
2325  */
2326  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2327  {
2328  have_nonmergeable_joinclause = true;
2329  continue; /* no good for these input relations */
2330  }
2331 
2332  /*
2333  * Insist that each side have a non-redundant eclass. This
2334  * restriction is needed because various bits of the planner expect
2335  * that each clause in a merge be associable with some pathkey in a
2336  * canonical pathkey list, but redundant eclasses can't appear in
2337  * canonical sort orderings. (XXX it might be worth relaxing this,
2338  * but not enough time to address it for 8.3.)
2339  */
2340  update_mergeclause_eclasses(root, restrictinfo);
2341 
2342  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2343  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2344  {
2345  have_nonmergeable_joinclause = true;
2346  continue; /* can't handle redundant eclasses */
2347  }
2348 
2349  result_list = lappend(result_list, restrictinfo);
2350  }
2351 
2352  /*
2353  * Report whether mergejoin is allowed (see comment at top of function).
2354  */
2355  switch (jointype)
2356  {
2357  case JOIN_RIGHT:
2358  case JOIN_RIGHT_ANTI:
2359  case JOIN_FULL:
2360  *mergejoin_allowed = !have_nonmergeable_joinclause;
2361  break;
2362  default:
2363  *mergejoin_allowed = true;
2364  break;
2365  }
2366 
2367  return result_list;
2368 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1277
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1388

References RestrictInfo::clause, clause_sides_match_join(), EC_MUST_BE_REDUNDANT, IS_OUTER_JOIN, IsA, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, 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 1201 of file joinpath.c.

1207 {
1208  JoinType save_jointype = jointype;
1209  Path *outer_path;
1210  Path *inner_path;
1211  Path *cheapest_partial_outer = NULL;
1212  Path *cheapest_safe_inner = NULL;
1213  List *all_pathkeys;
1214  ListCell *l;
1215 
1216  /*
1217  * We only consider the cheapest-total-cost input paths, since we are
1218  * assuming here that a sort is required. We will consider
1219  * cheapest-startup-cost input paths later, and only if they don't need a
1220  * sort.
1221  *
1222  * This function intentionally does not consider parameterized input
1223  * paths, except when the cheapest-total is parameterized. If we did so,
1224  * we'd have a combinatorial explosion of mergejoin paths of dubious
1225  * value. This interacts with decisions elsewhere that also discriminate
1226  * against mergejoins with parameterized inputs; see comments in
1227  * src/backend/optimizer/README.
1228  */
1229  outer_path = outerrel->cheapest_total_path;
1230  inner_path = innerrel->cheapest_total_path;
1231 
1232  /*
1233  * If either cheapest-total path is parameterized by the other rel, we
1234  * can't use a mergejoin. (There's no use looking for alternative input
1235  * paths, since these should already be the least-parameterized available
1236  * paths.)
1237  */
1238  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1239  PATH_PARAM_BY_REL(inner_path, outerrel))
1240  return;
1241 
1242  /*
1243  * If unique-ification is requested, do it and then handle as a plain
1244  * inner join.
1245  */
1246  if (jointype == JOIN_UNIQUE_OUTER)
1247  {
1248  outer_path = (Path *) create_unique_path(root, outerrel,
1249  outer_path, extra->sjinfo);
1250  Assert(outer_path);
1251  jointype = JOIN_INNER;
1252  }
1253  else if (jointype == JOIN_UNIQUE_INNER)
1254  {
1255  inner_path = (Path *) create_unique_path(root, innerrel,
1256  inner_path, extra->sjinfo);
1257  Assert(inner_path);
1258  jointype = JOIN_INNER;
1259  }
1260 
1261  /*
1262  * If the joinrel is parallel-safe, we may be able to consider a partial
1263  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1264  * outer path will be partial, and therefore we won't be able to properly
1265  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1266  * and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1267  * Also, the resulting path must not be parameterized.
1268  */
1269  if (joinrel->consider_parallel &&
1270  save_jointype != JOIN_UNIQUE_OUTER &&
1271  save_jointype != JOIN_FULL &&
1272  save_jointype != JOIN_RIGHT &&
1273  save_jointype != JOIN_RIGHT_ANTI &&
1274  outerrel->partial_pathlist != NIL &&
1275  bms_is_empty(joinrel->lateral_relids))
1276  {
1277  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1278 
1279  if (inner_path->parallel_safe)
1280  cheapest_safe_inner = inner_path;
1281  else if (save_jointype != JOIN_UNIQUE_INNER)
1282  cheapest_safe_inner =
1284  }
1285 
1286  /*
1287  * Each possible ordering of the available mergejoin clauses will generate
1288  * a differently-sorted result path at essentially the same cost. We have
1289  * no basis for choosing one over another at this level of joining, but
1290  * some sort orders may be more useful than others for higher-level
1291  * mergejoins, so it's worth considering multiple orderings.
1292  *
1293  * Actually, it's not quite true that every mergeclause ordering will
1294  * generate a different path order, because some of the clauses may be
1295  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1296  * what we do is convert the mergeclause list to a list of canonical
1297  * pathkeys, and then consider different orderings of the pathkeys.
1298  *
1299  * Generating a path for *every* permutation of the pathkeys doesn't seem
1300  * like a winning strategy; the cost in planning time is too high. For
1301  * now, we generate one path for each pathkey, listing that pathkey first
1302  * and the rest in random order. This should allow at least a one-clause
1303  * mergejoin without re-sorting against any other possible mergejoin
1304  * partner path. But if we've not guessed the right ordering of secondary
1305  * keys, we may end up evaluating clauses as qpquals when they could have
1306  * been done as mergeclauses. (In practice, it's rare that there's more
1307  * than two or three mergeclauses, so expending a huge amount of thought
1308  * on that is probably not worth it.)
1309  *
1310  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1311  * some heuristics behind it (see that function), so be sure to try it
1312  * exactly as-is as well as making variants.
1313  */
1314  all_pathkeys = select_outer_pathkeys_for_merge(root,
1315  extra->mergeclause_list,
1316  joinrel);
1317 
1318  foreach(l, all_pathkeys)
1319  {
1320  PathKey *front_pathkey = (PathKey *) lfirst(l);
1321  List *cur_mergeclauses;
1322  List *outerkeys;
1323  List *innerkeys;
1324  List *merge_pathkeys;
1325 
1326  /* Make a pathkey list with this guy first */
1327  if (l != list_head(all_pathkeys))
1328  outerkeys = lcons(front_pathkey,
1329  list_delete_nth_cell(list_copy(all_pathkeys),
1330  foreach_current_index(l)));
1331  else
1332  outerkeys = all_pathkeys; /* no work at first one... */
1333 
1334  /* Sort the mergeclauses into the corresponding ordering */
1335  cur_mergeclauses =
1337  outerkeys,
1338  extra->mergeclause_list);
1339 
1340  /* Should have used them all... */
1341  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1342 
1343  /* Build sort pathkeys for the inner side */
1344  innerkeys = make_inner_pathkeys_for_merge(root,
1345  cur_mergeclauses,
1346  outerkeys);
1347 
1348  /* Build pathkeys representing output sort order */
1349  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1350  outerkeys);
1351 
1352  /*
1353  * And now we can make the path.
1354  *
1355  * Note: it's possible that the cheapest paths will already be sorted
1356  * properly. try_mergejoin_path will detect that case and suppress an
1357  * explicit sort step, so we needn't do so here.
1358  */
1359  try_mergejoin_path(root,
1360  joinrel,
1361  outer_path,
1362  inner_path,
1363  merge_pathkeys,
1364  cur_mergeclauses,
1365  outerkeys,
1366  innerkeys,
1367  jointype,
1368  extra,
1369  false);
1370 
1371  /*
1372  * If we have partial outer and parallel safe inner path then try
1373  * partial mergejoin path.
1374  */
1375  if (cheapest_partial_outer && cheapest_safe_inner)
1377  joinrel,
1378  cheapest_partial_outer,
1379  cheapest_safe_inner,
1380  merge_pathkeys,
1381  cur_mergeclauses,
1382  outerkeys,
1383  innerkeys,
1384  jointype,
1385  extra);
1386  }
1387 }
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:972
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:1426
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
#define foreach_current_index(cell)
Definition: pg_list.h:403

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_RIGHT_ANTI, 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 1042 of file joinpath.c.

1049 {
1050  Relids required_outer;
1051  JoinCostWorkspace workspace;
1052 
1053  /*
1054  * Check to see if proposed path is still parameterized, and reject if the
1055  * parameterization wouldn't be sensible.
1056  */
1057  required_outer = calc_non_nestloop_required_outer(outer_path,
1058  inner_path);
1059  if (required_outer &&
1060  !bms_overlap(required_outer, extra->param_source_rels))
1061  {
1062  /* Waste no memory when we reject a path here */
1063  bms_free(required_outer);
1064  return;
1065  }
1066 
1067  /*
1068  * See comments in try_nestloop_path(). Also note that hashjoin paths
1069  * never have any output pathkeys, per comments in create_hashjoin_path.
1070  */
1071  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1072  outer_path, inner_path, extra, false);
1073 
1074  if (add_path_precheck(joinrel,
1075  workspace.startup_cost, workspace.total_cost,
1076  NIL, required_outer))
1077  {
1078  add_path(joinrel, (Path *)
1079  create_hashjoin_path(root,
1080  joinrel,
1081  jointype,
1082  &workspace,
1083  extra,
1084  outer_path,
1085  inner_path,
1086  false, /* parallel_hash */
1087  extra->restrictlist,
1088  required_outer,
1089  hashclauses));
1090  }
1091  else
1092  {
1093  /* Waste no memory when we reject a path here */
1094  bms_free(required_outer);
1095  }
1096 }
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:3804
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2387
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, bool parallel_hash, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition: pathnode.c:2572
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 877 of file joinpath.c.

888 {
889  Relids required_outer;
890  JoinCostWorkspace workspace;
891 
892  if (is_partial)
893  {
895  joinrel,
896  outer_path,
897  inner_path,
898  pathkeys,
899  mergeclauses,
900  outersortkeys,
901  innersortkeys,
902  jointype,
903  extra);
904  return;
905  }
906 
907  /*
908  * Check to see if proposed path is still parameterized, and reject if the
909  * parameterization wouldn't be sensible.
910  */
911  required_outer = calc_non_nestloop_required_outer(outer_path,
912  inner_path);
913  if (required_outer &&
914  !bms_overlap(required_outer, extra->param_source_rels))
915  {
916  /* Waste no memory when we reject a path here */
917  bms_free(required_outer);
918  return;
919  }
920 
921  /*
922  * If the given paths are already well enough ordered, we can skip doing
923  * an explicit sort.
924  */
925  if (outersortkeys &&
926  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
927  outersortkeys = NIL;
928  if (innersortkeys &&
929  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
930  innersortkeys = NIL;
931 
932  /*
933  * See comments in try_nestloop_path().
934  */
935  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
936  outer_path, inner_path,
937  outersortkeys, innersortkeys,
938  extra);
939 
940  if (add_path_precheck(joinrel,
941  workspace.startup_cost, workspace.total_cost,
942  pathkeys, required_outer))
943  {
944  add_path(joinrel, (Path *)
946  joinrel,
947  jointype,
948  &workspace,
949  extra,
950  outer_path,
951  inner_path,
952  extra->restrictlist,
953  pathkeys,
954  required_outer,
955  mergeclauses,
956  outersortkeys,
957  innersortkeys));
958  }
959  else
960  {
961  /* Waste no memory when we reject a path here */
962  bms_free(required_outer);
963  }
964 }
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, JoinPathExtraData *extra)
Definition: costsize.c:3245
MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer, List *mergeclauses, List *outersortkeys, List *innersortkeys)
Definition: pathnode.c:2506

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

687 {
688  Relids required_outer;
689  JoinCostWorkspace workspace;
690  RelOptInfo *innerrel = inner_path->parent;
691  RelOptInfo *outerrel = outer_path->parent;
692  Relids innerrelids;
693  Relids outerrelids;
694  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
695  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
696 
697  /*
698  * Paths are parameterized by top-level parents, so run parameterization
699  * tests on the parent relids.
700  */
701  if (innerrel->top_parent_relids)
702  innerrelids = innerrel->top_parent_relids;
703  else
704  innerrelids = innerrel->relids;
705 
706  if (outerrel->top_parent_relids)
707  outerrelids = outerrel->top_parent_relids;
708  else
709  outerrelids = outerrel->relids;
710 
711  /*
712  * Check to see if proposed path is still parameterized, and reject if the
713  * parameterization wouldn't be sensible --- unless allow_star_schema_join
714  * says to allow it anyway. Also, we must reject if have_dangerous_phv
715  * doesn't like the look of it, which could only happen if the nestloop is
716  * still parameterized.
717  */
718  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
719  innerrelids, inner_paramrels);
720  if (required_outer &&
721  ((!bms_overlap(required_outer, extra->param_source_rels) &&
722  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
723  have_dangerous_phv(root, outerrelids, inner_paramrels)))
724  {
725  /* Waste no memory when we reject a path here */
726  bms_free(required_outer);
727  return;
728  }
729 
730  /* If we got past that, we shouldn't have any unsafe outer-join refs */
731  Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
732 
733  /*
734  * Do a precheck to quickly eliminate obviously-inferior paths. We
735  * calculate a cheap lower bound on the path's cost and then use
736  * add_path_precheck() to see if the path is clearly going to be dominated
737  * by some existing path for the joinrel. If not, do the full pushup with
738  * creating a fully valid path structure and submitting it to add_path().
739  * The latter two steps are expensive enough to make this two-phase
740  * methodology worthwhile.
741  */
742  initial_cost_nestloop(root, &workspace, jointype,
743  outer_path, inner_path, extra);
744 
745  if (add_path_precheck(joinrel,
746  workspace.startup_cost, workspace.total_cost,
747  pathkeys, required_outer))
748  {
749  /*
750  * If the inner path is parameterized, it is parameterized by the
751  * topmost parent of the outer rel, not the outer rel itself. Fix
752  * that.
753  */
754  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
755  {
756  inner_path = reparameterize_path_by_child(root, inner_path,
757  outer_path->parent);
758 
759  /*
760  * If we could not translate the path, we can't create nest loop
761  * path.
762  */
763  if (!inner_path)
764  {
765  bms_free(required_outer);
766  return;
767  }
768  }
769 
770  add_path(joinrel, (Path *)
772  joinrel,
773  jointype,
774  &workspace,
775  extra,
776  outer_path,
777  inner_path,
778  extra->restrictlist,
779  pathkeys,
780  required_outer));
781  }
782  else
783  {
784  /* Waste no memory when we reject a path here */
785  bms_free(required_outer);
786  }
787 }
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2964
#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:359
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1305
NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer)
Definition: pathnode.c:2420
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:4030

References add_path(), add_path_precheck(), allow_star_schema_join(), Assert(), 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 1108 of file joinpath.c.

1116 {
1117  JoinCostWorkspace workspace;
1118 
1119  /*
1120  * If the inner path is parameterized, the parameterization must be fully
1121  * satisfied by the proposed outer path. Parameterized partial paths are
1122  * not supported. The caller should already have verified that no lateral
1123  * rels are required here.
1124  */
1125  Assert(bms_is_empty(joinrel->lateral_relids));
1126  if (inner_path->param_info != NULL)
1127  {
1128  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1129 
1130  if (!bms_is_empty(inner_paramrels))
1131  return;
1132  }
1133 
1134  /*
1135  * Before creating a path, get a quick lower bound on what it is likely to
1136  * cost. Bail out right away if it looks terrible.
1137  */
1138  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1139  outer_path, inner_path, extra, parallel_hash);
1140  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
1141  return;
1142 
1143  /* Might be good enough to be worth trying, so let's try it. */
1144  add_partial_path(joinrel, (Path *)
1145  create_hashjoin_path(root,
1146  joinrel,
1147  jointype,
1148  &workspace,
1149  extra,
1150  outer_path,
1151  inner_path,
1152  parallel_hash,
1153  extra->restrictlist,
1154  NULL,
1155  hashclauses));
1156 }
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 972 of file joinpath.c.

982 {
983  JoinCostWorkspace workspace;
984 
985  /*
986  * See comments in try_partial_hashjoin_path().
987  */
989  if (inner_path->param_info != NULL)
990  {
991  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
992 
993  if (!bms_is_empty(inner_paramrels))
994  return;
995  }
996 
997  /*
998  * If the given paths are already well enough ordered, we can skip doing
999  * an explicit sort.
1000  */
1001  if (outersortkeys &&
1002  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1003  outersortkeys = NIL;
1004  if (innersortkeys &&
1005  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1006  innersortkeys = NIL;
1007 
1008  /*
1009  * See comments in try_partial_nestloop_path().
1010  */
1011  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1012  outer_path, inner_path,
1013  outersortkeys, innersortkeys,
1014  extra);
1015 
1016  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
1017  return;
1018 
1019  /* Might be good enough to be worth trying, so let's try it. */
1020  add_partial_path(joinrel, (Path *)
1021  create_mergejoin_path(root,
1022  joinrel,
1023  jointype,
1024  &workspace,
1025  extra,
1026  outer_path,
1027  inner_path,
1028  extra->restrictlist,
1029  pathkeys,
1030  NULL,
1031  mergeclauses,
1032  outersortkeys,
1033  innersortkeys));
1034 }

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

802 {
803  JoinCostWorkspace workspace;
804 
805  /*
806  * If the inner path is parameterized, the parameterization must be fully
807  * satisfied by the proposed outer path. Parameterized partial paths are
808  * not supported. The caller should already have verified that no lateral
809  * rels are required here.
810  */
812  if (inner_path->param_info != NULL)
813  {
814  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
815  RelOptInfo *outerrel = outer_path->parent;
816  Relids outerrelids;
817 
818  /*
819  * The inner and outer paths are parameterized, if at all, by the top
820  * level parents, not the child relations, so we must use those relids
821  * for our parameterization tests.
822  */
823  if (outerrel->top_parent_relids)
824  outerrelids = outerrel->top_parent_relids;
825  else
826  outerrelids = outerrel->relids;
827 
828  if (!bms_is_subset(inner_paramrels, outerrelids))
829  return;
830  }
831 
832  /*
833  * Before creating a path, get a quick lower bound on what it is likely to
834  * cost. Bail out right away if it looks terrible.
835  */
836  initial_cost_nestloop(root, &workspace, jointype,
837  outer_path, inner_path, extra);
838  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
839  return;
840 
841  /*
842  * If the inner path is parameterized, it is parameterized by the topmost
843  * parent of the outer rel, not the outer rel itself. Fix that.
844  */
845  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
846  {
847  inner_path = reparameterize_path_by_child(root, inner_path,
848  outer_path->parent);
849 
850  /*
851  * If we could not translate the path, we can't create nest loop path.
852  */
853  if (!inner_path)
854  return;
855  }
856 
857  /* Might be good enough to be worth trying, so let's try it. */
858  add_partial_path(joinrel, (Path *)
860  joinrel,
861  jointype,
862  &workspace,
863  extra,
864  outer_path,
865  inner_path,
866  extra->restrictlist,
867  pathkeys,
868  NULL));
869 }

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