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/placeholder.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "utils/lsyscache.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 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 *ph_lateral_vars, List **param_exprs, List **operators, bool *binary_mode)
 
static Listextract_lateral_vars_from_PHVs (PlannerInfo *root, Relids innerrelids)
 
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:582
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1679

Definition at line 40 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 46 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 43 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 124 of file joinpath.c.

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

References 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, 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, root, 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 363 of file joinpath.c.

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

References bms_nonempty_difference(), and bms_overlap().

Referenced by try_nestloop_path().

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

2055 {
2056  ListCell *lc1;
2057 
2058  /* generate merge join path for each partial outer path */
2059  foreach(lc1, outerrel->partial_pathlist)
2060  {
2061  Path *outerpath = (Path *) lfirst(lc1);
2062  List *merge_pathkeys;
2063 
2064  /*
2065  * Figure out what useful ordering any paths we create will have.
2066  */
2067  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
2068  outerpath->pathkeys);
2069 
2070  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
2071  extra, false, inner_cheapest_total,
2072  merge_pathkeys, true);
2073  }
2074 }
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:1541
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1294
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1675
List * partial_pathlist
Definition: pathnodes.h:900

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

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

2094 {
2095  JoinType save_jointype = jointype;
2096  Path *inner_cheapest_total = innerrel->cheapest_total_path;
2097  Path *matpath = NULL;
2098  ListCell *lc1;
2099 
2100  if (jointype == JOIN_UNIQUE_INNER)
2101  jointype = JOIN_INNER;
2102 
2103  /*
2104  * Consider materializing the cheapest inner path, unless: 1) we're doing
2105  * JOIN_UNIQUE_INNER, because in this case we have to unique-ify the
2106  * cheapest inner path, 2) enable_material is off, 3) the cheapest inner
2107  * path is not parallel-safe, 4) the cheapest inner path is parameterized
2108  * by the outer rel, or 5) the cheapest inner path materializes its output
2109  * anyway.
2110  */
2111  if (save_jointype != JOIN_UNIQUE_INNER &&
2112  enable_material && inner_cheapest_total->parallel_safe &&
2113  !PATH_PARAM_BY_REL(inner_cheapest_total, outerrel) &&
2114  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
2115  {
2116  matpath = (Path *)
2117  create_material_path(innerrel, inner_cheapest_total);
2118  Assert(matpath->parallel_safe);
2119  }
2120 
2121  foreach(lc1, outerrel->partial_pathlist)
2122  {
2123  Path *outerpath = (Path *) lfirst(lc1);
2124  List *pathkeys;
2125  ListCell *lc2;
2126 
2127  /* Figure out what useful ordering any paths we create will have. */
2128  pathkeys = build_join_pathkeys(root, joinrel, jointype,
2129  outerpath->pathkeys);
2130 
2131  /*
2132  * Try the cheapest parameterized paths; only those which will produce
2133  * an unparameterized path when joined to this outerrel will survive
2134  * try_partial_nestloop_path. The cheapest unparameterized path is
2135  * also in this list.
2136  */
2137  foreach(lc2, innerrel->cheapest_parameterized_paths)
2138  {
2139  Path *innerpath = (Path *) lfirst(lc2);
2140  Path *mpath;
2141 
2142  /* Can't join to an inner path that is not parallel-safe */
2143  if (!innerpath->parallel_safe)
2144  continue;
2145 
2146  /*
2147  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
2148  * cheapest_total_path, and we have to unique-ify it. (We might
2149  * be able to relax this to allow other safe, unparameterized
2150  * inner paths, but right now create_unique_path is not on board
2151  * with that.)
2152  */
2153  if (save_jointype == JOIN_UNIQUE_INNER)
2154  {
2155  if (innerpath != innerrel->cheapest_total_path)
2156  continue;
2157  innerpath = (Path *) create_unique_path(root, innerrel,
2158  innerpath,
2159  extra->sjinfo);
2160  Assert(innerpath);
2161  }
2162 
2163  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
2164  pathkeys, jointype, extra);
2165 
2166  /*
2167  * Try generating a memoize path and see if that makes the nested
2168  * loop any cheaper.
2169  */
2170  mpath = get_memoize_path(root, innerrel, outerrel,
2171  innerpath, outerpath, jointype,
2172  extra);
2173  if (mpath != NULL)
2174  try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2175  pathkeys, jointype, extra);
2176  }
2177 
2178  /* Also consider materialized form of the cheapest inner path */
2179  if (matpath != NULL)
2180  try_partial_nestloop_path(root, joinrel, outerpath, matpath,
2181  pathkeys, jointype, extra);
2182  }
2183 }
#define Assert(condition)
Definition: c.h:837
bool enable_material
Definition: costsize.c:154
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:635
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:675
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:46
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:947
JoinType
Definition: nodes.h:288
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1727
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1634
NodeTag pathtype
Definition: pathnodes.h:1635
bool parallel_safe
Definition: pathnodes.h:1664
List * cheapest_parameterized_paths
Definition: pathnodes.h:904
struct Path * cheapest_total_path
Definition: pathnodes.h:902

References Assert, build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, create_material_path(), create_unique_path(), enable_material, ExecMaterializesOutput(), get_memoize_path(), JOIN_INNER, JOIN_UNIQUE_INNER, lfirst, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, Path::pathkeys, Path::pathtype, root, JoinPathExtraData::sjinfo, and try_partial_nestloop_path().

Referenced by match_unsorted_outer().

◆ extract_lateral_vars_from_PHVs()

static List* extract_lateral_vars_from_PHVs ( PlannerInfo root,
Relids  innerrelids 
)
static

Definition at line 584 of file joinpath.c.

585 {
586  List *ph_lateral_vars = NIL;
587  ListCell *lc;
588 
589  /* Nothing would be found if the query contains no LATERAL RTEs */
590  if (!root->hasLateralRTEs)
591  return NIL;
592 
593  /*
594  * No need to consider PHVs that are due to be evaluated at joinrels,
595  * since we do not add Memoize nodes on top of joinrel paths.
596  */
597  if (bms_membership(innerrelids) == BMS_MULTIPLE)
598  return NIL;
599 
600  foreach(lc, root->placeholder_list)
601  {
602  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
603  List *vars;
604  ListCell *cell;
605 
606  /* PHV is uninteresting if no lateral refs */
607  if (phinfo->ph_lateral == NULL)
608  continue;
609 
610  /* PHV is uninteresting if not due to be evaluated at innerrelids */
611  if (!bms_equal(phinfo->ph_eval_at, innerrelids))
612  continue;
613 
614  /*
615  * If the PHV does not reference any rels in innerrelids, use its
616  * contained expression as a cache key rather than extracting the
617  * Vars/PHVs from it and using those. This can be beneficial in cases
618  * where the expression results in fewer distinct values to cache
619  * tuples for.
620  */
621  if (!bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
622  innerrelids))
623  {
624  ph_lateral_vars = lappend(ph_lateral_vars, phinfo->ph_var->phexpr);
625  continue;
626  }
627 
628  /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */
629  vars = pull_vars_of_level((Node *) phinfo->ph_var->phexpr, 0);
630  foreach(cell, vars)
631  {
632  Node *node = (Node *) lfirst(cell);
633 
634  if (IsA(node, Var))
635  {
636  Var *var = (Var *) node;
637 
638  Assert(var->varlevelsup == 0);
639 
640  if (bms_is_member(var->varno, phinfo->ph_lateral))
641  ph_lateral_vars = lappend(ph_lateral_vars, node);
642  }
643  else if (IsA(node, PlaceHolderVar))
644  {
645  PlaceHolderVar *phv = (PlaceHolderVar *) node;
646 
647  Assert(phv->phlevelsup == 0);
648 
649  if (bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at,
650  phinfo->ph_lateral))
651  ph_lateral_vars = lappend(ph_lateral_vars, node);
652  }
653  else
654  Assert(false);
655  }
656 
657  list_free(vars);
658  }
659 
660  return ph_lateral_vars;
661 }
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:781
@ BMS_MULTIPLE
Definition: bitmapset.h:73
List * lappend(List *list, void *datum)
Definition: list.c:339
void list_free(List *list)
Definition: list.c:1546
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
Definition: placeholder.c:83
Definition: nodes.h:129
Relids ph_lateral
Definition: pathnodes.h:3101
Relids ph_eval_at
Definition: pathnodes.h:3098
PlaceHolderVar * ph_var
Definition: pathnodes.h:3095
Index phlevelsup
Definition: pathnodes.h:2807
Definition: primnodes.h:248
int varno
Definition: primnodes.h:255
Index varlevelsup
Definition: primnodes.h:280
Definition: regcomp.c:282
List * pull_vars_of_level(Node *node, int levelsup)
Definition: var.c:338
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:113

