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

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. They
337  * could add new paths (such as CustomPaths) by calling add_path(), or
338  * add_partial_path() if parallel aware. They could also delete or modify
339  * paths added by the core code.
340  */
342  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
343  jointype, &extra);
344 }
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:1243
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:425
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:359
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:930
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:5004
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:2358
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1277
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:2104
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1728
@ JOIN_SEMI
Definition: nodes.h:297
@ JOIN_FULL
Definition: nodes.h:285
@ JOIN_INNER
Definition: nodes.h:283
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:305
@ JOIN_UNIQUE_INNER
Definition: nodes.h:306
@ JOIN_ANTI
Definition: nodes.h:298
@ 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:3205
Relids param_source_rels
Definition: pathnodes.h:3209
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3208
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3207
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:990
Relids lateral_relids
Definition: pathnodes.h:898
RelOptKind reloptkind
Definition: pathnodes.h:850
Relids min_righthand
Definition: pathnodes.h:2869
JoinType jointype
Definition: pathnodes.h:2872
Relids min_lefthand
Definition: pathnodes.h:2868

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

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

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

1247 {
1248  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
1249  bms_is_subset(rinfo->right_relids, innerrel->relids))
1250  {
1251  /* lefthand side is outer */
1252  rinfo->outer_is_left = true;
1253  return true;
1254  }
1255  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
1256  bms_is_subset(rinfo->right_relids, outerrel->relids))
1257  {
1258  /* righthand side is outer */
1259  rinfo->outer_is_left = false;
1260  return true;
1261  }
1262  return false; /* no good for these input relations */
1263 }

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

1987 {
1988  ListCell *lc1;
1989 
1990  /* generate merge join path for each partial outer path */
1991  foreach(lc1, outerrel->partial_pathlist)
1992  {
1993  Path *outerpath = (Path *) lfirst(lc1);
1994  List *merge_pathkeys;
1995 
1996  /*
1997  * Figure out what useful ordering any paths we create will have.
1998  */
1999  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
2000  outerpath->pathkeys);
2001 
2002  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
2003  extra, false, inner_cheapest_total,
2004  merge_pathkeys, true);
2005  }
2006 }
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:1480
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1311
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1645
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 2020 of file joinpath.c.

2026 {
2027  JoinType save_jointype = jointype;
2028  ListCell *lc1;
2029 
2030  if (jointype == JOIN_UNIQUE_INNER)
2031  jointype = JOIN_INNER;
2032 
2033  foreach(lc1, outerrel->partial_pathlist)
2034  {
2035  Path *outerpath = (Path *) lfirst(lc1);
2036  List *pathkeys;
2037  ListCell *lc2;
2038 
2039  /* Figure out what useful ordering any paths we create will have. */
2040  pathkeys = build_join_pathkeys(root, joinrel, jointype,
2041  outerpath->pathkeys);
2042 
2043  /*
2044  * Try the cheapest parameterized paths; only those which will produce
2045  * an unparameterized path when joined to this outerrel will survive
2046  * try_partial_nestloop_path. The cheapest unparameterized path is
2047  * also in this list.
2048  */
2049  foreach(lc2, innerrel->cheapest_parameterized_paths)
2050  {
2051  Path *innerpath = (Path *) lfirst(lc2);
2052  Path *mpath;
2053 
2054  /* Can't join to an inner path that is not parallel-safe */
2055  if (!innerpath->parallel_safe)
2056  continue;
2057 
2058  /*
2059  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
2060  * cheapest_total_path, and we have to unique-ify it. (We might
2061  * be able to relax this to allow other safe, unparameterized
2062  * inner paths, but right now create_unique_path is not on board
2063  * with that.)
2064  */
2065  if (save_jointype == JOIN_UNIQUE_INNER)
2066  {
2067  if (innerpath != innerrel->cheapest_total_path)
2068  continue;
2069  innerpath = (Path *) create_unique_path(root, innerrel,
2070  innerpath,
2071  extra->sjinfo);
2072  Assert(innerpath);
2073  }
2074 
2075  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
2076  pathkeys, jointype, extra);
2077 
2078  /*
2079  * Try generating a memoize path and see if that makes the nested
2080  * loop any cheaper.
2081  */
2082  mpath = get_memoize_path(root, innerrel, outerrel,
2083  innerpath, outerpath, jointype,
2084  extra);
2085  if (mpath != NULL)
2086  try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2087  pathkeys, jointype, extra);
2088  }
2089  }
2090 }
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:580
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:849
Assert(fmt[strlen(fmt) - 1] !='\n')
JoinType
Definition: nodes.h:278
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1656
bool parallel_safe
Definition: pathnodes.h:1635
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 1480 of file joinpath.c.

1490 {
1491  List *mergeclauses;
1492  List *innersortkeys;
1493  List *trialsortkeys;
1494  Path *cheapest_startup_inner;
1495  Path *cheapest_total_inner;
1496  JoinType save_jointype = jointype;
1497  int num_sortkeys;
1498  int sortkeycnt;
1499 
1500  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1501  jointype = JOIN_INNER;
1502 
1503  /* Look for useful mergeclauses (if any) */
1504  mergeclauses =
1506  outerpath->pathkeys,
1507  extra->mergeclause_list);
1508 
1509  /*
1510  * Done with this outer path if no chance for a mergejoin.
1511  *
1512  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1513  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1514  * but since mergejoin is our only join type that supports FULL JOIN
1515  * without any join clauses, it's necessary to generate a clauseless
1516  * mergejoin path instead.
1517  */
1518  if (mergeclauses == NIL)
1519  {
1520  if (jointype == JOIN_FULL)
1521  /* okay to try for mergejoin */ ;
1522  else
1523  return;
1524  }
1525  if (useallclauses &&
1526  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1527  return;
1528 
1529  /* Compute the required ordering of the inner path */
1530  innersortkeys = make_inner_pathkeys_for_merge(root,
1531  mergeclauses,
1532  outerpath->pathkeys);
1533 
1534  /*
1535  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1536  * a sort will be needed, only cheapest total cost matters. (But
1537  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1538  * already correctly sorted.)
1539  */
1540  try_mergejoin_path(root,
1541  joinrel,
1542  outerpath,
1543  inner_cheapest_total,
1544  merge_pathkeys,
1545  mergeclauses,
1546  NIL,
1547  innersortkeys,
1548  jointype,
1549  extra,
1550  is_partial);
1551 
1552  /* Can't do anything else if inner path needs to be unique'd */
1553  if (save_jointype == JOIN_UNIQUE_INNER)
1554  return;
1555 
1556  /*
1557  * Look for presorted inner paths that satisfy the innersortkey list ---
1558  * or any truncation thereof, if we are allowed to build a mergejoin using
1559  * a subset of the merge clauses. Here, we consider both cheap startup
1560  * cost and cheap total cost.
1561  *
1562  * Currently we do not consider parameterized inner paths here. This
1563  * interacts with decisions elsewhere that also discriminate against
1564  * mergejoins with parameterized inputs; see comments in
1565  * src/backend/optimizer/README.
1566  *
1567  * As we shorten the sortkey list, we should consider only paths that are
1568  * strictly cheaper than (in particular, not the same as) any path found
1569  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1570  * merge keys than a given path allows (treating the rest as plain
1571  * joinquals), which is unlikely to be a good idea. Also, eliminating
1572  * paths here on the basis of compare_path_costs is a lot cheaper than
1573  * building the mergejoin path only to throw it away.
1574  *
1575  * If inner_cheapest_total is well enough sorted to have not required a
1576  * sort in the path made above, we shouldn't make a duplicate path with
1577  * it, either. We handle that case with the same logic that handles the
1578  * previous consideration, by initializing the variables that track
1579  * cheapest-so-far properly. Note that we do NOT reject
1580  * inner_cheapest_total if we find it matches some shorter set of
1581  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1582  * sorting inner_cheapest_total, whereas we did sort it above, so the
1583  * plans being considered are different.
1584  */
1585  if (pathkeys_contained_in(innersortkeys,
1586  inner_cheapest_total->pathkeys))
1587  {
1588  /* inner_cheapest_total didn't require a sort */
1589  cheapest_startup_inner = inner_cheapest_total;
1590  cheapest_total_inner = inner_cheapest_total;
1591  }
1592  else
1593  {
1594  /* it did require a sort, at least for the full set of keys */
1595  cheapest_startup_inner = NULL;
1596  cheapest_total_inner = NULL;
1597  }
1598  num_sortkeys = list_length(innersortkeys);
1599  if (num_sortkeys > 1 && !useallclauses)
1600  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1601  else
1602  trialsortkeys = innersortkeys; /* won't really truncate */
1603 
1604  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1605  {
1606  Path *innerpath;
1607  List *newclauses = NIL;
1608 
1609  /*
1610  * Look for an inner path ordered well enough for the first
1611  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1612  * destructively, which is why we made a copy...
1613  */
1614  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1615  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1616  trialsortkeys,
1617  NULL,
1618  TOTAL_COST,
1619  is_partial);
1620  if (innerpath != NULL &&
1621  (cheapest_total_inner == NULL ||
1622  compare_path_costs(innerpath, cheapest_total_inner,
1623  TOTAL_COST) < 0))
1624  {
1625  /* Found a cheap (or even-cheaper) sorted path */
1626  /* Select the right mergeclauses, if we didn't already */
1627  if (sortkeycnt < num_sortkeys)
1628  {
1629  newclauses =
1631  mergeclauses,
1632  trialsortkeys);
1633  Assert(newclauses != NIL);
1634  }
1635  else
1636  newclauses = mergeclauses;
1637  try_mergejoin_path(root,
1638  joinrel,
1639  outerpath,
1640  innerpath,
1641  merge_pathkeys,
1642  newclauses,
1643  NIL,
1644  NIL,
1645  jointype,
1646  extra,
1647  is_partial);
1648  cheapest_total_inner = innerpath;
1649  }
1650  /* Same on the basis of cheapest startup cost ... */
1651  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1652  trialsortkeys,
1653  NULL,
1654  STARTUP_COST,
1655  is_partial);
1656  if (innerpath != NULL &&
1657  (cheapest_startup_inner == NULL ||
1658  compare_path_costs(innerpath, cheapest_startup_inner,
1659  STARTUP_COST) < 0))
1660  {
1661  /* Found a cheap (or even-cheaper) sorted path */
1662  if (innerpath != cheapest_total_inner)
1663  {
1664  /*
1665  * Avoid rebuilding clause list if we already made one; saves
1666  * memory in big join trees...
1667  */
1668  if (newclauses == NIL)
1669  {
1670  if (sortkeycnt < num_sortkeys)
1671  {
1672  newclauses =
1674  mergeclauses,
1675  trialsortkeys);
1676  Assert(newclauses != NIL);
1677  }
1678  else
1679  newclauses = mergeclauses;
1680  }
1681  try_mergejoin_path(root,
1682  joinrel,
1683  outerpath,
1684  innerpath,
1685  merge_pathkeys,
1686  newclauses,
1687  NIL,
1688  NIL,
1689  jointype,
1690  extra,
1691  is_partial);
1692  }
1693  cheapest_startup_inner = innerpath;
1694  }
1695 
1696  /*
1697  * Don't consider truncated sortkeys if we need all clauses.
1698  */
1699  if (useallclauses)
1700  break;
1701  }
1702 }
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:931
List * list_truncate(List *list, int new_size)
Definition: list.c:631
List * list_copy(const List *oldlist)
Definition: list.c:1573
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1840
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:637
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1529
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1943
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:343
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 580 of file joinpath.c.

584 {
585  List *param_exprs;
586  List *hash_operators;
587  ListCell *lc;
588  bool binary_mode;
589 
590  /* Obviously not if it's disabled */
591  if (!enable_memoize)
592  return NULL;
593 
594  /*
595  * We can safely not bother with all this unless we expect to perform more
596  * than one inner scan. The first scan is always going to be a cache
597  * miss. This would likely fail later anyway based on costs, so this is
598  * really just to save some wasted effort.
599  */
600  if (outer_path->parent->rows < 2)
601  return NULL;
602 
603  /*
604  * We can only have a memoize node when there's some kind of cache key,
605  * either parameterized path clauses or lateral Vars. No cache key sounds
606  * more like something a Materialize node might be more useful for.
607  */
608  if ((inner_path->param_info == NULL ||
609  inner_path->param_info->ppi_clauses == NIL) &&
610  innerrel->lateral_vars == NIL)
611  return NULL;
612 
613  /*
614  * Currently we don't do this for SEMI and ANTI joins unless they're
615  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
616  * don't scan the inner node to completion, which will mean memoize cannot
617  * mark the cache entry as complete.
618  *
619  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
620  * = true. Should we? See add_paths_to_joinrel()
621  */
622  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
623  jointype == JOIN_ANTI))
624  return NULL;
625 
626  /*
627  * Memoize normally marks cache entries as complete when it runs out of
628  * tuples to read from its subplan. However, with unique joins, Nested
629  * Loop will skip to the next outer tuple after finding the first matching
630  * inner tuple. This means that we may not read the inner side of the
631  * join to completion which leaves no opportunity to mark the cache entry
632  * as complete. To work around that, when the join is unique we
633  * automatically mark cache entries as complete after fetching the first
634  * tuple. This works when the entire join condition is parameterized.
635  * Otherwise, when the parameterization is only a subset of the join
636  * condition, we can't be sure which part of it causes the join to be
637  * unique. This means there are no guarantees that only 1 tuple will be
638  * read. We cannot mark the cache entry as complete after reading the
639  * first tuple without that guarantee. This means the scope of Memoize
640  * node's usefulness is limited to only outer rows that have no join
641  * partner as this is the only case where Nested Loop would exhaust the
642  * inner scan of a unique join. Since the scope is limited to that, we
643  * just don't bother making a memoize path in this case.
644  *
645  * Lateral vars needn't be considered here as they're not considered when
646  * determining if the join is unique.
647  *
648  * XXX this could be enabled if the remaining join quals were made part of
649  * the inner scan's filter instead of the join filter. Maybe it's worth
650  * considering doing that?
651  */
652  if (extra->inner_unique &&
653  (inner_path->param_info == NULL ||
654  bms_num_members(inner_path->param_info->ppi_serials) <
655  list_length(extra->restrictlist)))
656  return NULL;
657 
658  /*
659  * We can't use a memoize node if there are volatile functions in the
660  * inner rel's target list or restrict list. A cache hit could reduce the
661  * number of calls to these functions.
662  */
663  if (contain_volatile_functions((Node *) innerrel->reltarget))
664  return NULL;
665 
666  foreach(lc, innerrel->baserestrictinfo)
667  {
668  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
669 
670  if (contain_volatile_functions((Node *) rinfo))
671  return NULL;
672  }
673 
674  /*
675  * Also check the parameterized path restrictinfos for volatile functions.
676  * Indexed functions must be immutable so shouldn't have any volatile
677  * functions, however, with a lateral join the inner scan may not be an
678  * index scan.
679  */
680  if (inner_path->param_info != NULL)
681  {
682  foreach(lc, inner_path->param_info->ppi_clauses)
683  {
684  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
685 
686  if (contain_volatile_functions((Node *) rinfo))
687  return NULL;
688  }
689  }
690 
691  /* Check if we have hash ops for each parameter to the path */
693  inner_path->param_info,
694  outerrel->top_parent ?
695  outerrel->top_parent : outerrel,
696  innerrel,
697  &param_exprs,
698  &hash_operators,
699  &binary_mode))
700  {
701  return (Path *) create_memoize_path(root,
702  innerrel,
703  inner_path,
704  param_exprs,
705  hash_operators,
706  extra->inner_unique,
707  binary_mode,
708  outer_path->rows);
709  }
710 
711  return NULL;
712 }
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:764
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:521
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:438
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:1600
Definition: nodes.h:129
Cardinality rows
Definition: pathnodes.h:1640
List * baserestrictinfo
Definition: pathnodes.h:966
struct PathTarget * reltarget
Definition: pathnodes.h:878
List * lateral_vars
Definition: pathnodes.h:921