References Assert, bms_equal(), bms_is_member(), bms_is_subset(), bms_membership(), BMS_MULTIPLE, bms_overlap(), find_placeholder_info(), IsA, lappend(), lfirst, list_free(), NIL, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_var, PlaceHolderVar::phlevelsup, pull_varnos(), pull_vars_of_level(), root, Var::varlevelsup, and Var::varno.

Referenced by get_memoize_path().

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

1551 {
1552  List *mergeclauses;
1553  List *innersortkeys;
1554  List *trialsortkeys;
1555  Path *cheapest_startup_inner;
1556  Path *cheapest_total_inner;
1557  JoinType save_jointype = jointype;
1558  int num_sortkeys;
1559  int sortkeycnt;
1560 
1561  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1562  jointype = JOIN_INNER;
1563 
1564  /* Look for useful mergeclauses (if any) */
1565  mergeclauses =
1567  outerpath->pathkeys,
1568  extra->mergeclause_list);
1569 
1570  /*
1571  * Done with this outer path if no chance for a mergejoin.
1572  *
1573  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1574  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1575  * but since mergejoin is our only join type that supports FULL JOIN
1576  * without any join clauses, it's necessary to generate a clauseless
1577  * mergejoin path instead.
1578  */
1579  if (mergeclauses == NIL)
1580  {
1581  if (jointype == JOIN_FULL)
1582  /* okay to try for mergejoin */ ;
1583  else
1584  return;
1585  }
1586  if (useallclauses &&
1587  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1588  return;
1589 
1590  /* Compute the required ordering of the inner path */
1591  innersortkeys = make_inner_pathkeys_for_merge(root,
1592  mergeclauses,
1593  outerpath->pathkeys);
1594 
1595  /*
1596  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1597  * a sort will be needed, only cheapest total cost matters. (But
1598  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1599  * already correctly sorted.)
1600  */
1602  joinrel,
1603  outerpath,
1604  inner_cheapest_total,
1605  merge_pathkeys,
1606  mergeclauses,
1607  NIL,
1608  innersortkeys,
1609  jointype,
1610  extra,
1611  is_partial);
1612 
1613  /* Can't do anything else if inner path needs to be unique'd */
1614  if (save_jointype == JOIN_UNIQUE_INNER)
1615  return;
1616 
1617  /*
1618  * Look for presorted inner paths that satisfy the innersortkey list ---
1619  * or any truncation thereof, if we are allowed to build a mergejoin using
1620  * a subset of the merge clauses. Here, we consider both cheap startup
1621  * cost and cheap total cost.
1622  *
1623  * Currently we do not consider parameterized inner paths here. This
1624  * interacts with decisions elsewhere that also discriminate against
1625  * mergejoins with parameterized inputs; see comments in
1626  * src/backend/optimizer/README.
1627  *
1628  * As we shorten the sortkey list, we should consider only paths that are
1629  * strictly cheaper than (in particular, not the same as) any path found
1630  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1631  * merge keys than a given path allows (treating the rest as plain
1632  * joinquals), which is unlikely to be a good idea. Also, eliminating
1633  * paths here on the basis of compare_path_costs is a lot cheaper than
1634  * building the mergejoin path only to throw it away.
1635  *
1636  * If inner_cheapest_total is well enough sorted to have not required a
1637  * sort in the path made above, we shouldn't make a duplicate path with
1638  * it, either. We handle that case with the same logic that handles the
1639  * previous consideration, by initializing the variables that track
1640  * cheapest-so-far properly. Note that we do NOT reject
1641  * inner_cheapest_total if we find it matches some shorter set of
1642  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1643  * sorting inner_cheapest_total, whereas we did sort it above, so the
1644  * plans being considered are different.
1645  */
1646  if (pathkeys_contained_in(innersortkeys,
1647  inner_cheapest_total->pathkeys))
1648  {
1649  /* inner_cheapest_total didn't require a sort */
1650  cheapest_startup_inner = inner_cheapest_total;
1651  cheapest_total_inner = inner_cheapest_total;
1652  }
1653  else
1654  {
1655  /* it did require a sort, at least for the full set of keys */
1656  cheapest_startup_inner = NULL;
1657  cheapest_total_inner = NULL;
1658  }
1659  num_sortkeys = list_length(innersortkeys);
1660  if (num_sortkeys > 1 && !useallclauses)
1661  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1662  else
1663  trialsortkeys = innersortkeys; /* won't really truncate */
1664 
1665  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1666  {
1667  Path *innerpath;
1668  List *newclauses = NIL;
1669 
1670  /*
1671  * Look for an inner path ordered well enough for the first
1672  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1673  * destructively, which is why we made a copy...
1674  */
1675  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1676  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1677  trialsortkeys,
1678  NULL,
1679  TOTAL_COST,
1680  is_partial);
1681  if (innerpath != NULL &&
1682  (cheapest_total_inner == NULL ||
1683  compare_path_costs(innerpath, cheapest_total_inner,
1684  TOTAL_COST) < 0))
1685  {
1686  /* Found a cheap (or even-cheaper) sorted path */
1687  /* Select the right mergeclauses, if we didn't already */
1688  if (sortkeycnt < num_sortkeys)
1689  {
1690  newclauses =
1692  mergeclauses,
1693  trialsortkeys);
1694  Assert(newclauses != NIL);
1695  }
1696  else
1697  newclauses = mergeclauses;
1699  joinrel,
1700  outerpath,
1701  innerpath,
1702  merge_pathkeys,
1703  newclauses,
1704  NIL,
1705  NIL,
1706  jointype,
1707  extra,
1708  is_partial);
1709  cheapest_total_inner = innerpath;
1710  }
1711  /* Same on the basis of cheapest startup cost ... */
1712  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1713  trialsortkeys,
1714  NULL,
1715  STARTUP_COST,
1716  is_partial);
1717  if (innerpath != NULL &&
1718  (cheapest_startup_inner == NULL ||
1719  compare_path_costs(innerpath, cheapest_startup_inner,
1720  STARTUP_COST) < 0))
1721  {
1722  /* Found a cheap (or even-cheaper) sorted path */
1723  if (innerpath != cheapest_total_inner)
1724  {
1725  /*
1726  * Avoid rebuilding clause list if we already made one; saves
1727  * memory in big join trees...
1728  */
1729  if (newclauses == NIL)
1730  {
1731  if (sortkeycnt < num_sortkeys)
1732  {
1733  newclauses =
1735  mergeclauses,
1736  trialsortkeys);
1737  Assert(newclauses != NIL);
1738  }
1739  else
1740  newclauses = mergeclauses;
1741  }
1743  joinrel,
1744  outerpath,
1745  innerpath,
1746  merge_pathkeys,
1747  newclauses,
1748  NIL,
1749  NIL,
1750  jointype,
1751  extra,
1752  is_partial);
1753  }
1754  cheapest_startup_inner = innerpath;
1755  }
1756 
1757  /*
1758  * Don't consider truncated sortkeys if we need all clauses.
1759  */
1760  if (useallclauses)
1761  break;
1762  }
1763 }
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:1026
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:1854
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:620
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1543
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1957
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:69
@ 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:898

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, root, 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 675 of file joinpath.c.