References RelOptInfo::baserestrictinfo, bms_num_members(), 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 2104 of file joinpath.c.

2110 {
2111  JoinType save_jointype = jointype;
2112  bool isouterjoin = IS_OUTER_JOIN(jointype);
2113  List *hashclauses;
2114  ListCell *l;
2115 
2116  /*
2117  * We need to build only one hashclauses list for any given pair of outer
2118  * and inner relations; all of the hashable clauses will be used as keys.
2119  *
2120  * Scan the join's restrictinfo list to find hashjoinable clauses that are
2121  * usable with this pair of sub-relations.
2122  */
2123  hashclauses = NIL;
2124  foreach(l, extra->restrictlist)
2125  {
2126  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2127 
2128  /*
2129  * If processing an outer join, only use its own join clauses for
2130  * hashing. For inner joins we need not be so picky.
2131  */
2132  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2133  continue;
2134 
2135  if (!restrictinfo->can_join ||
2136  restrictinfo->hashjoinoperator == InvalidOid)
2137  continue; /* not hashjoinable */
2138 
2139  /*
2140  * Check if clause has the form "outer op inner" or "inner op outer".
2141  */
2142  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2143  continue; /* no good for these input relations */
2144 
2145  hashclauses = lappend(hashclauses, restrictinfo);
2146  }
2147 
2148  /* If we found any usable hashclauses, make paths */
2149  if (hashclauses)
2150  {
2151  /*
2152  * We consider both the cheapest-total-cost and cheapest-startup-cost
2153  * outer paths. There's no need to consider any but the
2154  * cheapest-total-cost inner path, however.
2155  */
2156  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2157  Path *cheapest_total_outer = outerrel->cheapest_total_path;
2158  Path *cheapest_total_inner = innerrel->cheapest_total_path;
2159 
2160  /*
2161  * If either cheapest-total path is parameterized by the other rel, we
2162  * can't use a hashjoin. (There's no use looking for alternative
2163  * input paths, since these should already be the least-parameterized
2164  * available paths.)
2165  */
2166  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2167  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2168  return;
2169 
2170  /* Unique-ify if need be; we ignore parameterized possibilities */
2171  if (jointype == JOIN_UNIQUE_OUTER)
2172  {
2173  cheapest_total_outer = (Path *)
2174  create_unique_path(root, outerrel,
2175  cheapest_total_outer, extra->sjinfo);
2176  Assert(cheapest_total_outer);
2177  jointype = JOIN_INNER;
2178  try_hashjoin_path(root,
2179  joinrel,
2180  cheapest_total_outer,
2181  cheapest_total_inner,
2182  hashclauses,
2183  jointype,
2184  extra);
2185  /* no possibility of cheap startup here */
2186  }
2187  else if (jointype == JOIN_UNIQUE_INNER)
2188  {
2189  cheapest_total_inner = (Path *)
2190  create_unique_path(root, innerrel,
2191  cheapest_total_inner, extra->sjinfo);
2192  Assert(cheapest_total_inner);
2193  jointype = JOIN_INNER;
2194  try_hashjoin_path(root,
2195  joinrel,
2196  cheapest_total_outer,
2197  cheapest_total_inner,
2198  hashclauses,
2199  jointype,
2200  extra);
2201  if (cheapest_startup_outer != NULL &&
2202  cheapest_startup_outer != cheapest_total_outer)
2203  try_hashjoin_path(root,
2204  joinrel,
2205  cheapest_startup_outer,
2206  cheapest_total_inner,
2207  hashclauses,
2208  jointype,
2209  extra);
2210  }
2211  else
2212  {
2213  /*
2214  * For other jointypes, we consider the cheapest startup outer
2215  * together with the cheapest total inner, and then consider
2216  * pairings of cheapest-total paths including parameterized ones.
2217  * There is no use in generating parameterized paths on the basis
2218  * of possibly cheap startup cost, so this is sufficient.
2219  */
2220  ListCell *lc1;
2221  ListCell *lc2;
2222 
2223  if (cheapest_startup_outer != NULL)
2224  try_hashjoin_path(root,
2225  joinrel,
2226  cheapest_startup_outer,
2227  cheapest_total_inner,
2228  hashclauses,
2229  jointype,
2230  extra);
2231 
2232  foreach(lc1, outerrel->cheapest_parameterized_paths)
2233  {
2234  Path *outerpath = (Path *) lfirst(lc1);
2235 
2236  /*
2237  * We cannot use an outer path that is parameterized by the
2238  * inner rel.
2239  */
2240  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2241  continue;
2242 
2243  foreach(lc2, innerrel->cheapest_parameterized_paths)
2244  {
2245  Path *innerpath = (Path *) lfirst(lc2);
2246 
2247  /*
2248  * We cannot use an inner path that is parameterized by
2249  * the outer rel, either.
2250  */
2251  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2252  continue;
2253 
2254  if (outerpath == cheapest_startup_outer &&
2255  innerpath == cheapest_total_inner)
2256  continue; /* already tried it */
2257 
2258  try_hashjoin_path(root,
2259  joinrel,
2260  outerpath,
2261  innerpath,
2262  hashclauses,
2263  jointype,
2264  extra);
2265  }
2266  }
2267  }
2268 
2269  /*
2270  * If the joinrel is parallel-safe, we may be able to consider a
2271  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2272  * because the outer path will be partial, and therefore we won't be
2273  * able to properly guarantee uniqueness. Also, the resulting path
2274  * must not be parameterized.
2275  */
2276  if (joinrel->consider_parallel &&
2277  save_jointype != JOIN_UNIQUE_OUTER &&
2278  outerrel->partial_pathlist != NIL &&
2279  bms_is_empty(joinrel->lateral_relids))
2280  {
2281  Path *cheapest_partial_outer;
2282  Path *cheapest_partial_inner = NULL;
2283  Path *cheapest_safe_inner = NULL;
2284 
2285  cheapest_partial_outer =
2286  (Path *) linitial(outerrel->partial_pathlist);
2287 
2288  /*
2289  * Can we use a partial inner plan too, so that we can build a
2290  * shared hash table in parallel? We can't handle
2291  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2292  */
2293  if (innerrel->partial_pathlist != NIL &&
2294  save_jointype != JOIN_UNIQUE_INNER &&
2296  {
2297  cheapest_partial_inner =
2298  (Path *) linitial(innerrel->partial_pathlist);
2299  try_partial_hashjoin_path(root, joinrel,
2300  cheapest_partial_outer,
2301  cheapest_partial_inner,
2302  hashclauses, jointype, extra,
2303  true /* parallel_hash */ );
2304  }
2305 
2306  /*
2307  * Normally, given that the joinrel is parallel-safe, the cheapest
2308  * total inner path will also be parallel-safe, but if not, we'll
2309  * have to search for the cheapest safe, unparameterized inner
2310  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2311  * inner path. If full, right, or right-anti join, we can't use
2312  * parallelism (building the hash table in each backend) because
2313  * no one process has all the match bits.
2314  */
2315  if (save_jointype == JOIN_FULL ||
2316  save_jointype == JOIN_RIGHT ||
2317  save_jointype == JOIN_RIGHT_ANTI)
2318  cheapest_safe_inner = NULL;
2319  else if (cheapest_total_inner->parallel_safe)
2320  cheapest_safe_inner = cheapest_total_inner;
2321  else if (save_jointype != JOIN_UNIQUE_INNER)
2322  cheapest_safe_inner =
2324 
2325  if (cheapest_safe_inner != NULL)
2326  try_partial_hashjoin_path(root, joinrel,
2327  cheapest_partial_outer,
2328  cheapest_safe_inner,
2329  hashclauses, jointype, extra,
2330  false /* parallel_hash */ );
2331  }
2332  }
2333 }
#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:1107
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1245
#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:1184
List * lappend(List *list, void *datum)
Definition: list.c:339
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:327
@ JOIN_RIGHT
Definition: nodes.h:286
@ JOIN_RIGHT_ANTI
Definition: nodes.h:299
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:716
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2698
#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 1728 of file joinpath.c.

1734 {
1735  JoinType save_jointype = jointype;
1736  bool nestjoinOK;
1737  bool useallclauses;
1738  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1739  Path *matpath = NULL;
1740  ListCell *lc1;
1741 
1742  /*
1743  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1744  * are doing a right, right-anti or full mergejoin, we must use *all* the
1745  * mergeclauses as join clauses, else we will not have a valid plan.
1746  * (Although these two flags are currently inverses, keep them separate
1747  * for clarity and possible future changes.)
1748  */
1749  switch (jointype)
1750  {
1751  case JOIN_INNER:
1752  case JOIN_LEFT:
1753  case JOIN_SEMI:
1754  case JOIN_ANTI:
1755  nestjoinOK = true;
1756  useallclauses = false;
1757  break;
1758  case JOIN_RIGHT:
1759  case JOIN_RIGHT_ANTI:
1760  case JOIN_FULL:
1761  nestjoinOK = false;
1762  useallclauses = true;
1763  break;
1764  case JOIN_UNIQUE_OUTER:
1765  case JOIN_UNIQUE_INNER:
1766  jointype = JOIN_INNER;
1767  nestjoinOK = true;
1768  useallclauses = false;
1769  break;
1770  default:
1771  elog(ERROR, "unrecognized join type: %d",
1772  (int) jointype);
1773  nestjoinOK = false; /* keep compiler quiet */
1774  useallclauses = false;
1775  break;
1776  }
1777 
1778  /*
1779  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1780  * we will consider it below as a member of cheapest_parameterized_paths,
1781  * but the other possibilities considered in this routine aren't usable.
1782  */
1783  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1784  inner_cheapest_total = NULL;
1785 
1786  /*
1787  * If we need to unique-ify the inner path, we will consider only the
1788  * cheapest-total inner.
1789  */
1790  if (save_jointype == JOIN_UNIQUE_INNER)
1791  {
1792  /* No way to do this with an inner path parameterized by outer rel */
1793  if (inner_cheapest_total == NULL)
1794  return;
1795  inner_cheapest_total = (Path *)
1796  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1797  Assert(inner_cheapest_total);
1798  }
1799  else if (nestjoinOK)
1800  {
1801  /*
1802  * Consider materializing the cheapest inner path, unless
1803  * enable_material is off or the path in question materializes its
1804  * output anyway.
1805  */
1806  if (enable_material && inner_cheapest_total != NULL &&
1807  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1808  matpath = (Path *)
1809  create_material_path(innerrel, inner_cheapest_total);
1810  }
1811 
1812  foreach(lc1, outerrel->pathlist)
1813  {
1814  Path *outerpath = (Path *) lfirst(lc1);
1815  List *merge_pathkeys;
1816 
1817  /*
1818  * We cannot use an outer path that is parameterized by the inner rel.
1819  */
1820  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1821  continue;
1822 
1823  /*
1824  * If we need to unique-ify the outer path, it's pointless to consider
1825  * any but the cheapest outer. (XXX we don't consider parameterized
1826  * outers, nor inners, for unique-ified cases. Should we?)
1827  */
1828  if (save_jointype == JOIN_UNIQUE_OUTER)
1829  {
1830  if (outerpath != outerrel->cheapest_total_path)
1831  continue;
1832  outerpath = (Path *) create_unique_path(root, outerrel,
1833  outerpath, extra->sjinfo);
1834  Assert(outerpath);
1835  }
1836 
1837  /*
1838  * The result will have this sort order (even if it is implemented as
1839  * a nestloop, and even if some of the mergeclauses are implemented by
1840  * qpquals rather than as true mergeclauses):
1841  */
1842  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1843  outerpath->pathkeys);
1844 
1845  if (save_jointype == JOIN_UNIQUE_INNER)
1846  {
1847  /*
1848  * Consider nestloop join, but only with the unique-ified cheapest
1849  * inner path
1850  */
1851  try_nestloop_path(root,
1852  joinrel,
1853  outerpath,
1854  inner_cheapest_total,
1855  merge_pathkeys,
1856  jointype,
1857  extra);
1858  }
1859  else if (nestjoinOK)
1860  {
1861  /*
1862  * Consider nestloop joins using this outer path and various
1863  * available paths for the inner relation. We consider the
1864  * cheapest-total paths for each available parameterization of the
1865  * inner relation, including the unparameterized case.
1866  */
1867  ListCell *lc2;
1868 
1869  foreach(lc2, innerrel->cheapest_parameterized_paths)
1870  {
1871  Path *innerpath = (Path *) lfirst(lc2);
1872  Path *mpath;
1873 
1874  try_nestloop_path(root,
1875  joinrel,
1876  outerpath,
1877  innerpath,
1878  merge_pathkeys,
1879  jointype,
1880  extra);
1881 
1882  /*
1883  * Try generating a memoize path and see if that makes the
1884  * nested loop any cheaper.
1885  */
1886  mpath = get_memoize_path(root, innerrel, outerrel,
1887  innerpath, outerpath, jointype,
1888  extra);
1889  if (mpath != NULL)
1890  try_nestloop_path(root,
1891  joinrel,
1892  outerpath,
1893  mpath,
1894  merge_pathkeys,
1895  jointype,
1896  extra);
1897  }
1898 
1899  /* Also consider materialized form of the cheapest inner path */
1900  if (matpath != NULL)
1901  try_nestloop_path(root,
1902  joinrel,
1903  outerpath,
1904  matpath,
1905  merge_pathkeys,
1906  jointype,
1907  extra);
1908  }
1909 
1910  /* Can't do anything else if outer path needs to be unique'd */
1911  if (save_jointype == JOIN_UNIQUE_OUTER)
1912  continue;
1913 
1914  /* Can't do anything else if inner rel is parameterized by outer */
1915  if (inner_cheapest_total == NULL)
1916  continue;
1917 
1918  /* Generate merge join paths */
1919  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1920  save_jointype, extra, useallclauses,
1921  inner_cheapest_total, merge_pathkeys,
1922  false);
1923  }
1924 
1925  /*
1926  * Consider partial nestloop and mergejoin plan if outerrel has any
1927  * partial path and the joinrel is parallel-safe. However, we can't
1928  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1929  * therefore we won't be able to properly guarantee uniqueness. Nor can
1930  * we handle joins needing lateral rels, since partial paths must not be
1931  * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
1932  * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1933  */
1934  if (joinrel->consider_parallel &&
1935  save_jointype != JOIN_UNIQUE_OUTER &&
1936  save_jointype != JOIN_FULL &&
1937  save_jointype != JOIN_RIGHT &&
1938  save_jointype != JOIN_RIGHT_ANTI &&
1939  outerrel->partial_pathlist != NIL &&
1940  bms_is_empty(joinrel->lateral_relids))
1941  {
1942  if (nestjoinOK)
1943  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1944  save_jointype, extra);
1945 
1946  /*
1947  * If inner_cheapest_total is NULL or non parallel-safe then find the
1948  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1949  * can't use any alternative inner path.
1950  */
1951  if (inner_cheapest_total == NULL ||
1952  !inner_cheapest_total->parallel_safe)
1953  {
1954  if (save_jointype == JOIN_UNIQUE_INNER)
1955  return;
1956 
1957  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1958  }
1959 
1960  if (inner_cheapest_total)
1961  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1962  save_jointype, extra,
1963  inner_cheapest_total);
1964  }
1965 }
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:720
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2020
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1980
@ JOIN_LEFT
Definition: nodes.h:284
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1568
NodeTag pathtype
Definition: pathnodes.h:1606

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