679 {
680  List *param_exprs;
681  List *hash_operators;
682  ListCell *lc;
683  bool binary_mode;
684  List *ph_lateral_vars;
685 
686  /* Obviously not if it's disabled */
687  if (!enable_memoize)
688  return NULL;
689 
690  /*
691  * We can safely not bother with all this unless we expect to perform more
692  * than one inner scan. The first scan is always going to be a cache
693  * miss. This would likely fail later anyway based on costs, so this is
694  * really just to save some wasted effort.
695  */
696  if (outer_path->parent->rows < 2)
697  return NULL;
698 
699  /*
700  * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be
701  * evaluated at innerrel. These lateral Vars/PHVs could be used as
702  * memoize cache keys.
703  */
704  ph_lateral_vars = extract_lateral_vars_from_PHVs(root, innerrel->relids);
705 
706  /*
707  * We can only have a memoize node when there's some kind of cache key,
708  * either parameterized path clauses or lateral Vars. No cache key sounds
709  * more like something a Materialize node might be more useful for.
710  */
711  if ((inner_path->param_info == NULL ||
712  inner_path->param_info->ppi_clauses == NIL) &&
713  innerrel->lateral_vars == NIL &&
714  ph_lateral_vars == NIL)
715  return NULL;
716 
717  /*
718  * Currently we don't do this for SEMI and ANTI joins unless they're
719  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
720  * don't scan the inner node to completion, which will mean memoize cannot
721  * mark the cache entry as complete.
722  *
723  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
724  * = true. Should we? See add_paths_to_joinrel()
725  */
726  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
727  jointype == JOIN_ANTI))
728  return NULL;
729 
730  /*
731  * Memoize normally marks cache entries as complete when it runs out of
732  * tuples to read from its subplan. However, with unique joins, Nested
733  * Loop will skip to the next outer tuple after finding the first matching
734  * inner tuple. This means that we may not read the inner side of the
735  * join to completion which leaves no opportunity to mark the cache entry
736  * as complete. To work around that, when the join is unique we
737  * automatically mark cache entries as complete after fetching the first
738  * tuple. This works when the entire join condition is parameterized.
739  * Otherwise, when the parameterization is only a subset of the join
740  * condition, we can't be sure which part of it causes the join to be
741  * unique. This means there are no guarantees that only 1 tuple will be
742  * read. We cannot mark the cache entry as complete after reading the
743  * first tuple without that guarantee. This means the scope of Memoize
744  * node's usefulness is limited to only outer rows that have no join
745  * partner as this is the only case where Nested Loop would exhaust the
746  * inner scan of a unique join. Since the scope is limited to that, we
747  * just don't bother making a memoize path in this case.
748  *
749  * Lateral vars needn't be considered here as they're not considered when
750  * determining if the join is unique.
751  *
752  * XXX this could be enabled if the remaining join quals were made part of
753  * the inner scan's filter instead of the join filter. Maybe it's worth
754  * considering doing that?
755  */
756  if (extra->inner_unique &&
757  (inner_path->param_info == NULL ||
758  bms_num_members(inner_path->param_info->ppi_serials) <
759  list_length(extra->restrictlist)))
760  return NULL;
761 
762  /*
763  * We can't use a memoize node if there are volatile functions in the
764  * inner rel's target list or restrict list. A cache hit could reduce the
765  * number of calls to these functions.
766  */
767  if (contain_volatile_functions((Node *) innerrel->reltarget))
768  return NULL;
769 
770  foreach(lc, innerrel->baserestrictinfo)
771  {
772  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
773 
774  if (contain_volatile_functions((Node *) rinfo))
775  return NULL;
776  }
777 
778  /*
779  * Also check the parameterized path restrictinfos for volatile functions.
780  * Indexed functions must be immutable so shouldn't have any volatile
781  * functions, however, with a lateral join the inner scan may not be an
782  * index scan.
783  */
784  if (inner_path->param_info != NULL)
785  {
786  foreach(lc, inner_path->param_info->ppi_clauses)
787  {
788  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
789 
790  if (contain_volatile_functions((Node *) rinfo))
791  return NULL;
792  }
793  }
794 
795  /* Check if we have hash ops for each parameter to the path */
797  inner_path->param_info,
798  outerrel->top_parent ?
799  outerrel->top_parent : outerrel,
800  innerrel,
801  ph_lateral_vars,
802  &param_exprs,
803  &hash_operators,
804  &binary_mode))
805  {
806  return (Path *) create_memoize_path(root,
807  innerrel,
808  inner_path,
809  param_exprs,
810  hash_operators,
811  extra->inner_unique,
812  binary_mode,
813  outer_path->rows);
814  }
815 
816  return NULL;
817 }
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:751
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:537
bool enable_memoize
Definition: costsize.c:155
static List * extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids)
Definition: joinpath.c:584
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List *ph_lateral_vars, List **param_exprs, List **operators, bool *binary_mode)
Definition: joinpath.c:439
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:1667
Cardinality rows
Definition: pathnodes.h:1669
List * baserestrictinfo
Definition: pathnodes.h:985
struct PathTarget * reltarget
Definition: pathnodes.h:893
List * lateral_vars
Definition: pathnodes.h:940

References RelOptInfo::baserestrictinfo, bms_num_members(), contain_volatile_functions(), create_memoize_path(), enable_memoize, extract_lateral_vars_from_PHVs(), JoinPathExtraData::inner_unique, JOIN_ANTI, JOIN_SEMI, RelOptInfo::lateral_vars, lfirst, list_length(), NIL, paraminfo_get_equal_hashops(), RelOptInfo::relids, RelOptInfo::reltarget, JoinPathExtraData::restrictlist, root, 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 2197 of file joinpath.c.

2203 {
2204  JoinType save_jointype = jointype;
2205  bool isouterjoin = IS_OUTER_JOIN(jointype);
2206  List *hashclauses;
2207  ListCell *l;
2208 
2209  /*
2210  * We need to build only one hashclauses list for any given pair of outer
2211  * and inner relations; all of the hashable clauses will be used as keys.
2212  *
2213  * Scan the join's restrictinfo list to find hashjoinable clauses that are
2214  * usable with this pair of sub-relations.
2215  */
2216  hashclauses = NIL;
2217  foreach(l, extra->restrictlist)
2218  {
2219  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2220 
2221  /*
2222  * If processing an outer join, only use its own join clauses for
2223  * hashing. For inner joins we need not be so picky.
2224  */
2225  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2226  continue;
2227 
2228  if (!restrictinfo->can_join ||
2229  restrictinfo->hashjoinoperator == InvalidOid)
2230  continue; /* not hashjoinable */
2231 
2232  /*
2233  * Check if clause has the form "outer op inner" or "inner op outer".
2234  */
2235  if (!clause_sides_match_join(restrictinfo, outerrel->relids,
2236  innerrel->relids))
2237  continue; /* no good for these input relations */
2238 
2239  /*
2240  * If clause has the form "inner op outer", check if its operator has
2241  * valid commutator. This is necessary because hashclauses in this
2242  * form will get commuted in createplan.c to put the outer var on the
2243  * left (see get_switched_clauses). This probably shouldn't ever
2244  * fail, since hashable operators ought to have commutators, but be
2245  * paranoid.
2246  *
2247  * The clause being hashjoinable indicates that it's an OpExpr.
2248  */
2249  if (!restrictinfo->outer_is_left &&
2250  !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno)))
2251  continue;
2252 
2253  hashclauses = lappend(hashclauses, restrictinfo);
2254  }
2255 
2256  /* If we found any usable hashclauses, make paths */
2257  if (hashclauses)
2258  {
2259  /*
2260  * We consider both the cheapest-total-cost and cheapest-startup-cost
2261  * outer paths. There's no need to consider any but the
2262  * cheapest-total-cost inner path, however.
2263  */
2264  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2265  Path *cheapest_total_outer = outerrel->cheapest_total_path;
2266  Path *cheapest_total_inner = innerrel->cheapest_total_path;
2267 
2268  /*
2269  * If either cheapest-total path is parameterized by the other rel, we
2270  * can't use a hashjoin. (There's no use looking for alternative
2271  * input paths, since these should already be the least-parameterized
2272  * available paths.)
2273  */
2274  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2275  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2276  return;
2277 
2278  /* Unique-ify if need be; we ignore parameterized possibilities */
2279  if (jointype == JOIN_UNIQUE_OUTER)
2280  {
2281  cheapest_total_outer = (Path *)
2282  create_unique_path(root, outerrel,
2283  cheapest_total_outer, extra->sjinfo);
2284  Assert(cheapest_total_outer);
2285  jointype = JOIN_INNER;
2287  joinrel,
2288  cheapest_total_outer,
2289  cheapest_total_inner,
2290  hashclauses,
2291  jointype,
2292  extra);
2293  /* no possibility of cheap startup here */
2294  }
2295  else if (jointype == JOIN_UNIQUE_INNER)
2296  {
2297  cheapest_total_inner = (Path *)
2298  create_unique_path(root, innerrel,
2299  cheapest_total_inner, extra->sjinfo);
2300  Assert(cheapest_total_inner);
2301  jointype = JOIN_INNER;
2303  joinrel,
2304  cheapest_total_outer,
2305  cheapest_total_inner,
2306  hashclauses,
2307  jointype,
2308  extra);
2309  if (cheapest_startup_outer != NULL &&
2310  cheapest_startup_outer != cheapest_total_outer)
2312  joinrel,
2313  cheapest_startup_outer,
2314  cheapest_total_inner,
2315  hashclauses,
2316  jointype,
2317  extra);
2318  }
2319  else
2320  {
2321  /*
2322  * For other jointypes, we consider the cheapest startup outer
2323  * together with the cheapest total inner, and then consider
2324  * pairings of cheapest-total paths including parameterized ones.
2325  * There is no use in generating parameterized paths on the basis
2326  * of possibly cheap startup cost, so this is sufficient.
2327  */
2328  ListCell *lc1;
2329  ListCell *lc2;
2330 
2331  if (cheapest_startup_outer != NULL)
2333  joinrel,
2334  cheapest_startup_outer,
2335  cheapest_total_inner,
2336  hashclauses,
2337  jointype,
2338  extra);
2339 
2340  foreach(lc1, outerrel->cheapest_parameterized_paths)
2341  {
2342  Path *outerpath = (Path *) lfirst(lc1);
2343 
2344  /*
2345  * We cannot use an outer path that is parameterized by the
2346  * inner rel.
2347  */
2348  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2349  continue;
2350 
2351  foreach(lc2, innerrel->cheapest_parameterized_paths)
2352  {
2353  Path *innerpath = (Path *) lfirst(lc2);
2354 
2355  /*
2356  * We cannot use an inner path that is parameterized by
2357  * the outer rel, either.
2358  */
2359  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2360  continue;
2361 
2362  if (outerpath == cheapest_startup_outer &&
2363  innerpath == cheapest_total_inner)
2364  continue; /* already tried it */
2365 
2367  joinrel,
2368  outerpath,
2369  innerpath,
2370  hashclauses,
2371  jointype,
2372  extra);
2373  }
2374  }
2375  }
2376 
2377  /*
2378  * If the joinrel is parallel-safe, we may be able to consider a
2379  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2380  * because the outer path will be partial, and therefore we won't be
2381  * able to properly guarantee uniqueness. Also, the resulting path
2382  * must not be parameterized.
2383  */
2384  if (joinrel->consider_parallel &&
2385  save_jointype != JOIN_UNIQUE_OUTER &&
2386  outerrel->partial_pathlist != NIL &&
2387  bms_is_empty(joinrel->lateral_relids))
2388  {
2389  Path *cheapest_partial_outer;
2390  Path *cheapest_partial_inner = NULL;
2391  Path *cheapest_safe_inner = NULL;
2392 
2393  cheapest_partial_outer =
2394  (Path *) linitial(outerrel->partial_pathlist);
2395 
2396  /*
2397  * Can we use a partial inner plan too, so that we can build a
2398  * shared hash table in parallel? We can't handle
2399  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2400  */
2401  if (innerrel->partial_pathlist != NIL &&
2402  save_jointype != JOIN_UNIQUE_INNER &&
2404  {
2405  cheapest_partial_inner =
2406  (Path *) linitial(innerrel->partial_pathlist);
2408  cheapest_partial_outer,
2409  cheapest_partial_inner,
2410  hashclauses, jointype, extra,
2411  true /* parallel_hash */ );
2412  }
2413 
2414  /*
2415  * Normally, given that the joinrel is parallel-safe, the cheapest
2416  * total inner path will also be parallel-safe, but if not, we'll
2417  * have to search for the cheapest safe, unparameterized inner
2418  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2419  * inner path. If full, right, right-semi or right-anti join, we
2420  * can't use parallelism (building the hash table in each backend)
2421  * because no one process has all the match bits.
2422  */
2423  if (save_jointype == JOIN_FULL ||
2424  save_jointype == JOIN_RIGHT ||
2425  save_jointype == JOIN_RIGHT_SEMI ||
2426  save_jointype == JOIN_RIGHT_ANTI)
2427  cheapest_safe_inner = NULL;
2428  else if (cheapest_total_inner->parallel_safe)
2429  cheapest_safe_inner = cheapest_total_inner;
2430  else if (save_jointype != JOIN_UNIQUE_INNER)
2431  cheapest_safe_inner =
2433 
2434  if (cheapest_safe_inner != NULL)
2436  cheapest_partial_outer,
2437  cheapest_safe_inner,
2438  hashclauses, jointype, extra,
2439  false /* parallel_hash */ );
2440  }
2441  }
2442 }
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define OidIsValid(objectId)
Definition: c.h:754
bool enable_parallel_hash
Definition: costsize.c:162
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1199
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:1276
Oid get_commutator(Oid opno)
Definition: lsyscache.c:1509
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:338
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
@ JOIN_RIGHT
Definition: nodes.h:296
@ JOIN_RIGHT_SEMI
Definition: nodes.h:309
@ JOIN_RIGHT_ANTI
Definition: nodes.h:310
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:699
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2731
#define linitial(l)
Definition: pg_list.h:178
#define InvalidOid
Definition: postgres_ext.h:36
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: restrictinfo.h:73
bool consider_parallel
Definition: pathnodes.h:887
struct Path * cheapest_startup_path
Definition: pathnodes.h:901
Expr * clause
Definition: pathnodes.h:2574

References Assert, bms_is_empty, castNode, RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, RestrictInfo::clause, clause_sides_match_join(), RelOptInfo::consider_parallel, create_unique_path(), enable_parallel_hash, get_cheapest_parallel_safe_total_inner(), get_commutator(), InvalidOid, IS_OUTER_JOIN, JOIN_FULL, JOIN_INNER, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, lappend(), RelOptInfo::lateral_relids, lfirst, linitial, NIL, OidIsValid, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, RelOptInfo::relids, JoinPathExtraData::restrictlist, RINFO_IS_PUSHED_DOWN, root, 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 1789 of file joinpath.c.