443 {
444  ListCell *lc;
445 
446  *param_exprs = NIL;
447  *operators = NIL;
448  *binary_mode = false;
449 
450  /* Add join clauses from param_info to the hash key */
451  if (param_info != NULL)
452  {
453  List *clauses = param_info->ppi_clauses;
454 
455  foreach(lc, clauses)
456  {
457  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
458  OpExpr *opexpr;
459  Node *expr;
460  Oid hasheqoperator;
461 
462  opexpr = (OpExpr *) rinfo->clause;
463 
464  /*
465  * Bail if the rinfo is not compatible. We need a join OpExpr
466  * with 2 args.
467  */
468  if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
469  !clause_sides_match_join(rinfo, outerrel, innerrel))
470  {
471  list_free(*operators);
472  list_free(*param_exprs);
473  return false;
474  }
475 
476  if (rinfo->outer_is_left)
477  {
478  expr = (Node *) linitial(opexpr->args);
479  hasheqoperator = rinfo->left_hasheqoperator;
480  }
481  else
482  {
483  expr = (Node *) lsecond(opexpr->args);
484  hasheqoperator = rinfo->right_hasheqoperator;
485  }
486 
487  /* can't do memoize if we can't hash the outer type */
488  if (!OidIsValid(hasheqoperator))
489  {
490  list_free(*operators);
491  list_free(*param_exprs);
492  return false;
493  }
494 
495  /*
496  * 'expr' may already exist as a parameter from a previous item in
497  * ppi_clauses. No need to include it again, however we'd better
498  * ensure we do switch into binary mode if required. See below.
499  */
500  if (!list_member(*param_exprs, expr))
501  {
502  *operators = lappend_oid(*operators, hasheqoperator);
503  *param_exprs = lappend(*param_exprs, expr);
504  }
505 
506  /*
507  * When the join operator is not hashable then it's possible that
508  * the operator will be able to distinguish something that the
509  * hash equality operator could not. For example with floating
510  * point types -0.0 and +0.0 are classed as equal by the hash
511  * function and equality function, but some other operator may be
512  * able to tell those values apart. This means that we must put
513  * memoize into binary comparison mode so that it does bit-by-bit
514  * comparisons rather than a "logical" comparison as it would
515  * using the hash equality operator.
516  */
517  if (!OidIsValid(rinfo->hashjoinoperator))
518  *binary_mode = true;
519  }
520  }
521 
522  /* Now add any lateral vars to the cache key too */
523  foreach(lc, innerrel->lateral_vars)
524  {
525  Node *expr = (Node *) lfirst(lc);
526  TypeCacheEntry *typentry;
527 
528  /* Reject if there are any volatile functions in lateral vars */
529  if (contain_volatile_functions(expr))
530  {
531  list_free(*operators);
532  list_free(*param_exprs);
533  return false;
534  }
535 
536  typentry = lookup_type_cache(exprType(expr),
538 
539  /* can't use memoize without a valid hash proc and equals operator */
540  if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
541  {
542  list_free(*operators);
543  list_free(*param_exprs);
544  return false;
545  }
546 
547  /*
548  * 'expr' may already exist as a parameter from the ppi_clauses. No
549  * need to include it again, however we'd better ensure we do switch
550  * into binary mode.
551  */
552  if (!list_member(*param_exprs, expr))
553  {
554  *operators = lappend_oid(*operators, typentry->eq_opr);
555  *param_exprs = lappend(*param_exprs, expr);
556  }
557 
558  /*
559  * We must go into binary mode as we don't have too much of an idea of
560  * how these lateral Vars are being used. See comment above when we
561  * set *binary_mode for the non-lateral Var case. This could be
562  * relaxed a bit if we had the RestrictInfos and knew the operators
563  * being used, however for cases like Vars that are arguments to
564  * functions we must operate in binary mode as we don't have
565  * visibility into what the function is doing with the Vars.
566  */
567  *binary_mode = true;
568  }
569 
570  /* We're okay to use memoize */
571  return true;
572 }
#define OidIsValid(objectId)
Definition: c.h:764
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
List * lappend_oid(List *list, Oid datum)
Definition: list.c:375
void list_free(List *list)
Definition: list.c:1546
bool list_member(const List *list, const void *datum)
Definition: list.c:661
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:43
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define lsecond(l)
Definition: pg_list.h:183
unsigned int Oid
Definition: postgres_ext.h:31
List * args
Definition: primnodes.h:771
List * ppi_clauses
Definition: pathnodes.h:1561
Expr * clause
Definition: pathnodes.h:2541
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:345
#define TYPECACHE_EQ_OPR
Definition: typcache.h:137
#define TYPECACHE_HASH_PROC
Definition: typcache.h:141

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(), list_member(), 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 2358 of file joinpath.c.