1795 {
1796  JoinType save_jointype = jointype;
1797  bool nestjoinOK;
1798  bool useallclauses;
1799  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1800  Path *matpath = NULL;
1801  ListCell *lc1;
1802 
1803  /*
1804  * For now we do not support RIGHT_SEMI join in mergejoin or nestloop
1805  * join.
1806  */
1807  if (jointype == JOIN_RIGHT_SEMI)
1808  return;
1809 
1810  /*
1811  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1812  * are doing a right, right-anti or full mergejoin, we must use *all* the
1813  * mergeclauses as join clauses, else we will not have a valid plan.
1814  * (Although these two flags are currently inverses, keep them separate
1815  * for clarity and possible future changes.)
1816  */
1817  switch (jointype)
1818  {
1819  case JOIN_INNER:
1820  case JOIN_LEFT:
1821  case JOIN_SEMI:
1822  case JOIN_ANTI:
1823  nestjoinOK = true;
1824  useallclauses = false;
1825  break;
1826  case JOIN_RIGHT:
1827  case JOIN_RIGHT_ANTI:
1828  case JOIN_FULL:
1829  nestjoinOK = false;
1830  useallclauses = true;
1831  break;
1832  case JOIN_UNIQUE_OUTER:
1833  case JOIN_UNIQUE_INNER:
1834  jointype = JOIN_INNER;
1835  nestjoinOK = true;
1836  useallclauses = false;
1837  break;
1838  default:
1839  elog(ERROR, "unrecognized join type: %d",
1840  (int) jointype);
1841  nestjoinOK = false; /* keep compiler quiet */
1842  useallclauses = false;
1843  break;
1844  }
1845 
1846  /*
1847  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1848  * we will consider it below as a member of cheapest_parameterized_paths,
1849  * but the other possibilities considered in this routine aren't usable.
1850  */
1851  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1852  inner_cheapest_total = NULL;
1853 
1854  /*
1855  * If we need to unique-ify the inner path, we will consider only the
1856  * cheapest-total inner.
1857  */
1858  if (save_jointype == JOIN_UNIQUE_INNER)
1859  {
1860  /* No way to do this with an inner path parameterized by outer rel */
1861  if (inner_cheapest_total == NULL)
1862  return;
1863  inner_cheapest_total = (Path *)
1864  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1865  Assert(inner_cheapest_total);
1866  }
1867  else if (nestjoinOK)
1868  {
1869  /*
1870  * Consider materializing the cheapest inner path, unless
1871  * enable_material is off or the path in question materializes its
1872  * output anyway.
1873  */
1874  if (enable_material && inner_cheapest_total != NULL &&
1875  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1876  matpath = (Path *)
1877  create_material_path(innerrel, inner_cheapest_total);
1878  }
1879 
1880  foreach(lc1, outerrel->pathlist)
1881  {
1882  Path *outerpath = (Path *) lfirst(lc1);
1883  List *merge_pathkeys;
1884 
1885  /*
1886  * We cannot use an outer path that is parameterized by the inner rel.
1887  */
1888  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1889  continue;
1890 
1891  /*
1892  * If we need to unique-ify the outer path, it's pointless to consider
1893  * any but the cheapest outer. (XXX we don't consider parameterized
1894  * outers, nor inners, for unique-ified cases. Should we?)
1895  */
1896  if (save_jointype == JOIN_UNIQUE_OUTER)
1897  {
1898  if (outerpath != outerrel->cheapest_total_path)
1899  continue;
1900  outerpath = (Path *) create_unique_path(root, outerrel,
1901  outerpath, extra->sjinfo);
1902  Assert(outerpath);
1903  }
1904 
1905  /*
1906  * The result will have this sort order (even if it is implemented as
1907  * a nestloop, and even if some of the mergeclauses are implemented by
1908  * qpquals rather than as true mergeclauses):
1909  */
1910  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1911  outerpath->pathkeys);
1912 
1913  if (save_jointype == JOIN_UNIQUE_INNER)
1914  {
1915  /*
1916  * Consider nestloop join, but only with the unique-ified cheapest
1917  * inner path
1918  */
1920  joinrel,
1921  outerpath,
1922  inner_cheapest_total,
1923  merge_pathkeys,
1924  jointype,
1925  extra);
1926  }
1927  else if (nestjoinOK)
1928  {
1929  /*
1930  * Consider nestloop joins using this outer path and various
1931  * available paths for the inner relation. We consider the
1932  * cheapest-total paths for each available parameterization of the
1933  * inner relation, including the unparameterized case.
1934  */
1935  ListCell *lc2;
1936 
1937  foreach(lc2, innerrel->cheapest_parameterized_paths)
1938  {
1939  Path *innerpath = (Path *) lfirst(lc2);
1940  Path *mpath;
1941 
1943  joinrel,
1944  outerpath,
1945  innerpath,
1946  merge_pathkeys,
1947  jointype,
1948  extra);
1949 
1950  /*
1951  * Try generating a memoize path and see if that makes the
1952  * nested loop any cheaper.
1953  */
1954  mpath = get_memoize_path(root, innerrel, outerrel,
1955  innerpath, outerpath, jointype,
1956  extra);
1957  if (mpath != NULL)
1959  joinrel,
1960  outerpath,
1961  mpath,
1962  merge_pathkeys,
1963  jointype,
1964  extra);
1965  }
1966 
1967  /* Also consider materialized form of the cheapest inner path */
1968  if (matpath != NULL)
1970  joinrel,
1971  outerpath,
1972  matpath,
1973  merge_pathkeys,
1974  jointype,
1975  extra);
1976  }
1977 
1978  /* Can't do anything else if outer path needs to be unique'd */
1979  if (save_jointype == JOIN_UNIQUE_OUTER)
1980  continue;
1981 
1982  /* Can't do anything else if inner rel is parameterized by outer */
1983  if (inner_cheapest_total == NULL)
1984  continue;
1985 
1986  /* Generate merge join paths */
1987  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1988  save_jointype, extra, useallclauses,
1989  inner_cheapest_total, merge_pathkeys,
1990  false);
1991  }
1992 
1993  /*
1994  * Consider partial nestloop and mergejoin plan if outerrel has any
1995  * partial path and the joinrel is parallel-safe. However, we can't
1996  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1997  * therefore we won't be able to properly guarantee uniqueness. Nor can
1998  * we handle joins needing lateral rels, since partial paths must not be
1999  * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
2000  * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
2001  */
2002  if (joinrel->consider_parallel &&
2003  save_jointype != JOIN_UNIQUE_OUTER &&
2004  save_jointype != JOIN_FULL &&
2005  save_jointype != JOIN_RIGHT &&
2006  save_jointype != JOIN_RIGHT_ANTI &&
2007  outerrel->partial_pathlist != NIL &&
2008  bms_is_empty(joinrel->lateral_relids))
2009  {
2010  if (nestjoinOK)
2011  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
2012  save_jointype, extra);
2013 
2014  /*
2015  * If inner_cheapest_total is NULL or non parallel-safe then find the
2016  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
2017  * can't use any alternative inner path.
2018  */
2019  if (inner_cheapest_total == NULL ||
2020  !inner_cheapest_total->parallel_safe)
2021  {
2022  if (save_jointype == JOIN_UNIQUE_INNER)
2023  return;
2024 
2025  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
2026  }
2027 
2028  if (inner_cheapest_total)
2029  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
2030  save_jointype, extra,
2031  inner_cheapest_total);
2032  }
2033 }
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:825
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2088
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:2048
@ JOIN_LEFT
Definition: nodes.h:294

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_RIGHT_SEMI, 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, root, 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 ph_lateral_vars,
List **  param_exprs,
List **  operators,
bool *  binary_mode 
)
static

Definition at line 439 of file joinpath.c.

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

2474 {
2475  List *result_list = NIL;
2476  bool isouterjoin = IS_OUTER_JOIN(jointype);
2477  bool have_nonmergeable_joinclause = false;
2478  ListCell *l;
2479 
2480  /*
2481  * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of
2482  * swapping inputs tends to be small here.
2483  */
2484  if (jointype == JOIN_RIGHT_SEMI)
2485  {
2486  *mergejoin_allowed = false;
2487  return NIL;
2488  }
2489 
2490  foreach(l, restrictlist)
2491  {
2492  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2493 
2494  /*
2495  * If processing an outer join, only use its own join clauses in the
2496  * merge. For inner joins we can use pushed-down clauses too. (Note:
2497  * we don't set have_nonmergeable_joinclause here because pushed-down
2498  * clauses will become otherquals not joinquals.)
2499  */
2500  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2501  continue;
2502 
2503  /* Check that clause is a mergeable operator clause */
2504  if (!restrictinfo->can_join ||
2505  restrictinfo->mergeopfamilies == NIL)
2506  {
2507  /*
2508  * The executor can handle extra joinquals that are constants, but
2509  * not anything else, when doing right/right-anti/full merge join.
2510  * (The reason to support constants is so we can do FULL JOIN ON
2511  * FALSE.)
2512  */
2513  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2514  have_nonmergeable_joinclause = true;
2515  continue; /* not mergejoinable */
2516  }
2517 
2518  /*
2519  * Check if clause has the form "outer op inner" or "inner op outer".
2520  */
2521  if (!clause_sides_match_join(restrictinfo, outerrel->relids,
2522  innerrel->relids))
2523  {
2524  have_nonmergeable_joinclause = true;
2525  continue; /* no good for these input relations */
2526  }
2527 
2528  /*
2529  * If clause has the form "inner op outer", check if its operator has
2530  * valid commutator. This is necessary because mergejoin clauses in
2531  * this form will get commuted in createplan.c to put the outer var on
2532  * the left (see get_switched_clauses). This probably shouldn't ever
2533  * fail, since mergejoinable operators ought to have commutators, but
2534  * be paranoid.
2535  *
2536  * The clause being mergejoinable indicates that it's an OpExpr.
2537  */
2538  if (!restrictinfo->outer_is_left &&
2539  !OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno)))
2540  {
2541  have_nonmergeable_joinclause = true;
2542  continue;
2543  }
2544 
2545  /*
2546  * Insist that each side have a non-redundant eclass. This
2547  * restriction is needed because various bits of the planner expect
2548  * that each clause in a merge be associable with some pathkey in a
2549  * canonical pathkey list, but redundant eclasses can't appear in
2550  * canonical sort orderings. (XXX it might be worth relaxing this,
2551  * but not enough time to address it for 8.3.)
2552  */
2553  update_mergeclause_eclasses(root, restrictinfo);
2554 
2555  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2556  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2557  {
2558  have_nonmergeable_joinclause = true;
2559  continue; /* can't handle redundant eclasses */
2560  }
2561 
2562  result_list = lappend(result_list, restrictinfo);
2563  }
2564 
2565  /*
2566  * Report whether mergejoin is allowed (see comment at top of function).
2567  */
2568  switch (jointype)
2569  {
2570  case JOIN_RIGHT:
2571  case JOIN_RIGHT_ANTI:
2572  case JOIN_FULL:
2573  *mergejoin_allowed = !have_nonmergeable_joinclause;
2574  break;
2575  default:
2576  *mergejoin_allowed = true;
2577  break;
2578  }
2579 
2580  return result_list;
2581 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1509
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1412

References castNode, RestrictInfo::clause, clause_sides_match_join(), EC_MUST_BE_REDUNDANT, get_commutator(), IS_OUTER_JOIN, IsA, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, lappend(), lfirst, NIL, OidIsValid, RelOptInfo::relids, RINFO_IS_PUSHED_DOWN, root, 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 1334 of file joinpath.c.

1340 {
1341  JoinType save_jointype = jointype;
1342  Path *outer_path;
1343  Path *inner_path;
1344  Path *cheapest_partial_outer = NULL;
1345  Path *cheapest_safe_inner = NULL;
1346  List *all_pathkeys;
1347  ListCell *l;
1348 
1349  /* Nothing to do if there are no available mergejoin clauses */
1350  if (extra->mergeclause_list == NIL)
1351  return;
1352 
1353  /*
1354  * We only consider the cheapest-total-cost input paths, since we are
1355  * assuming here that a sort is required. We will consider
1356  * cheapest-startup-cost input paths later, and only if they don't need a
1357  * sort.
1358  *
1359  * This function intentionally does not consider parameterized input
1360  * paths, except when the cheapest-total is parameterized. If we did so,
1361  * we'd have a combinatorial explosion of mergejoin paths of dubious
1362  * value. This interacts with decisions elsewhere that also discriminate
1363  * against mergejoins with parameterized inputs; see comments in
1364  * src/backend/optimizer/README.
1365  */
1366  outer_path = outerrel->cheapest_total_path;
1367  inner_path = innerrel->cheapest_total_path;
1368 
1369  /*
1370  * If either cheapest-total path is parameterized by the other rel, we
1371  * can't use a mergejoin. (There's no use looking for alternative input
1372  * paths, since these should already be the least-parameterized available
1373  * paths.)
1374  */
1375  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1376  PATH_PARAM_BY_REL(inner_path, outerrel))
1377  return;
1378 
1379  /*
1380  * If unique-ification is requested, do it and then handle as a plain
1381  * inner join.
1382  */
1383  if (jointype == JOIN_UNIQUE_OUTER)
1384  {
1385  outer_path = (Path *) create_unique_path(root, outerrel,
1386  outer_path, extra->sjinfo);
1387  Assert(outer_path);
1388  jointype = JOIN_INNER;
1389  }
1390  else if (jointype == JOIN_UNIQUE_INNER)
1391  {
1392  inner_path = (Path *) create_unique_path(root, innerrel,
1393  inner_path, extra->sjinfo);
1394  Assert(inner_path);
1395  jointype = JOIN_INNER;
1396  }
1397 
1398  /*
1399  * If the joinrel is parallel-safe, we may be able to consider a partial
1400  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1401  * outer path will be partial, and therefore we won't be able to properly
1402  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1403  * and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1404  * Also, the resulting path must not be parameterized.
1405  */
1406  if (joinrel->consider_parallel &&
1407  save_jointype != JOIN_UNIQUE_OUTER &&
1408  save_jointype != JOIN_FULL &&
1409  save_jointype != JOIN_RIGHT &&
1410  save_jointype != JOIN_RIGHT_ANTI &&
1411  outerrel->partial_pathlist != NIL &&
1412  bms_is_empty(joinrel->lateral_relids))
1413  {
1414  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1415 
1416  if (inner_path->parallel_safe)
1417  cheapest_safe_inner = inner_path;
1418  else if (save_jointype != JOIN_UNIQUE_INNER)
1419  cheapest_safe_inner =
1421  }
1422 
1423  /*
1424  * Each possible ordering of the available mergejoin clauses will generate
1425  * a differently-sorted result path at essentially the same cost. We have
1426  * no basis for choosing one over another at this level of joining, but
1427  * some sort orders may be more useful than others for higher-level
1428  * mergejoins, so it's worth considering multiple orderings.
1429  *
1430  * Actually, it's not quite true that every mergeclause ordering will
1431  * generate a different path order, because some of the clauses may be
1432  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1433  * what we do is convert the mergeclause list to a list of canonical
1434  * pathkeys, and then consider different orderings of the pathkeys.
1435  *
1436  * Generating a path for *every* permutation of the pathkeys doesn't seem
1437  * like a winning strategy; the cost in planning time is too high. For
1438  * now, we generate one path for each pathkey, listing that pathkey first
1439  * and the rest in random order. This should allow at least a one-clause
1440  * mergejoin without re-sorting against any other possible mergejoin
1441  * partner path. But if we've not guessed the right ordering of secondary
1442  * keys, we may end up evaluating clauses as qpquals when they could have
1443  * been done as mergeclauses. (In practice, it's rare that there's more
1444  * than two or three mergeclauses, so expending a huge amount of thought
1445  * on that is probably not worth it.)
1446  *
1447  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1448  * some heuristics behind it (see that function), so be sure to try it
1449  * exactly as-is as well as making variants.
1450  */
1451  all_pathkeys = select_outer_pathkeys_for_merge(root,
1452  extra->mergeclause_list,
1453  joinrel);
1454 
1455  foreach(l, all_pathkeys)
1456  {
1457  PathKey *front_pathkey = (PathKey *) lfirst(l);
1458  List *cur_mergeclauses;
1459  List *outerkeys;
1460  List *innerkeys;
1461  List *merge_pathkeys;
1462 
1463  /* Make a pathkey list with this guy first */
1464  if (l != list_head(all_pathkeys))
1465  outerkeys = lcons(front_pathkey,
1466  list_delete_nth_cell(list_copy(all_pathkeys),
1467  foreach_current_index(l)));
1468  else
1469  outerkeys = all_pathkeys; /* no work at first one... */
1470 
1471  /* Sort the mergeclauses into the corresponding ordering */
1472  cur_mergeclauses =
1474  outerkeys,
1475  extra->mergeclause_list);
1476 
1477  /* Should have used them all... */
1478  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1479 
1480  /* Build sort pathkeys for the inner side */
1481  innerkeys = make_inner_pathkeys_for_merge(root,
1482  cur_mergeclauses,
1483  outerkeys);
1484 
1485  /* Build pathkeys representing output sort order */
1486  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1487  outerkeys);
1488 
1489  /*
1490  * And now we can make the path.
1491  *
1492  * Note: it's possible that the cheapest paths will already be sorted
1493  * properly. try_mergejoin_path will detect that case and suppress an
1494  * explicit sort step, so we needn't do so here.
1495  */
1497  joinrel,
1498  outer_path,
1499  inner_path,
1500  merge_pathkeys,
1501  cur_mergeclauses,
1502  outerkeys,
1503  innerkeys,
1504  jointype,
1505  extra,
1506  false);
1507 
1508  /*
1509  * If we have partial outer and parallel safe inner path then try
1510  * partial mergejoin path.
1511  */
1512  if (cheapest_partial_outer && cheapest_safe_inner)
1514  joinrel,
1515  cheapest_partial_outer,
1516  cheapest_safe_inner,
1517  merge_pathkeys,
1518  cur_mergeclauses,
1519  outerkeys,
1520  innerkeys,
1521  jointype,
1522  extra);
1523  }
1524 }
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:1132
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:1658
#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, root, 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 1199 of file joinpath.c.