2365 {
2366  List *result_list = NIL;
2367  bool isouterjoin = IS_OUTER_JOIN(jointype);
2368  bool have_nonmergeable_joinclause = false;
2369  ListCell *l;
2370 
2371  foreach(l, restrictlist)
2372  {
2373  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2374 
2375  /*
2376  * If processing an outer join, only use its own join clauses in the
2377  * merge. For inner joins we can use pushed-down clauses too. (Note:
2378  * we don't set have_nonmergeable_joinclause here because pushed-down
2379  * clauses will become otherquals not joinquals.)
2380  */
2381  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2382  continue;
2383 
2384  /* Check that clause is a mergeable operator clause */
2385  if (!restrictinfo->can_join ||
2386  restrictinfo->mergeopfamilies == NIL)
2387  {
2388  /*
2389  * The executor can handle extra joinquals that are constants, but
2390  * not anything else, when doing right/right-anti/full merge join.
2391  * (The reason to support constants is so we can do FULL JOIN ON
2392  * FALSE.)
2393  */
2394  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2395  have_nonmergeable_joinclause = true;
2396  continue; /* not mergejoinable */
2397  }
2398 
2399  /*
2400  * Check if clause has the form "outer op inner" or "inner op outer".
2401  */
2402  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2403  {
2404  have_nonmergeable_joinclause = true;
2405  continue; /* no good for these input relations */
2406  }
2407 
2408  /*
2409  * Insist that each side have a non-redundant eclass. This
2410  * restriction is needed because various bits of the planner expect
2411  * that each clause in a merge be associable with some pathkey in a
2412  * canonical pathkey list, but redundant eclasses can't appear in
2413  * canonical sort orderings. (XXX it might be worth relaxing this,
2414  * but not enough time to address it for 8.3.)
2415  */
2416  update_mergeclause_eclasses(root, restrictinfo);
2417 
2418  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2419  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2420  {
2421  have_nonmergeable_joinclause = true;
2422  continue; /* can't handle redundant eclasses */
2423  }
2424 
2425  result_list = lappend(result_list, restrictinfo);
2426  }
2427 
2428  /*
2429  * Report whether mergejoin is allowed (see comment at top of function).
2430  */
2431  switch (jointype)
2432  {
2433  case JOIN_RIGHT:
2434  case JOIN_RIGHT_ANTI:
2435  case JOIN_FULL:
2436  *mergejoin_allowed = !have_nonmergeable_joinclause;
2437  break;
2438  default:
2439  *mergejoin_allowed = true;
2440  break;
2441  }
2442 
2443  return result_list;
2444 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1495
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1390

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

1283 {
1284  JoinType save_jointype = jointype;
1285  Path *outer_path;
1286  Path *inner_path;
1287  Path *cheapest_partial_outer = NULL;
1288  Path *cheapest_safe_inner = NULL;
1289  List *all_pathkeys;
1290  ListCell *l;
1291 
1292  /*
1293  * We only consider the cheapest-total-cost input paths, since we are
1294  * assuming here that a sort is required. We will consider
1295  * cheapest-startup-cost input paths later, and only if they don't need a
1296  * sort.
1297  *
1298  * This function intentionally does not consider parameterized input
1299  * paths, except when the cheapest-total is parameterized. If we did so,
1300  * we'd have a combinatorial explosion of mergejoin paths of dubious
1301  * value. This interacts with decisions elsewhere that also discriminate
1302  * against mergejoins with parameterized inputs; see comments in
1303  * src/backend/optimizer/README.
1304  */
1305  outer_path = outerrel->cheapest_total_path;
1306  inner_path = innerrel->cheapest_total_path;
1307 
1308  /*
1309  * If either cheapest-total path is parameterized by the other rel, we
1310  * can't use a mergejoin. (There's no use looking for alternative input
1311  * paths, since these should already be the least-parameterized available
1312  * paths.)
1313  */
1314  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1315  PATH_PARAM_BY_REL(inner_path, outerrel))
1316  return;
1317 
1318  /*
1319  * If unique-ification is requested, do it and then handle as a plain
1320  * inner join.
1321  */
1322  if (jointype == JOIN_UNIQUE_OUTER)
1323  {
1324  outer_path = (Path *) create_unique_path(root, outerrel,
1325  outer_path, extra->sjinfo);
1326  Assert(outer_path);
1327  jointype = JOIN_INNER;
1328  }
1329  else if (jointype == JOIN_UNIQUE_INNER)
1330  {
1331  inner_path = (Path *) create_unique_path(root, innerrel,
1332  inner_path, extra->sjinfo);
1333  Assert(inner_path);
1334  jointype = JOIN_INNER;
1335  }
1336 
1337  /*
1338  * If the joinrel is parallel-safe, we may be able to consider a partial
1339  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1340  * outer path will be partial, and therefore we won't be able to properly
1341  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1342  * and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1343  * Also, the resulting path must not be parameterized.
1344  */
1345  if (joinrel->consider_parallel &&
1346  save_jointype != JOIN_UNIQUE_OUTER &&
1347  save_jointype != JOIN_FULL &&
1348  save_jointype != JOIN_RIGHT &&
1349  save_jointype != JOIN_RIGHT_ANTI &&
1350  outerrel->partial_pathlist != NIL &&
1351  bms_is_empty(joinrel->lateral_relids))
1352  {
1353  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1354 
1355  if (inner_path->parallel_safe)
1356  cheapest_safe_inner = inner_path;
1357  else if (save_jointype != JOIN_UNIQUE_INNER)
1358  cheapest_safe_inner =
1360  }
1361 
1362  /*
1363  * Each possible ordering of the available mergejoin clauses will generate
1364  * a differently-sorted result path at essentially the same cost. We have
1365  * no basis for choosing one over another at this level of joining, but
1366  * some sort orders may be more useful than others for higher-level
1367  * mergejoins, so it's worth considering multiple orderings.
1368  *
1369  * Actually, it's not quite true that every mergeclause ordering will
1370  * generate a different path order, because some of the clauses may be
1371  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1372  * what we do is convert the mergeclause list to a list of canonical
1373  * pathkeys, and then consider different orderings of the pathkeys.
1374  *
1375  * Generating a path for *every* permutation of the pathkeys doesn't seem
1376  * like a winning strategy; the cost in planning time is too high. For
1377  * now, we generate one path for each pathkey, listing that pathkey first
1378  * and the rest in random order. This should allow at least a one-clause
1379  * mergejoin without re-sorting against any other possible mergejoin
1380  * partner path. But if we've not guessed the right ordering of secondary
1381  * keys, we may end up evaluating clauses as qpquals when they could have
1382  * been done as mergeclauses. (In practice, it's rare that there's more
1383  * than two or three mergeclauses, so expending a huge amount of thought
1384  * on that is probably not worth it.)
1385  *
1386  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1387  * some heuristics behind it (see that function), so be sure to try it
1388  * exactly as-is as well as making variants.
1389  */
1390  all_pathkeys = select_outer_pathkeys_for_merge(root,
1391  extra->mergeclause_list,
1392  joinrel);
1393 
1394  foreach(l, all_pathkeys)
1395  {
1396  PathKey *front_pathkey = (PathKey *) lfirst(l);
1397  List *cur_mergeclauses;
1398  List *outerkeys;
1399  List *innerkeys;
1400  List *merge_pathkeys;
1401 
1402  /* Make a pathkey list with this guy first */
1403  if (l != list_head(all_pathkeys))
1404  outerkeys = lcons(front_pathkey,
1405  list_delete_nth_cell(list_copy(all_pathkeys),
1406  foreach_current_index(l)));
1407  else
1408  outerkeys = all_pathkeys; /* no work at first one... */
1409 
1410  /* Sort the mergeclauses into the corresponding ordering */
1411  cur_mergeclauses =
1413  outerkeys,
1414  extra->mergeclause_list);
1415 
1416  /* Should have used them all... */
1417  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1418 
1419  /* Build sort pathkeys for the inner side */
1420  innerkeys = make_inner_pathkeys_for_merge(root,
1421  cur_mergeclauses,
1422  outerkeys);
1423 
1424  /* Build pathkeys representing output sort order */
1425  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1426  outerkeys);
1427 
1428  /*
1429  * And now we can make the path.
1430  *
1431  * Note: it's possible that the cheapest paths will already be sorted
1432  * properly. try_mergejoin_path will detect that case and suppress an
1433  * explicit sort step, so we needn't do so here.
1434  */
1435  try_mergejoin_path(root,
1436  joinrel,
1437  outer_path,
1438  inner_path,
1439  merge_pathkeys,
1440  cur_mergeclauses,
1441  outerkeys,
1442  innerkeys,
1443  jointype,
1444  extra,
1445  false);
1446 
1447  /*
1448  * If we have partial outer and parallel safe inner path then try
1449  * partial mergejoin path.
1450  */
1451  if (cheapest_partial_outer && cheapest_safe_inner)
1453  joinrel,
1454  cheapest_partial_outer,
1455  cheapest_safe_inner,
1456  merge_pathkeys,
1457  cur_mergeclauses,
1458  outerkeys,
1459  innerkeys,
1460  jointype,
1461  extra);
1462  }
1463 }
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:1037
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:767
List * lcons(void *datum, List *list)
Definition: list.c:495
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1644
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403
static ListCell * list_head(const List *l)
Definition: pg_list.h:128

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