1206 {
1207  Relids required_outer;
1208  JoinCostWorkspace workspace;
1209 
1210  /*
1211  * If we are forming an outer join at this join, it's nonsensical to use
1212  * an input path that uses the outer join as part of its parameterization.
1213  * (This can happen despite our join order restrictions, since those apply
1214  * to what is in an input relation not what its parameters are.)
1215  */
1216  if (extra->sjinfo->ojrelid != 0 &&
1217  (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1218  bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1219  return;
1220 
1221  /*
1222  * Check to see if proposed path is still parameterized, and reject if the
1223  * parameterization wouldn't be sensible.
1224  */
1225  required_outer = calc_non_nestloop_required_outer(outer_path,
1226  inner_path);
1227  if (required_outer &&
1228  !bms_overlap(required_outer, extra->param_source_rels))
1229  {
1230  /* Waste no memory when we reject a path here */
1231  bms_free(required_outer);
1232  return;
1233  }
1234 
1235  /*
1236  * See comments in try_nestloop_path(). Also note that hashjoin paths
1237  * never have any output pathkeys, per comments in create_hashjoin_path.
1238  */
1239  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1240  outer_path, inner_path, extra, false);
1241 
1242  if (add_path_precheck(joinrel, workspace.disabled_nodes,
1243  workspace.startup_cost, workspace.total_cost,
1244  NIL, required_outer))
1245  {
1246  add_path(joinrel, (Path *)
1248  joinrel,
1249  jointype,
1250  &workspace,
1251  extra,
1252  outer_path,
1253  inner_path,
1254  false, /* parallel_hash */
1255  extra->restrictlist,
1256  required_outer,
1257  hashclauses));
1258  }
1259  else
1260  {
1261  /* Waste no memory when we reject a path here */
1262  bms_free(required_outer);
1263  }
1264 }
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
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:4160
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2483
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:2697
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:461
bool add_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:688

References add_path(), add_path_precheck(), bms_free(), bms_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_hashjoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_hashjoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, root, 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 1026 of file joinpath.c.

1037 {
1038  Relids required_outer;
1039  JoinCostWorkspace workspace;
1040 
1041  if (is_partial)
1042  {
1044  joinrel,
1045  outer_path,
1046  inner_path,
1047  pathkeys,
1048  mergeclauses,
1049  outersortkeys,
1050  innersortkeys,
1051  jointype,
1052  extra);
1053  return;
1054  }
1055 
1056  /*
1057  * If we are forming an outer join at this join, it's nonsensical to use
1058  * an input path that uses the outer join as part of its parameterization.
1059  * (This can happen despite our join order restrictions, since those apply
1060  * to what is in an input relation not what its parameters are.)
1061  */
1062  if (extra->sjinfo->ojrelid != 0 &&
1063  (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1064  bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1065  return;
1066 
1067  /*
1068  * Check to see if proposed path is still parameterized, and reject if the
1069  * parameterization wouldn't be sensible.
1070  */
1071  required_outer = calc_non_nestloop_required_outer(outer_path,
1072  inner_path);
1073  if (required_outer &&
1074  !bms_overlap(required_outer, extra->param_source_rels))
1075  {
1076  /* Waste no memory when we reject a path here */
1077  bms_free(required_outer);
1078  return;
1079  }
1080 
1081  /*
1082  * If the given paths are already well enough ordered, we can skip doing
1083  * an explicit sort.
1084  */
1085  if (outersortkeys &&
1086  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1087  outersortkeys = NIL;
1088  if (innersortkeys &&
1089  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1090  innersortkeys = NIL;
1091 
1092  /*
1093  * See comments in try_nestloop_path().
1094  */
1095  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1096  outer_path, inner_path,
1097  outersortkeys, innersortkeys,
1098  extra);
1099 
1100  if (add_path_precheck(joinrel, workspace.disabled_nodes,
1101  workspace.startup_cost, workspace.total_cost,
1102  pathkeys, required_outer))
1103  {
1104  add_path(joinrel, (Path *)
1106  joinrel,
1107  jointype,
1108  &workspace,
1109  extra,
1110  outer_path,
1111  inner_path,
1112  extra->restrictlist,
1113  pathkeys,
1114  required_outer,
1115  mergeclauses,
1116  outersortkeys,
1117  innersortkeys));
1118  }
1119  else
1120  {
1121  /* Waste no memory when we reject a path here */
1122  bms_free(required_outer);
1123  }
1124 }
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:3552
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:2631

References add_path(), add_path_precheck(), bms_free(), bms_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_mergejoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_mergejoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, Path::pathkeys, pathkeys_contained_in(), JoinPathExtraData::restrictlist, root, 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 825 of file joinpath.c.

832 {
833  Relids required_outer;
834  JoinCostWorkspace workspace;
835  RelOptInfo *innerrel = inner_path->parent;
836  RelOptInfo *outerrel = outer_path->parent;
837  Relids innerrelids;
838  Relids outerrelids;
839  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
840  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
841 
842  /*
843  * If we are forming an outer join at this join, it's nonsensical to use
844  * an input path that uses the outer join as part of its parameterization.
845  * (This can happen despite our join order restrictions, since those apply
846  * to what is in an input relation not what its parameters are.)
847  */
848  if (extra->sjinfo->ojrelid != 0 &&
849  (bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) ||
850  bms_is_member(extra->sjinfo->ojrelid, outer_paramrels)))
851  return;
852 
853  /*
854  * Any parameterization of the input paths refers to topmost parents of
855  * the relevant relations, because reparameterize_path_by_child() hasn't
856  * been called yet. So we must consider topmost parents of the relations
857  * being joined, too, while determining parameterization of the result and
858  * checking for disallowed parameterization cases.
859  */
860  if (innerrel->top_parent_relids)
861  innerrelids = innerrel->top_parent_relids;
862  else
863  innerrelids = innerrel->relids;
864 
865  if (outerrel->top_parent_relids)
866  outerrelids = outerrel->top_parent_relids;
867  else
868  outerrelids = outerrel->relids;
869 
870  /*
871  * Check to see if proposed path is still parameterized, and reject if the
872  * parameterization wouldn't be sensible --- unless allow_star_schema_join
873  * says to allow it anyway. Also, we must reject if have_dangerous_phv
874  * doesn't like the look of it, which could only happen if the nestloop is
875  * still parameterized.
876  */
877  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
878  innerrelids, inner_paramrels);
879  if (required_outer &&
880  ((!bms_overlap(required_outer, extra->param_source_rels) &&
881  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
882  have_dangerous_phv(root, outerrelids, inner_paramrels)))
883  {
884  /* Waste no memory when we reject a path here */
885  bms_free(required_outer);
886  return;
887  }
888 
889  /* If we got past that, we shouldn't have any unsafe outer-join refs */
890  Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
891 
892  /*
893  * If the inner path is parameterized, it is parameterized by the topmost
894  * parent of the outer rel, not the outer rel itself. We will need to
895  * translate the parameterization, if this path is chosen, during
896  * create_plan(). Here we just check whether we will be able to perform
897  * the translation, and if not avoid creating a nestloop path.
898  */
899  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
900  !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
901  {
902  bms_free(required_outer);
903  return;
904  }
905 
906  /*
907  * Do a precheck to quickly eliminate obviously-inferior paths. We
908  * calculate a cheap lower bound on the path's cost and then use
909  * add_path_precheck() to see if the path is clearly going to be dominated
910  * by some existing path for the joinrel. If not, do the full pushup with
911  * creating a fully valid path structure and submitting it to add_path().
912  * The latter two steps are expensive enough to make this two-phase
913  * methodology worthwhile.
914  */
915  initial_cost_nestloop(root, &workspace, jointype,
916  outer_path, inner_path, extra);
917 
918  if (add_path_precheck(joinrel, workspace.disabled_nodes,
919  workspace.startup_cost, workspace.total_cost,
920  pathkeys, required_outer))
921  {
922  add_path(joinrel, (Path *)
924  joinrel,
925  jointype,
926  &workspace,
927  extra,
928  outer_path,
929  inner_path,
930  extra->restrictlist,
931  pathkeys,
932  required_outer));
933  }
934  else
935  {
936  /* Waste no memory when we reject a path here */
937  bms_free(required_outer);
938  }
939 }
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:3268
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:40
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:363
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1307
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:2535
bool path_is_reparameterizable_by_child(Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:4508
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2456

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(), JoinCostWorkspace::disabled_nodes, have_dangerous_phv(), initial_cost_nestloop(), SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, path_is_reparameterizable_by_child(), PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, JoinPathExtraData::restrictlist, root, 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 1276 of file joinpath.c.

1284 {
1285  JoinCostWorkspace workspace;
1286 
1287  /*
1288  * If the inner path is parameterized, we can't use a partial hashjoin.
1289  * Parameterized partial paths are not supported. The caller should
1290  * already have verified that no lateral rels are required here.
1291  */
1292  Assert(bms_is_empty(joinrel->lateral_relids));
1293  Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1294  if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1295  return;
1296 
1297  /*
1298  * Before creating a path, get a quick lower bound on what it is likely to
1299  * cost. Bail out right away if it looks terrible.
1300  */
1301  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1302  outer_path, inner_path, extra, parallel_hash);
1303  if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1304  workspace.total_cost, NIL))
1305  return;
1306 
1307  /* Might be good enough to be worth trying, so let's try it. */
1308  add_partial_path(joinrel, (Path *)
1310  joinrel,
1311  jointype,
1312  &workspace,
1313  extra,
1314  outer_path,
1315  inner_path,
1316  parallel_hash,
1317  extra->restrictlist,
1318  NULL,
1319  hashclauses));
1320 }
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:795
bool add_partial_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost total_cost, List *pathkeys)
Definition: pathnode.c:921

References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty, create_hashjoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_hashjoin(), RelOptInfo::lateral_relids, NIL, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, root, 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 1132 of file joinpath.c.

1142 {
1143  JoinCostWorkspace workspace;
1144 
1145  /*
1146  * See comments in try_partial_hashjoin_path().
1147  */
1148  Assert(bms_is_empty(joinrel->lateral_relids));
1149  Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
1150  if (!bms_is_empty(PATH_REQ_OUTER(inner_path)))
1151  return;
1152 
1153  /*
1154  * If the given paths are already well enough ordered, we can skip doing
1155  * an explicit sort.
1156  */
1157  if (outersortkeys &&
1158  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1159  outersortkeys = NIL;
1160  if (innersortkeys &&
1161  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1162  innersortkeys = NIL;
1163 
1164  /*
1165  * See comments in try_partial_nestloop_path().
1166  */
1167  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1168  outer_path, inner_path,
1169  outersortkeys, innersortkeys,
1170  extra);
1171 
1172  if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1173  workspace.total_cost, pathkeys))
1174  return;
1175 
1176  /* Might be good enough to be worth trying, so let's try it. */
1177  add_partial_path(joinrel, (Path *)
1179  joinrel,
1180  jointype,
1181  &workspace,
1182  extra,
1183  outer_path,
1184  inner_path,
1185  extra->restrictlist,
1186  pathkeys,
1187  NULL,
1188  mergeclauses,
1189  outersortkeys,
1190  innersortkeys));
1191 }

References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty, create_mergejoin_path(), JoinCostWorkspace::disabled_nodes, initial_cost_mergejoin(), RelOptInfo::lateral_relids, NIL, PATH_REQ_OUTER, Path::pathkeys, pathkeys_contained_in(), JoinPathExtraData::restrictlist, root, 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 947 of file joinpath.c.

954 {
955  JoinCostWorkspace workspace;
956 
957  /*
958  * If the inner path is parameterized, the parameterization must be fully
959  * satisfied by the proposed outer path. Parameterized partial paths are
960  * not supported. The caller should already have verified that no lateral
961  * rels are required here.
962  */
964  Assert(bms_is_empty(PATH_REQ_OUTER(outer_path)));
965  if (inner_path->param_info != NULL)
966  {
967  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
968  RelOptInfo *outerrel = outer_path->parent;
969  Relids outerrelids;
970 
971  /*
972  * The inner and outer paths are parameterized, if at all, by the top
973  * level parents, not the child relations, so we must use those relids
974  * for our parameterization tests.
975  */
976  if (outerrel->top_parent_relids)
977  outerrelids = outerrel->top_parent_relids;
978  else
979  outerrelids = outerrel->relids;
980 
981  if (!bms_is_subset(inner_paramrels, outerrelids))
982  return;
983  }
984 
985  /*
986  * If the inner path is parameterized, it is parameterized by the topmost
987  * parent of the outer rel, not the outer rel itself. We will need to
988  * translate the parameterization, if this path is chosen, during
989  * create_plan(). Here we just check whether we will be able to perform
990  * the translation, and if not avoid creating a nestloop path.
991  */
992  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
993  !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
994  return;
995 
996  /*
997  * Before creating a path, get a quick lower bound on what it is likely to
998  * cost. Bail out right away if it looks terrible.
999  */
1000  initial_cost_nestloop(root, &workspace, jointype,
1001  outer_path, inner_path, extra);
1002  if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes,
1003  workspace.total_cost, pathkeys))
1004  return;
1005 
1006  /* Might be good enough to be worth trying, so let's try it. */
1007  add_partial_path(joinrel, (Path *)
1009  joinrel,
1010  jointype,
1011  &workspace,
1012  extra,
1013  outer_path,
1014  inner_path,
1015  extra->restrictlist,
1016  pathkeys,
1017  NULL));
1018 }

References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty, bms_is_subset(), create_nestloop_path(), JoinCostWorkspace::disabled_nodes, initial_cost_nestloop(), RelOptInfo::lateral_relids, path_is_reparameterizable_by_child(), PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, JoinPathExtraData::restrictlist, root, 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 33 of file joinpath.c.

Referenced by add_paths_to_joinrel().