1114 {
1115  Relids required_outer;
1116  JoinCostWorkspace workspace;
1117 
1118  /*
1119  * If we are forming an outer join at this join, it's nonsensical to use
1120  * an input path that uses the outer join as part of its parameterization.
1121  * (This can happen despite our join order restrictions, since those apply
1122  * to what is in an input relation not what its parameters are.)
1123  */
1124  if (extra->sjinfo->ojrelid != 0 &&
1125  (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1126  bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1127  return;
1128 
1129  /*
1130  * Check to see if proposed path is still parameterized, and reject if the
1131  * parameterization wouldn't be sensible.
1132  */
1133  required_outer = calc_non_nestloop_required_outer(outer_path,
1134  inner_path);
1135  if (required_outer &&
1136  !bms_overlap(required_outer, extra->param_source_rels))
1137  {
1138  /* Waste no memory when we reject a path here */
1139  bms_free(required_outer);
1140  return;
1141  }
1142 
1143  /*
1144  * See comments in try_nestloop_path(). Also note that hashjoin paths
1145  * never have any output pathkeys, per comments in create_hashjoin_path.
1146  */
1147  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1148  outer_path, inner_path, extra, false);
1149 
1150  if (add_path_precheck(joinrel,
1151  workspace.startup_cost, workspace.total_cost,
1152  NIL, required_outer))
1153  {
1154  add_path(joinrel, (Path *)
1155  create_hashjoin_path(root,
1156  joinrel,
1157  jointype,
1158  &workspace,
1159  extra,
1160  outer_path,
1161  inner_path,
1162  false, /* parallel_hash */
1163  extra->restrictlist,
1164  required_outer,
1165  hashclauses));
1166  }
1167  else
1168  {
1169  /* Waste no memory when we reject a path here */
1170  bms_free(required_outer);
1171  }
1172 }
void bms_free(Bitmapset *a)
Definition: bitmapset.c:252
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:523
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:4074
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2400
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:2604
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_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_hashjoin_path(), initial_cost_hashjoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, JoinPathExtraData::sjinfo, 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 931 of file joinpath.c.

942 {
943  Relids required_outer;
944  JoinCostWorkspace workspace;
945 
946  if (is_partial)
947  {
949  joinrel,
950  outer_path,
951  inner_path,
952  pathkeys,
953  mergeclauses,
954  outersortkeys,
955  innersortkeys,
956  jointype,
957  extra);
958  return;
959  }
960 
961  /*
962  * If we are forming an outer join at this join, it's nonsensical to use
963  * an input path that uses the outer join as part of its parameterization.
964  * (This can happen despite our join order restrictions, since those apply
965  * to what is in an input relation not what its parameters are.)
966  */
967  if (extra->sjinfo->ojrelid != 0 &&
968  (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
969  bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
970  return;
971 
972  /*
973  * Check to see if proposed path is still parameterized, and reject if the
974  * parameterization wouldn't be sensible.
975  */
976  required_outer = calc_non_nestloop_required_outer(outer_path,
977  inner_path);
978  if (required_outer &&
979  !bms_overlap(required_outer, extra->param_source_rels))
980  {
981  /* Waste no memory when we reject a path here */
982  bms_free(required_outer);
983  return;
984  }
985 
986  /*
987  * If the given paths are already well enough ordered, we can skip doing
988  * an explicit sort.
989  */
990  if (outersortkeys &&
991  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
992  outersortkeys = NIL;
993  if (innersortkeys &&
994  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
995  innersortkeys = NIL;
996 
997  /*
998  * See comments in try_nestloop_path().
999  */
1000  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1001  outer_path, inner_path,
1002  outersortkeys, innersortkeys,
1003  extra);
1004 
1005  if (add_path_precheck(joinrel,
1006  workspace.startup_cost, workspace.total_cost,
1007  pathkeys, required_outer))
1008  {
1009  add_path(joinrel, (Path *)
1010  create_mergejoin_path(root,
1011  joinrel,
1012  jointype,
1013  &workspace,
1014  extra,
1015  outer_path,
1016  inner_path,
1017  extra->restrictlist,
1018  pathkeys,
1019  required_outer,
1020  mergeclauses,
1021  outersortkeys,
1022  innersortkeys));
1023  }
1024  else
1025  {
1026  /* Waste no memory when we reject a path here */
1027  bms_free(required_outer);
1028  }
1029 }
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:3515
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:2538

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

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

727 {
728  Relids required_outer;
729  JoinCostWorkspace workspace;
730  RelOptInfo *innerrel = inner_path->parent;
731  RelOptInfo *outerrel = outer_path->parent;
732  Relids innerrelids;
733  Relids outerrelids;
734  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
735  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
736 
737  /*
738  * If we are forming an outer join at this join, it's nonsensical to use
739  * an input path that uses the outer join as part of its parameterization.
740  * (This can happen despite our join order restrictions, since those apply
741  * to what is in an input relation not what its parameters are.)
742  */
743  if (extra->sjinfo->ojrelid != 0 &&
744  (bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) ||
745  bms_is_member(extra->sjinfo->ojrelid, outer_paramrels)))
746  return;
747 
748  /*
749  * Any parameterization of the input paths refers to topmost parents of
750  * the relevant relations, because reparameterize_path_by_child() hasn't
751  * been called yet. So we must consider topmost parents of the relations
752  * being joined, too, while determining parameterization of the result and
753  * checking for disallowed parameterization cases.
754  */
755  if (innerrel->top_parent_relids)
756  innerrelids = innerrel->top_parent_relids;
757  else
758  innerrelids = innerrel->relids;
759 
760  if (outerrel->top_parent_relids)
761  outerrelids = outerrel->top_parent_relids;
762  else
763  outerrelids = outerrel->relids;
764 
765  /*
766  * Check to see if proposed path is still parameterized, and reject if the
767  * parameterization wouldn't be sensible --- unless allow_star_schema_join
768  * says to allow it anyway. Also, we must reject if have_dangerous_phv
769  * doesn't like the look of it, which could only happen if the nestloop is
770  * still parameterized.
771  */
772  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
773  innerrelids, inner_paramrels);
774  if (required_outer &&
775  ((!bms_overlap(required_outer, extra->param_source_rels) &&
776  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
777  have_dangerous_phv(root, outerrelids, inner_paramrels)))
778  {
779  /* Waste no memory when we reject a path here */
780  bms_free(required_outer);
781  return;
782  }
783 
784  /* If we got past that, we shouldn't have any unsafe outer-join refs */
785  Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
786 
787  /*
788  * Do a precheck to quickly eliminate obviously-inferior paths. We
789  * calculate a cheap lower bound on the path's cost and then use
790  * add_path_precheck() to see if the path is clearly going to be dominated
791  * by some existing path for the joinrel. If not, do the full pushup with
792  * creating a fully valid path structure and submitting it to add_path().
793  * The latter two steps are expensive enough to make this two-phase
794  * methodology worthwhile.
795  */
796  initial_cost_nestloop(root, &workspace, jointype,
797  outer_path, inner_path, extra);
798 
799  if (add_path_precheck(joinrel,
800  workspace.startup_cost, workspace.total_cost,
801  pathkeys, required_outer))
802  {
803  /*
804  * If the inner path is parameterized, it is parameterized by the
805  * topmost parent of the outer rel, not the outer rel itself. Fix
806  * that.
807  */
808  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
809  {
810  inner_path = reparameterize_path_by_child(root, inner_path,
811  outer_path->parent);
812 
813  /*
814  * If we could not translate the path, we can't create nest loop
815  * path.
816  */
817  if (!inner_path)
818  {
819  bms_free(required_outer);
820  return;
821  }
822  }
823 
824  add_path(joinrel, (Path *)
826  joinrel,
827  jointype,
828  &workspace,
829  extra,
830  outer_path,
831  inner_path,
832  extra->restrictlist,
833  pathkeys,
834  required_outer));
835  }
836  else
837  {
838  /* Waste no memory when we reject a path here */
839  bms_free(required_outer);
840  }
841 }
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:3234
#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:362
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1286
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:2452
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2373
Path * reparameterize_path_by_child(PlannerInfo *root, Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:4089

References add_path(), add_path_precheck(), allow_star_schema_join(), Assert(), bms_free(), bms_is_member(), bms_overlap(), calc_nestloop_required_outer(), create_nestloop_path(), have_dangerous_phv(), initial_cost_nestloop(), SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, reparameterize_path_by_child(), JoinPathExtraData::restrictlist, JoinPathExtraData::sjinfo, 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 1184 of file joinpath.c.

1192 {
1193  JoinCostWorkspace workspace;
1194 
1195  /*
1196  * If the inner path is parameterized, the parameterization must be fully
1197  * satisfied by the proposed outer path. Parameterized partial paths are
1198  * not supported. The caller should already have verified that no lateral
1199  * rels are required here.
1200  */
1201  Assert(bms_is_empty(joinrel->lateral_relids));
1202  if (inner_path->param_info != NULL)
1203  {
1204  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1205 
1206  if (!bms_is_empty(inner_paramrels))
1207  return;
1208  }
1209 
1210  /*
1211  * Before creating a path, get a quick lower bound on what it is likely to
1212  * cost. Bail out right away if it looks terrible.
1213  */
1214  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1215  outer_path, inner_path, extra, parallel_hash);
1216  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
1217  return;
1218 
1219  /* Might be good enough to be worth trying, so let's try it. */
1220  add_partial_path(joinrel, (Path *)
1221  create_hashjoin_path(root,
1222  joinrel,
1223  jointype,
1224  &workspace,
1225  extra,
1226  outer_path,
1227  inner_path,
1228  parallel_hash,
1229  extra->restrictlist,
1230  NULL,
1231  hashclauses));
1232 }
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 1037 of file joinpath.c.

1047 {
1048  JoinCostWorkspace workspace;
1049 
1050  /*
1051  * See comments in try_partial_hashjoin_path().
1052  */
1053  Assert(bms_is_empty(joinrel->lateral_relids));
1054  if (inner_path->param_info != NULL)
1055  {
1056  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1057 
1058  if (!bms_is_empty(inner_paramrels))
1059  return;
1060  }
1061 
1062  /*
1063  * If the given paths are already well enough ordered, we can skip doing
1064  * an explicit sort.
1065  */
1066  if (outersortkeys &&
1067  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1068  outersortkeys = NIL;
1069  if (innersortkeys &&
1070  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1071  innersortkeys = NIL;
1072 
1073  /*
1074  * See comments in try_partial_nestloop_path().
1075  */
1076  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1077  outer_path, inner_path,
1078  outersortkeys, innersortkeys,
1079  extra);
1080 
1081  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
1082  return;
1083 
1084  /* Might be good enough to be worth trying, so let's try it. */
1085  add_partial_path(joinrel, (Path *)
1086  create_mergejoin_path(root,
1087  joinrel,
1088  jointype,
1089  &workspace,
1090  extra,
1091  outer_path,
1092  inner_path,
1093  extra->restrictlist,
1094  pathkeys,
1095  NULL,
1096  mergeclauses,
1097  outersortkeys,
1098  innersortkeys));
1099 }

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

856 {
857  JoinCostWorkspace workspace;
858 
859  /*
860  * If the inner path is parameterized, the parameterization must be fully
861  * satisfied by the proposed outer path. Parameterized partial paths are
862  * not supported. The caller should already have verified that no lateral
863  * rels are required here.
864  */
866  if (inner_path->param_info != NULL)
867  {
868  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
869  RelOptInfo *outerrel = outer_path->parent;
870  Relids outerrelids;
871 
872  /*
873  * The inner and outer paths are parameterized, if at all, by the top
874  * level parents, not the child relations, so we must use those relids
875  * for our parameterization tests.
876  */
877  if (outerrel->top_parent_relids)
878  outerrelids = outerrel->top_parent_relids;
879  else
880  outerrelids = outerrel->relids;
881 
882  if (!bms_is_subset(inner_paramrels, outerrelids))
883  return;
884  }
885 
886  /*
887  * Before creating a path, get a quick lower bound on what it is likely to
888  * cost. Bail out right away if it looks terrible.
889  */
890  initial_cost_nestloop(root, &workspace, jointype,
891  outer_path, inner_path, extra);
892  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
893  return;
894 
895  /*
896  * If the inner path is parameterized, it is parameterized by the topmost
897  * parent of the outer rel, not the outer rel itself. Fix that.
898  */
899  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
900  {
901  inner_path = reparameterize_path_by_child(root, inner_path,
902  outer_path->parent);
903 
904  /*
905  * If we could not translate the path, we can't create nest loop path.
906  */
907  if (!inner_path)
908  return;
909  }
910 
911  /* Might be good enough to be worth trying, so let's try it. */
912  add_partial_path(joinrel, (Path *)
914  joinrel,
915  jointype,
916  &workspace,
917  extra,
918  outer_path,
919  inner_path,
920  extra->restrictlist,
921  pathkeys,
922  NULL));
923 }

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