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

Go to the source code of this file.

Macros

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

Functions

static void try_partial_mergejoin_path (PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra)
 
static void sort_inner_and_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static bool clause_sides_match_join (RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
 
static void match_unsorted_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void consider_parallel_nestloop (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static void consider_parallel_mergejoin (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
 
static void hash_inner_and_outer (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
static Listselect_mergejoin_clauses (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
 
static void generate_mergejoin_paths (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
static bool allow_star_schema_join (PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
 
static bool paraminfo_get_equal_hashops (PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List **param_exprs, List **operators)
 
static Pathget_resultcache_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))
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1193
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494

Definition at line 36 of file joinpath.c.

Referenced by try_nestloop_path(), and try_partial_nestloop_path().

◆ PATH_PARAM_BY_REL

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

Definition at line 42 of file joinpath.c.

Referenced by hash_inner_and_outer(), match_unsorted_outer(), and sort_inner_and_outer().

◆ PATH_PARAM_BY_REL_SELF

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

Definition at line 39 of file joinpath.c.

Function Documentation

◆ add_paths_to_joinrel()

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

Definition at line 123 of file joinpath.c.

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.

Referenced by populate_joinrel_with_paths().

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

◆ allow_star_schema_join()

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

Definition at line 356 of file joinpath.c.

References bms_nonempty_difference(), and bms_overlap().

Referenced by try_nestloop_path().

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

◆ clause_sides_match_join()

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

Definition at line 1034 of file joinpath.c.

References bms_is_subset(), RestrictInfo::left_relids, RestrictInfo::outer_is_left, RelOptInfo::relids, and RestrictInfo::right_relids.

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

1036 {
1037  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
1038  bms_is_subset(rinfo->right_relids, innerrel->relids))
1039  {
1040  /* lefthand side is outer */
1041  rinfo->outer_is_left = true;
1042  return true;
1043  }
1044  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
1045  bms_is_subset(rinfo->right_relids, outerrel->relids))
1046  {
1047  /* righthand side is outer */
1048  rinfo->outer_is_left = false;
1049  return true;
1050  }
1051  return false; /* no good for these input relations */
1052 }
Relids left_relids
Definition: pathnodes.h:2075
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
bool outer_is_left
Definition: pathnodes.h:2103
Relids relids
Definition: pathnodes.h:676
Relids right_relids
Definition: pathnodes.h:2076

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

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

Referenced by match_unsorted_outer().

1773 {
1774  ListCell *lc1;
1775 
1776  /* generate merge join path for each partial outer path */
1777  foreach(lc1, outerrel->partial_pathlist)
1778  {
1779  Path *outerpath = (Path *) lfirst(lc1);
1780  List *merge_pathkeys;
1781 
1782  /*
1783  * Figure out what useful ordering any paths we create will have.
1784  */
1785  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1786  outerpath->pathkeys);
1787 
1788  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1789  extra, false, inner_cheapest_total,
1790  merge_pathkeys, true);
1791  }
1792 }
List * partial_pathlist
Definition: pathnodes.h:692
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1082
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:1268
List * pathkeys
Definition: pathnodes.h:1188
#define lfirst(lc)
Definition: pg_list.h:169
Definition: pg_list.h:50

◆ consider_parallel_nestloop()

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

Definition at line 1806 of file joinpath.c.

References Assert, build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, create_unique_path(), get_resultcache_path(), JOIN_INNER, JOIN_UNIQUE_INNER, lfirst, Path::parallel_safe, RelOptInfo::partial_pathlist, Path::pathkeys, JoinPathExtraData::sjinfo, and try_partial_nestloop_path().

Referenced by match_unsorted_outer().

1812 {
1813  JoinType save_jointype = jointype;
1814  ListCell *lc1;
1815 
1816  if (jointype == JOIN_UNIQUE_INNER)
1817  jointype = JOIN_INNER;
1818 
1819  foreach(lc1, outerrel->partial_pathlist)
1820  {
1821  Path *outerpath = (Path *) lfirst(lc1);
1822  List *pathkeys;
1823  ListCell *lc2;
1824 
1825  /* Figure out what useful ordering any paths we create will have. */
1826  pathkeys = build_join_pathkeys(root, joinrel, jointype,
1827  outerpath->pathkeys);
1828 
1829  /*
1830  * Try the cheapest parameterized paths; only those which will produce
1831  * an unparameterized path when joined to this outerrel will survive
1832  * try_partial_nestloop_path. The cheapest unparameterized path is
1833  * also in this list.
1834  */
1835  foreach(lc2, innerrel->cheapest_parameterized_paths)
1836  {
1837  Path *innerpath = (Path *) lfirst(lc2);
1838  Path *rcpath;
1839 
1840  /* Can't join to an inner path that is not parallel-safe */
1841  if (!innerpath->parallel_safe)
1842  continue;
1843 
1844  /*
1845  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
1846  * cheapest_total_path, and we have to unique-ify it. (We might
1847  * be able to relax this to allow other safe, unparameterized
1848  * inner paths, but right now create_unique_path is not on board
1849  * with that.)
1850  */
1851  if (save_jointype == JOIN_UNIQUE_INNER)
1852  {
1853  if (innerpath != innerrel->cheapest_total_path)
1854  continue;
1855  innerpath = (Path *) create_unique_path(root, innerrel,
1856  innerpath,
1857  extra->sjinfo);
1858  Assert(innerpath);
1859  }
1860 
1861  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
1862  pathkeys, jointype, extra);
1863 
1864  /*
1865  * Try generating a result cache path and see if that makes the
1866  * nested loop any cheaper.
1867  */
1868  rcpath = get_resultcache_path(root, innerrel, outerrel,
1869  innerpath, outerpath, jointype,
1870  extra);
1871  if (rcpath != NULL)
1872  try_partial_nestloop_path(root, joinrel, outerpath, rcpath,
1873  pathkeys, jointype, extra);
1874  }
1875  }
1876 }
List * partial_pathlist
Definition: pathnodes.h:692
List * cheapest_parameterized_paths
Definition: pathnodes.h:696
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1641
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1082
JoinType
Definition: nodes.h:706
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:2521
struct Path * cheapest_total_path
Definition: pathnodes.h:694
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:660
List * pathkeys
Definition: pathnodes.h:1188
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
bool parallel_safe
Definition: pathnodes.h:1180
Definition: pg_list.h:50
static Path * get_resultcache_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:461

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

References Assert, compare_path_costs(), find_mergeclauses_for_outer_pathkeys(), get_cheapest_path_for_pathkeys(), JOIN_FULL, JOIN_INNER, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, list_copy(), list_length(), list_truncate(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, Path::pathkeys, pathkeys_contained_in(), RelOptInfo::pathlist, STARTUP_COST, TOTAL_COST, trim_mergeclauses_for_inner_pathkeys(), and try_mergejoin_path().

Referenced by consider_parallel_mergejoin(), and match_unsorted_outer().

1278 {
1279  List *mergeclauses;
1280  List *innersortkeys;
1281  List *trialsortkeys;
1282  Path *cheapest_startup_inner;
1283  Path *cheapest_total_inner;
1284  JoinType save_jointype = jointype;
1285  int num_sortkeys;
1286  int sortkeycnt;
1287 
1288  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1289  jointype = JOIN_INNER;
1290 
1291  /* Look for useful mergeclauses (if any) */
1292  mergeclauses =
1294  outerpath->pathkeys,
1295  extra->mergeclause_list);
1296 
1297  /*
1298  * Done with this outer path if no chance for a mergejoin.
1299  *
1300  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1301  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1302  * but since mergejoin is our only join type that supports FULL JOIN
1303  * without any join clauses, it's necessary to generate a clauseless
1304  * mergejoin path instead.
1305  */
1306  if (mergeclauses == NIL)
1307  {
1308  if (jointype == JOIN_FULL)
1309  /* okay to try for mergejoin */ ;
1310  else
1311  return;
1312  }
1313  if (useallclauses &&
1314  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1315  return;
1316 
1317  /* Compute the required ordering of the inner path */
1318  innersortkeys = make_inner_pathkeys_for_merge(root,
1319  mergeclauses,
1320  outerpath->pathkeys);
1321 
1322  /*
1323  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1324  * a sort will be needed, only cheapest total cost matters. (But
1325  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1326  * already correctly sorted.)
1327  */
1328  try_mergejoin_path(root,
1329  joinrel,
1330  outerpath,
1331  inner_cheapest_total,
1332  merge_pathkeys,
1333  mergeclauses,
1334  NIL,
1335  innersortkeys,
1336  jointype,
1337  extra,
1338  is_partial);
1339 
1340  /* Can't do anything else if inner path needs to be unique'd */
1341  if (save_jointype == JOIN_UNIQUE_INNER)
1342  return;
1343 
1344  /*
1345  * Look for presorted inner paths that satisfy the innersortkey list ---
1346  * or any truncation thereof, if we are allowed to build a mergejoin using
1347  * a subset of the merge clauses. Here, we consider both cheap startup
1348  * cost and cheap total cost.
1349  *
1350  * Currently we do not consider parameterized inner paths here. This
1351  * interacts with decisions elsewhere that also discriminate against
1352  * mergejoins with parameterized inputs; see comments in
1353  * src/backend/optimizer/README.
1354  *
1355  * As we shorten the sortkey list, we should consider only paths that are
1356  * strictly cheaper than (in particular, not the same as) any path found
1357  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1358  * merge keys than a given path allows (treating the rest as plain
1359  * joinquals), which is unlikely to be a good idea. Also, eliminating
1360  * paths here on the basis of compare_path_costs is a lot cheaper than
1361  * building the mergejoin path only to throw it away.
1362  *
1363  * If inner_cheapest_total is well enough sorted to have not required a
1364  * sort in the path made above, we shouldn't make a duplicate path with
1365  * it, either. We handle that case with the same logic that handles the
1366  * previous consideration, by initializing the variables that track
1367  * cheapest-so-far properly. Note that we do NOT reject
1368  * inner_cheapest_total if we find it matches some shorter set of
1369  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1370  * sorting inner_cheapest_total, whereas we did sort it above, so the
1371  * plans being considered are different.
1372  */
1373  if (pathkeys_contained_in(innersortkeys,
1374  inner_cheapest_total->pathkeys))
1375  {
1376  /* inner_cheapest_total didn't require a sort */
1377  cheapest_startup_inner = inner_cheapest_total;
1378  cheapest_total_inner = inner_cheapest_total;
1379  }
1380  else
1381  {
1382  /* it did require a sort, at least for the full set of keys */
1383  cheapest_startup_inner = NULL;
1384  cheapest_total_inner = NULL;
1385  }
1386  num_sortkeys = list_length(innersortkeys);
1387  if (num_sortkeys > 1 && !useallclauses)
1388  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1389  else
1390  trialsortkeys = innersortkeys; /* won't really truncate */
1391 
1392  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1393  {
1394  Path *innerpath;
1395  List *newclauses = NIL;
1396 
1397  /*
1398  * Look for an inner path ordered well enough for the first
1399  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1400  * destructively, which is why we made a copy...
1401  */
1402  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1403  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1404  trialsortkeys,
1405  NULL,
1406  TOTAL_COST,
1407  is_partial);
1408  if (innerpath != NULL &&
1409  (cheapest_total_inner == NULL ||
1410  compare_path_costs(innerpath, cheapest_total_inner,
1411  TOTAL_COST) < 0))
1412  {
1413  /* Found a cheap (or even-cheaper) sorted path */
1414  /* Select the right mergeclauses, if we didn't already */
1415  if (sortkeycnt < num_sortkeys)
1416  {
1417  newclauses =
1419  mergeclauses,
1420  trialsortkeys);
1421  Assert(newclauses != NIL);
1422  }
1423  else
1424  newclauses = mergeclauses;
1425  try_mergejoin_path(root,
1426  joinrel,
1427  outerpath,
1428  innerpath,
1429  merge_pathkeys,
1430  newclauses,
1431  NIL,
1432  NIL,
1433  jointype,
1434  extra,
1435  is_partial);
1436  cheapest_total_inner = innerpath;
1437  }
1438  /* Same on the basis of cheapest startup cost ... */
1439  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1440  trialsortkeys,
1441  NULL,
1442  STARTUP_COST,
1443  is_partial);
1444  if (innerpath != NULL &&
1445  (cheapest_startup_inner == NULL ||
1446  compare_path_costs(innerpath, cheapest_startup_inner,
1447  STARTUP_COST) < 0))
1448  {
1449  /* Found a cheap (or even-cheaper) sorted path */
1450  if (innerpath != cheapest_total_inner)
1451  {
1452  /*
1453  * Avoid rebuilding clause list if we already made one; saves
1454  * memory in big join trees...
1455  */
1456  if (newclauses == NIL)
1457  {
1458  if (sortkeycnt < num_sortkeys)
1459  {
1460  newclauses =
1462  mergeclauses,
1463  trialsortkeys);
1464  Assert(newclauses != NIL);
1465  }
1466  else
1467  newclauses = mergeclauses;
1468  }
1469  try_mergejoin_path(root,
1470  joinrel,
1471  outerpath,
1472  innerpath,
1473  merge_pathkeys,
1474  newclauses,
1475  NIL,
1476  NIL,
1477  jointype,
1478  extra,
1479  is_partial);
1480  }
1481  cheapest_startup_inner = innerpath;
1482  }
1483 
1484  /*
1485  * Don't consider truncated sortkeys if we need all clauses.
1486  */
1487  if (useallclauses)
1488  break;
1489  }
1490 }
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:404
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:742
#define NIL
Definition: pg_list.h:65
List * list_truncate(List *list, int new_size)
Definition: list.c:600
List * list_copy(const List *oldlist)
Definition: list.c:1418
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1547
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1262
JoinType
Definition: nodes.h:706
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71
List * mergeclause_list
Definition: pathnodes.h:2519
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1650
List * pathkeys
Definition: pathnodes.h:1188
#define Assert(condition)
Definition: c.h:804
static int list_length(const List *l)
Definition: pg_list.h:149
List * pathlist
Definition: pathnodes.h:690
Definition: pg_list.h:50

◆ get_resultcache_path()

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

Definition at line 461 of file joinpath.c.

References RelOptInfo::baserestrictinfo, contain_volatile_functions(), create_resultcache_path(), enable_resultcache, JoinPathExtraData::inner_unique, JOIN_ANTI, JOIN_SEMI, RelOptInfo::lateral_vars, lfirst, NIL, Path::param_info, paraminfo_get_equal_hashops(), Path::parent, ParamPathInfo::ppi_clauses, RelOptInfo::reltarget, and RelOptInfo::rows.

Referenced by consider_parallel_nestloop(), and match_unsorted_outer().

465 {
466  List *param_exprs;
467  List *hash_operators;
468  ListCell *lc;
469 
470  /* Obviously not if it's disabled */
471  if (!enable_resultcache)
472  return NULL;
473 
474  /*
475  * We can safely not bother with all this unless we expect to perform more
476  * than one inner scan. The first scan is always going to be a cache
477  * miss. This would likely fail later anyway based on costs, so this is
478  * really just to save some wasted effort.
479  */
480  if (outer_path->parent->rows < 2)
481  return NULL;
482 
483  /*
484  * We can only have a result cache when there's some kind of cache key,
485  * either parameterized path clauses or lateral Vars. No cache key sounds
486  * more like something a Materialize node might be more useful for.
487  */
488  if ((inner_path->param_info == NULL ||
489  inner_path->param_info->ppi_clauses == NIL) &&
490  innerrel->lateral_vars == NIL)
491  return NULL;
492 
493  /*
494  * Currently we don't do this for SEMI and ANTI joins unless they're
495  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
496  * don't scan the inner node to completion, which will mean result cache
497  * cannot mark the cache entry as complete.
498  *
499  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
500  * = true. Should we? See add_paths_to_joinrel()
501  */
502  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
503  jointype == JOIN_ANTI))
504  return NULL;
505 
506  /*
507  * We can't use a result cache if there are volatile functions in the
508  * inner rel's target list or restrict list. A cache hit could reduce the
509  * number of calls to these functions.
510  */
511  if (contain_volatile_functions((Node *) innerrel->reltarget))
512  return NULL;
513 
514  foreach(lc, innerrel->baserestrictinfo)
515  {
516  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
517 
518  if (contain_volatile_functions((Node *) rinfo))
519  return NULL;
520  }
521 
522  /* Check if we have hash ops for each parameter to the path */
524  inner_path->param_info,
525  outerrel,
526  innerrel,
527  &param_exprs,
528  &hash_operators))
529  {
530  return (Path *) create_resultcache_path(root,
531  innerrel,
532  inner_path,
533  param_exprs,
534  hash_operators,
535  extra->inner_unique,
536  outer_path->parent->rows);
537  }
538 
539  return NULL;
540 }
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List **param_exprs, List **operators)
Definition: joinpath.c:378
#define NIL
Definition: pg_list.h:65
ResultCachePath * create_resultcache_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, double calls)
Definition: pathnode.c:1585
bool enable_resultcache
Definition: costsize.c:143
List * baserestrictinfo
Definition: pathnodes.h:740
ParamPathInfo * param_info
Definition: pathnodes.h:1177
Definition: nodes.h:539
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:448
RelOptInfo * parent
Definition: pathnodes.h:1174
double rows
Definition: pathnodes.h:679
#define lfirst(lc)
Definition: pg_list.h:169
List * lateral_vars
Definition: pathnodes.h:711
List * ppi_clauses
Definition: pathnodes.h:1135
Definition: pg_list.h:50
struct PathTarget * reltarget
Definition: pathnodes.h:687

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

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

Referenced by add_paths_to_joinrel().

1896 {
1897  JoinType save_jointype = jointype;
1898  bool isouterjoin = IS_OUTER_JOIN(jointype);
1899  List *hashclauses;
1900  ListCell *l;
1901 
1902  /*
1903  * We need to build only one hashclauses list for any given pair of outer
1904  * and inner relations; all of the hashable clauses will be used as keys.
1905  *
1906  * Scan the join's restrictinfo list to find hashjoinable clauses that are
1907  * usable with this pair of sub-relations.
1908  */
1909  hashclauses = NIL;
1910  foreach(l, extra->restrictlist)
1911  {
1912  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1913 
1914  /*
1915  * If processing an outer join, only use its own join clauses for
1916  * hashing. For inner joins we need not be so picky.
1917  */
1918  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
1919  continue;
1920 
1921  if (!restrictinfo->can_join ||
1922  restrictinfo->hashjoinoperator == InvalidOid)
1923  continue; /* not hashjoinable */
1924 
1925  /*
1926  * Check if clause has the form "outer op inner" or "inner op outer".
1927  */
1928  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
1929  continue; /* no good for these input relations */
1930 
1931  hashclauses = lappend(hashclauses, restrictinfo);
1932  }
1933 
1934  /* If we found any usable hashclauses, make paths */
1935  if (hashclauses)
1936  {
1937  /*
1938  * We consider both the cheapest-total-cost and cheapest-startup-cost
1939  * outer paths. There's no need to consider any but the
1940  * cheapest-total-cost inner path, however.
1941  */
1942  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
1943  Path *cheapest_total_outer = outerrel->cheapest_total_path;
1944  Path *cheapest_total_inner = innerrel->cheapest_total_path;
1945 
1946  /*
1947  * If either cheapest-total path is parameterized by the other rel, we
1948  * can't use a hashjoin. (There's no use looking for alternative
1949  * input paths, since these should already be the least-parameterized
1950  * available paths.)
1951  */
1952  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
1953  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
1954  return;
1955 
1956  /* Unique-ify if need be; we ignore parameterized possibilities */
1957  if (jointype == JOIN_UNIQUE_OUTER)
1958  {
1959  cheapest_total_outer = (Path *)
1960  create_unique_path(root, outerrel,
1961  cheapest_total_outer, extra->sjinfo);
1962  Assert(cheapest_total_outer);
1963  jointype = JOIN_INNER;
1964  try_hashjoin_path(root,
1965  joinrel,
1966  cheapest_total_outer,
1967  cheapest_total_inner,
1968  hashclauses,
1969  jointype,
1970  extra);
1971  /* no possibility of cheap startup here */
1972  }
1973  else if (jointype == JOIN_UNIQUE_INNER)
1974  {
1975  cheapest_total_inner = (Path *)
1976  create_unique_path(root, innerrel,
1977  cheapest_total_inner, extra->sjinfo);
1978  Assert(cheapest_total_inner);
1979  jointype = JOIN_INNER;
1980  try_hashjoin_path(root,
1981  joinrel,
1982  cheapest_total_outer,
1983  cheapest_total_inner,
1984  hashclauses,
1985  jointype,
1986  extra);
1987  if (cheapest_startup_outer != NULL &&
1988  cheapest_startup_outer != cheapest_total_outer)
1989  try_hashjoin_path(root,
1990  joinrel,
1991  cheapest_startup_outer,
1992  cheapest_total_inner,
1993  hashclauses,
1994  jointype,
1995  extra);
1996  }
1997  else
1998  {
1999  /*
2000  * For other jointypes, we consider the cheapest startup outer
2001  * together with the cheapest total inner, and then consider
2002  * pairings of cheapest-total paths including parameterized ones.
2003  * There is no use in generating parameterized paths on the basis
2004  * of possibly cheap startup cost, so this is sufficient.
2005  */
2006  ListCell *lc1;
2007  ListCell *lc2;
2008 
2009  if (cheapest_startup_outer != NULL)
2010  try_hashjoin_path(root,
2011  joinrel,
2012  cheapest_startup_outer,
2013  cheapest_total_inner,
2014  hashclauses,
2015  jointype,
2016  extra);
2017 
2018  foreach(lc1, outerrel->cheapest_parameterized_paths)
2019  {
2020  Path *outerpath = (Path *) lfirst(lc1);
2021 
2022  /*
2023  * We cannot use an outer path that is parameterized by the
2024  * inner rel.
2025  */
2026  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2027  continue;
2028 
2029  foreach(lc2, innerrel->cheapest_parameterized_paths)
2030  {
2031  Path *innerpath = (Path *) lfirst(lc2);
2032 
2033  /*
2034  * We cannot use an inner path that is parameterized by
2035  * the outer rel, either.
2036  */
2037  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2038  continue;
2039 
2040  if (outerpath == cheapest_startup_outer &&
2041  innerpath == cheapest_total_inner)
2042  continue; /* already tried it */
2043 
2044  try_hashjoin_path(root,
2045  joinrel,
2046  outerpath,
2047  innerpath,
2048  hashclauses,
2049  jointype,
2050  extra);
2051  }
2052  }
2053  }
2054 
2055  /*
2056  * If the joinrel is parallel-safe, we may be able to consider a
2057  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2058  * because the outer path will be partial, and therefore we won't be
2059  * able to properly guarantee uniqueness. Similarly, we can't handle
2060  * JOIN_FULL and JOIN_RIGHT, because they can produce false null
2061  * extended rows. Also, the resulting path must not be parameterized.
2062  * We would be able to support JOIN_FULL and JOIN_RIGHT for Parallel
2063  * Hash, since in that case we're back to a single hash table with a
2064  * single set of match bits for each batch, but that will require
2065  * figuring out a deadlock-free way to wait for the probe to finish.
2066  */
2067  if (joinrel->consider_parallel &&
2068  save_jointype != JOIN_UNIQUE_OUTER &&
2069  save_jointype != JOIN_FULL &&
2070  save_jointype != JOIN_RIGHT &&
2071  outerrel->partial_pathlist != NIL &&
2072  bms_is_empty(joinrel->lateral_relids))
2073  {
2074  Path *cheapest_partial_outer;
2075  Path *cheapest_partial_inner = NULL;
2076  Path *cheapest_safe_inner = NULL;
2077 
2078  cheapest_partial_outer =
2079  (Path *) linitial(outerrel->partial_pathlist);
2080 
2081  /*
2082  * Can we use a partial inner plan too, so that we can build a
2083  * shared hash table in parallel? We can't handle
2084  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2085  */
2086  if (innerrel->partial_pathlist != NIL &&
2087  save_jointype != JOIN_UNIQUE_INNER &&
2089  {
2090  cheapest_partial_inner =
2091  (Path *) linitial(innerrel->partial_pathlist);
2092  try_partial_hashjoin_path(root, joinrel,
2093  cheapest_partial_outer,
2094  cheapest_partial_inner,
2095  hashclauses, jointype, extra,
2096  true /* parallel_hash */ );
2097  }
2098 
2099  /*
2100  * Normally, given that the joinrel is parallel-safe, the cheapest
2101  * total inner path will also be parallel-safe, but if not, we'll
2102  * have to search for the cheapest safe, unparameterized inner
2103  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2104  * inner path.
2105  */
2106  if (cheapest_total_inner->parallel_safe)
2107  cheapest_safe_inner = cheapest_total_inner;
2108  else if (save_jointype != JOIN_UNIQUE_INNER)
2109  cheapest_safe_inner =
2111 
2112  if (cheapest_safe_inner != NULL)
2113  try_partial_hashjoin_path(root, joinrel,
2114  cheapest_partial_outer,
2115  cheapest_safe_inner,
2116  hashclauses, jointype, extra,
2117  false /* parallel_hash */ );
2118  }
2119  }
2120 }
#define NIL
Definition: pg_list.h:65
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:907
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:973
struct Path * cheapest_startup_path
Definition: pathnodes.h:693
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:755
bool enable_parallel_hash
Definition: costsize.c:150
List * partial_pathlist
Definition: pathnodes.h:692
List * cheapest_parameterized_paths
Definition: pathnodes.h:696
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1641
JoinType
Definition: nodes.h:706
Relids lateral_relids
Definition: pathnodes.h:701
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:2521
#define linitial(l)
Definition: pg_list.h:174
struct Path * cheapest_total_path
Definition: pathnodes.h:694
Relids relids
Definition: pathnodes.h:676
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:482
List * lappend(List *list, void *datum)
Definition: list.c:336
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2128
#define InvalidOid
Definition: postgres_ext.h:36
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:42
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
bool parallel_safe
Definition: pathnodes.h:1180
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1034
Oid hashjoinoperator
Definition: pathnodes.h:2106
bool consider_parallel
Definition: pathnodes.h:684
List * pathlist
Definition: pathnodes.h:690
Definition: pg_list.h:50

◆ match_unsorted_outer()

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

Definition at line 1516 of file joinpath.c.

References Assert, bms_is_empty(), build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, consider_parallel_mergejoin(), consider_parallel_nestloop(), create_material_path(), create_unique_path(), elog, enable_material, ERROR, ExecMaterializesOutput(), generate_mergejoin_paths(), get_cheapest_parallel_safe_total_inner(), get_resultcache_path(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_LEFT, JOIN_RIGHT, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lfirst, NIL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, JoinPathExtraData::sjinfo, and try_nestloop_path().

Referenced by add_paths_to_joinrel().

1522 {
1523  JoinType save_jointype = jointype;
1524  bool nestjoinOK;
1525  bool useallclauses;
1526  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1527  Path *matpath = NULL;
1528  ListCell *lc1;
1529 
1530  /*
1531  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1532  * are doing a right or full mergejoin, we must use *all* the mergeclauses
1533  * as join clauses, else we will not have a valid plan. (Although these
1534  * two flags are currently inverses, keep them separate for clarity and
1535  * possible future changes.)
1536  */
1537  switch (jointype)
1538  {
1539  case JOIN_INNER:
1540  case JOIN_LEFT:
1541  case JOIN_SEMI:
1542  case JOIN_ANTI:
1543  nestjoinOK = true;
1544  useallclauses = false;
1545  break;
1546  case JOIN_RIGHT:
1547  case JOIN_FULL:
1548  nestjoinOK = false;
1549  useallclauses = true;
1550  break;
1551  case JOIN_UNIQUE_OUTER:
1552  case JOIN_UNIQUE_INNER:
1553  jointype = JOIN_INNER;
1554  nestjoinOK = true;
1555  useallclauses = false;
1556  break;
1557  default:
1558  elog(ERROR, "unrecognized join type: %d",
1559  (int) jointype);
1560  nestjoinOK = false; /* keep compiler quiet */
1561  useallclauses = false;
1562  break;
1563  }
1564 
1565  /*
1566  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1567  * we will consider it below as a member of cheapest_parameterized_paths,
1568  * but the other possibilities considered in this routine aren't usable.
1569  */
1570  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1571  inner_cheapest_total = NULL;
1572 
1573  /*
1574  * If we need to unique-ify the inner path, we will consider only the
1575  * cheapest-total inner.
1576  */
1577  if (save_jointype == JOIN_UNIQUE_INNER)
1578  {
1579  /* No way to do this with an inner path parameterized by outer rel */
1580  if (inner_cheapest_total == NULL)
1581  return;
1582  inner_cheapest_total = (Path *)
1583  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1584  Assert(inner_cheapest_total);
1585  }
1586  else if (nestjoinOK)
1587  {
1588  /*
1589  * Consider materializing the cheapest inner path, unless
1590  * enable_material is off or the path in question materializes its
1591  * output anyway.
1592  */
1593  if (enable_material && inner_cheapest_total != NULL &&
1594  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1595  matpath = (Path *)
1596  create_material_path(innerrel, inner_cheapest_total);
1597  }
1598 
1599  foreach(lc1, outerrel->pathlist)
1600  {
1601  Path *outerpath = (Path *) lfirst(lc1);
1602  List *merge_pathkeys;
1603 
1604  /*
1605  * We cannot use an outer path that is parameterized by the inner rel.
1606  */
1607  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1608  continue;
1609 
1610  /*
1611  * If we need to unique-ify the outer path, it's pointless to consider
1612  * any but the cheapest outer. (XXX we don't consider parameterized
1613  * outers, nor inners, for unique-ified cases. Should we?)
1614  */
1615  if (save_jointype == JOIN_UNIQUE_OUTER)
1616  {
1617  if (outerpath != outerrel->cheapest_total_path)
1618  continue;
1619  outerpath = (Path *) create_unique_path(root, outerrel,
1620  outerpath, extra->sjinfo);
1621  Assert(outerpath);
1622  }
1623 
1624  /*
1625  * The result will have this sort order (even if it is implemented as
1626  * a nestloop, and even if some of the mergeclauses are implemented by
1627  * qpquals rather than as true mergeclauses):
1628  */
1629  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1630  outerpath->pathkeys);
1631 
1632  if (save_jointype == JOIN_UNIQUE_INNER)
1633  {
1634  /*
1635  * Consider nestloop join, but only with the unique-ified cheapest
1636  * inner path
1637  */
1638  try_nestloop_path(root,
1639  joinrel,
1640  outerpath,
1641  inner_cheapest_total,
1642  merge_pathkeys,
1643  jointype,
1644  extra);
1645  }
1646  else if (nestjoinOK)
1647  {
1648  /*
1649  * Consider nestloop joins using this outer path and various
1650  * available paths for the inner relation. We consider the
1651  * cheapest-total paths for each available parameterization of the
1652  * inner relation, including the unparameterized case.
1653  */
1654  ListCell *lc2;
1655 
1656  foreach(lc2, innerrel->cheapest_parameterized_paths)
1657  {
1658  Path *innerpath = (Path *) lfirst(lc2);
1659  Path *rcpath;
1660 
1661  try_nestloop_path(root,
1662  joinrel,
1663  outerpath,
1664  innerpath,
1665  merge_pathkeys,
1666  jointype,
1667  extra);
1668 
1669  /*
1670  * Try generating a result cache path and see if that makes
1671  * the nested loop any cheaper.
1672  */
1673  rcpath = get_resultcache_path(root, innerrel, outerrel,
1674  innerpath, outerpath, jointype,
1675  extra);
1676  if (rcpath != NULL)
1677  try_nestloop_path(root,
1678  joinrel,
1679  outerpath,
1680  rcpath,
1681  merge_pathkeys,
1682  jointype,
1683  extra);
1684  }
1685 
1686  /* Also consider materialized form of the cheapest inner path */
1687  if (matpath != NULL)
1688  try_nestloop_path(root,
1689  joinrel,
1690  outerpath,
1691  matpath,
1692  merge_pathkeys,
1693  jointype,
1694  extra);
1695  }
1696 
1697  /* Can't do anything else if outer path needs to be unique'd */
1698  if (save_jointype == JOIN_UNIQUE_OUTER)
1699  continue;
1700 
1701  /* Can't do anything else if inner rel is parameterized by outer */
1702  if (inner_cheapest_total == NULL)
1703  continue;
1704 
1705  /* Generate merge join paths */
1706  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1707  save_jointype, extra, useallclauses,
1708  inner_cheapest_total, merge_pathkeys,
1709  false);
1710  }
1711 
1712  /*
1713  * Consider partial nestloop and mergejoin plan if outerrel has any
1714  * partial path and the joinrel is parallel-safe. However, we can't
1715  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1716  * therefore we won't be able to properly guarantee uniqueness. Nor can
1717  * we handle joins needing lateral rels, since partial paths must not be
1718  * parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1719  * because they can produce false null extended rows.
1720  */
1721  if (joinrel->consider_parallel &&
1722  save_jointype != JOIN_UNIQUE_OUTER &&
1723  save_jointype != JOIN_FULL &&
1724  save_jointype != JOIN_RIGHT &&
1725  outerrel->partial_pathlist != NIL &&
1726  bms_is_empty(joinrel->lateral_relids))
1727  {
1728  if (nestjoinOK)
1729  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1730  save_jointype, extra);
1731 
1732  /*
1733  * If inner_cheapest_total is NULL or non parallel-safe then find the
1734  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1735  * can't use any alternative inner path.
1736  */
1737  if (inner_cheapest_total == NULL ||
1738  !inner_cheapest_total->parallel_safe)
1739  {
1740  if (save_jointype == JOIN_UNIQUE_INNER)
1741  return;
1742 
1743  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1744  }
1745 
1746  if (inner_cheapest_total)
1747  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1748  save_jointype, extra,
1749  inner_cheapest_total);
1750  }
1751 }
#define NIL
Definition: pg_list.h:65
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:548
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1552
List * partial_pathlist
Definition: pathnodes.h:692
List * cheapest_parameterized_paths
Definition: pathnodes.h:696
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1641
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1082
JoinType
Definition: nodes.h:706
NodeTag pathtype
Definition: pathnodes.h:1172
Relids lateral_relids
Definition: pathnodes.h:701
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:2521
#define ERROR
Definition: elog.h:46
struct Path * cheapest_total_path
Definition: pathnodes.h:694
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:1268
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:482
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1806
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1766
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:42
List * pathkeys
Definition: pathnodes.h:1188
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
bool parallel_safe
Definition: pathnodes.h:1180
bool consider_parallel
Definition: pathnodes.h:684
#define elog(elevel,...)
Definition: elog.h:232
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:643
List * pathlist
Definition: pathnodes.h:690
Definition: pg_list.h:50
static Path * get_resultcache_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:461
bool enable_material
Definition: costsize.c:142

◆ paraminfo_get_equal_hashops()

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

Definition at line 378 of file joinpath.c.

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

Referenced by get_resultcache_path().

382 {
383  ListCell *lc;
384 
385  *param_exprs = NIL;
386  *operators = NIL;
387 
388  if (param_info != NULL)
389  {
390  List *clauses = param_info->ppi_clauses;
391 
392  foreach(lc, clauses)
393  {
394  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
395  OpExpr *opexpr;
396  Node *expr;
397 
398  /* can't use result cache without a valid hash equals operator */
399  if (!OidIsValid(rinfo->hasheqoperator) ||
400  !clause_sides_match_join(rinfo, outerrel, innerrel))
401  {
402  list_free(*operators);
403  list_free(*param_exprs);
404  return false;
405  }
406 
407  /*
408  * We already checked that this is an OpExpr with 2 args when
409  * setting hasheqoperator.
410  */
411  opexpr = (OpExpr *) rinfo->clause;
412  if (rinfo->outer_is_left)
413  expr = (Node *) linitial(opexpr->args);
414  else
415  expr = (Node *) lsecond(opexpr->args);
416 
417  *operators = lappend_oid(*operators, rinfo->hasheqoperator);
418  *param_exprs = lappend(*param_exprs, expr);
419  }
420  }
421 
422  /* Now add any lateral vars to the cache key too */
423  foreach(lc, innerrel->lateral_vars)
424  {
425  Node *expr = (Node *) lfirst(lc);
426  TypeCacheEntry *typentry;
427 
428  /* Reject if there are any volatile functions */
429  if (contain_volatile_functions(expr))
430  {
431  list_free(*operators);
432  list_free(*param_exprs);
433  return false;
434  }
435 
436  typentry = lookup_type_cache(exprType(expr),
438 
439  /* can't use result cache without a valid hash equals operator */
440  if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
441  {
442  list_free(*operators);
443  list_free(*param_exprs);
444  return false;
445  }
446 
447  *operators = lappend_oid(*operators, typentry->eq_opr);
448  *param_exprs = lappend(*param_exprs, expr);
449  }
450 
451  /* We're okay to use result cache */
452  return true;
453 }
#define NIL
Definition: pg_list.h:65
Definition: nodes.h:539
#define TYPECACHE_EQ_OPR
Definition: typcache.h:136
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:448
List * lappend_oid(List *list, Oid datum)
Definition: list.c:372
#define OidIsValid(objectId)
Definition: c.h:710
#define lsecond(l)
Definition: pg_list.h:179
#define linitial(l)
Definition: pg_list.h:174
bool outer_is_left
Definition: pathnodes.h:2103
Oid hasheqoperator
Definition: pathnodes.h:2115
List * lappend(List *list, void *datum)
Definition: list.c:336
Expr * clause
Definition: pathnodes.h:2045
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:338
#define lfirst(lc)
Definition: pg_list.h:169
List * lateral_vars
Definition: pathnodes.h:711
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1034
List * ppi_clauses
Definition: pathnodes.h:1135
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:41
void list_free(List *list)
Definition: list.c:1391
List * args
Definition: primnodes.h:548
Definition: pg_list.h:50
#define TYPECACHE_HASH_PROC
Definition: typcache.h:140

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

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

Referenced by add_paths_to_joinrel().

2152 {
2153  List *result_list = NIL;
2154  bool isouterjoin = IS_OUTER_JOIN(jointype);
2155  bool have_nonmergeable_joinclause = false;
2156  ListCell *l;
2157 
2158  foreach(l, restrictlist)
2159  {
2160  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2161 
2162  /*
2163  * If processing an outer join, only use its own join clauses in the
2164  * merge. For inner joins we can use pushed-down clauses too. (Note:
2165  * we don't set have_nonmergeable_joinclause here because pushed-down
2166  * clauses will become otherquals not joinquals.)
2167  */
2168  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2169  continue;
2170 
2171  /* Check that clause is a mergeable operator clause */
2172  if (!restrictinfo->can_join ||
2173  restrictinfo->mergeopfamilies == NIL)
2174  {
2175  /*
2176  * The executor can handle extra joinquals that are constants, but
2177  * not anything else, when doing right/full merge join. (The
2178  * reason to support constants is so we can do FULL JOIN ON
2179  * FALSE.)
2180  */
2181  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2182  have_nonmergeable_joinclause = true;
2183  continue; /* not mergejoinable */
2184  }
2185 
2186  /*
2187  * Check if clause has the form "outer op inner" or "inner op outer".
2188  */
2189  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2190  {
2191  have_nonmergeable_joinclause = true;
2192  continue; /* no good for these input relations */
2193  }
2194 
2195  /*
2196  * Insist that each side have a non-redundant eclass. This
2197  * restriction is needed because various bits of the planner expect
2198  * that each clause in a merge be associable with some pathkey in a
2199  * canonical pathkey list, but redundant eclasses can't appear in
2200  * canonical sort orderings. (XXX it might be worth relaxing this,
2201  * but not enough time to address it for 8.3.)
2202  *
2203  * Note: it would be bad if this condition failed for an otherwise
2204  * mergejoinable FULL JOIN clause, since that would result in
2205  * undesirable planner failure. I believe that is not possible
2206  * however; a variable involved in a full join could only appear in
2207  * below_outer_join eclasses, which aren't considered redundant.
2208  *
2209  * This case *can* happen for left/right join clauses: the outer-side
2210  * variable could be equated to a constant. Because we will propagate
2211  * that constant across the join clause, the loss of ability to do a
2212  * mergejoin is not really all that big a deal, and so it's not clear
2213  * that improving this is important.
2214  */
2215  update_mergeclause_eclasses(root, restrictinfo);
2216 
2217  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2218  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2219  {
2220  have_nonmergeable_joinclause = true;
2221  continue; /* can't handle redundant eclasses */
2222  }
2223 
2224  result_list = lappend(result_list, restrictinfo);
2225  }
2226 
2227  /*
2228  * Report whether mergejoin is allowed (see comment at top of function).
2229  */
2230  switch (jointype)
2231  {
2232  case JOIN_RIGHT:
2233  case JOIN_FULL:
2234  *mergejoin_allowed = !have_nonmergeable_joinclause;
2235  break;
2236  default:
2237  *mergejoin_allowed = true;
2238  break;
2239  }
2240 
2241  return result_list;
2242 }
#define NIL
Definition: pg_list.h:65
#define IsA(nodeptr, _type_)
Definition: nodes.h:590
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:755
EquivalenceClass * right_ec
Definition: pathnodes.h:2097
List * mergeopfamilies
Definition: pathnodes.h:2093
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1000
Relids relids
Definition: pathnodes.h:676
List * lappend(List *list, void *datum)
Definition: list.c:336
Expr * clause
Definition: pathnodes.h:2045
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2128
#define lfirst(lc)
Definition: pg_list.h:169
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1034
EquivalenceClass * left_ec
Definition: pathnodes.h:2096
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228

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

References Assert, bms_is_empty(), build_join_pathkeys(), RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, create_unique_path(), find_mergeclauses_for_outer_pathkeys(), foreach_current_index, get_cheapest_parallel_safe_total_inner(), JOIN_FULL, JOIN_INNER, JOIN_RIGHT, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lcons(), lfirst, linitial, list_copy(), list_delete_nth_cell(), list_head(), list_length(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, Path::parallel_safe, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, select_outer_pathkeys_for_merge(), JoinPathExtraData::sjinfo, try_mergejoin_path(), and try_partial_mergejoin_path().

Referenced by add_paths_to_joinrel().

1072 {
1073  JoinType save_jointype = jointype;
1074  Path *outer_path;
1075  Path *inner_path;
1076  Path *cheapest_partial_outer = NULL;
1077  Path *cheapest_safe_inner = NULL;
1078  List *all_pathkeys;
1079  ListCell *l;
1080 
1081  /*
1082  * We only consider the cheapest-total-cost input paths, since we are
1083  * assuming here that a sort is required. We will consider
1084  * cheapest-startup-cost input paths later, and only if they don't need a
1085  * sort.
1086  *
1087  * This function intentionally does not consider parameterized input
1088  * paths, except when the cheapest-total is parameterized. If we did so,
1089  * we'd have a combinatorial explosion of mergejoin paths of dubious
1090  * value. This interacts with decisions elsewhere that also discriminate
1091  * against mergejoins with parameterized inputs; see comments in
1092  * src/backend/optimizer/README.
1093  */
1094  outer_path = outerrel->cheapest_total_path;
1095  inner_path = innerrel->cheapest_total_path;
1096 
1097  /*
1098  * If either cheapest-total path is parameterized by the other rel, we
1099  * can't use a mergejoin. (There's no use looking for alternative input
1100  * paths, since these should already be the least-parameterized available
1101  * paths.)
1102  */
1103  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1104  PATH_PARAM_BY_REL(inner_path, outerrel))
1105  return;
1106 
1107  /*
1108  * If unique-ification is requested, do it and then handle as a plain
1109  * inner join.
1110  */
1111  if (jointype == JOIN_UNIQUE_OUTER)
1112  {
1113  outer_path = (Path *) create_unique_path(root, outerrel,
1114  outer_path, extra->sjinfo);
1115  Assert(outer_path);
1116  jointype = JOIN_INNER;
1117  }
1118  else if (jointype == JOIN_UNIQUE_INNER)
1119  {
1120  inner_path = (Path *) create_unique_path(root, innerrel,
1121  inner_path, extra->sjinfo);
1122  Assert(inner_path);
1123  jointype = JOIN_INNER;
1124  }
1125 
1126  /*
1127  * If the joinrel is parallel-safe, we may be able to consider a partial
1128  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1129  * outer path will be partial, and therefore we won't be able to properly
1130  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
1131  * JOIN_RIGHT, because they can produce false null extended rows. Also,
1132  * the resulting path must not be parameterized.
1133  */
1134  if (joinrel->consider_parallel &&
1135  save_jointype != JOIN_UNIQUE_OUTER &&
1136  save_jointype != JOIN_FULL &&
1137  save_jointype != JOIN_RIGHT &&
1138  outerrel->partial_pathlist != NIL &&
1139  bms_is_empty(joinrel->lateral_relids))
1140  {
1141  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1142 
1143  if (inner_path->parallel_safe)
1144  cheapest_safe_inner = inner_path;
1145  else if (save_jointype != JOIN_UNIQUE_INNER)
1146  cheapest_safe_inner =
1148  }
1149 
1150  /*
1151  * Each possible ordering of the available mergejoin clauses will generate
1152  * a differently-sorted result path at essentially the same cost. We have
1153  * no basis for choosing one over another at this level of joining, but
1154  * some sort orders may be more useful than others for higher-level
1155  * mergejoins, so it's worth considering multiple orderings.
1156  *
1157  * Actually, it's not quite true that every mergeclause ordering will
1158  * generate a different path order, because some of the clauses may be
1159  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1160  * what we do is convert the mergeclause list to a list of canonical
1161  * pathkeys, and then consider different orderings of the pathkeys.
1162  *
1163  * Generating a path for *every* permutation of the pathkeys doesn't seem
1164  * like a winning strategy; the cost in planning time is too high. For
1165  * now, we generate one path for each pathkey, listing that pathkey first
1166  * and the rest in random order. This should allow at least a one-clause
1167  * mergejoin without re-sorting against any other possible mergejoin
1168  * partner path. But if we've not guessed the right ordering of secondary
1169  * keys, we may end up evaluating clauses as qpquals when they could have
1170  * been done as mergeclauses. (In practice, it's rare that there's more
1171  * than two or three mergeclauses, so expending a huge amount of thought
1172  * on that is probably not worth it.)
1173  *
1174  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1175  * some heuristics behind it (see that function), so be sure to try it
1176  * exactly as-is as well as making variants.
1177  */
1178  all_pathkeys = select_outer_pathkeys_for_merge(root,
1179  extra->mergeclause_list,
1180  joinrel);
1181 
1182  foreach(l, all_pathkeys)
1183  {
1184  List *front_pathkey = (List *) lfirst(l);
1185  List *cur_mergeclauses;
1186  List *outerkeys;
1187  List *innerkeys;
1188  List *merge_pathkeys;
1189 
1190  /* Make a pathkey list with this guy first */
1191  if (l != list_head(all_pathkeys))
1192  outerkeys = lcons(front_pathkey,
1193  list_delete_nth_cell(list_copy(all_pathkeys),
1194  foreach_current_index(l)));
1195  else
1196  outerkeys = all_pathkeys; /* no work at first one... */
1197 
1198  /* Sort the mergeclauses into the corresponding ordering */
1199  cur_mergeclauses =
1201  outerkeys,
1202  extra->mergeclause_list);
1203 
1204  /* Should have used them all... */
1205  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1206 
1207  /* Build sort pathkeys for the inner side */
1208  innerkeys = make_inner_pathkeys_for_merge(root,
1209  cur_mergeclauses,
1210  outerkeys);
1211 
1212  /* Build pathkeys representing output sort order */
1213  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1214  outerkeys);
1215 
1216  /*
1217  * And now we can make the path.
1218  *
1219  * Note: it's possible that the cheapest paths will already be sorted
1220  * properly. try_mergejoin_path will detect that case and suppress an
1221  * explicit sort step, so we needn't do so here.
1222  */
1223  try_mergejoin_path(root,
1224  joinrel,
1225  outer_path,
1226  inner_path,
1227  merge_pathkeys,
1228  cur_mergeclauses,
1229  outerkeys,
1230  innerkeys,
1231  jointype,
1232  extra,
1233  false);
1234 
1235  /*
1236  * If we have partial outer and parallel safe inner path then try
1237  * partial mergejoin path.
1238  */
1239  if (cheapest_partial_outer && cheapest_safe_inner)
1241  joinrel,
1242  cheapest_partial_outer,
1243  cheapest_safe_inner,
1244  merge_pathkeys,
1245  cur_mergeclauses,
1246  outerkeys,
1247  innerkeys,
1248  jointype,
1249  extra);
1250  }
1251 }
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:742
#define NIL
Definition: pg_list.h:65
List * list_copy(const List *oldlist)
Definition: list.c:1418
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1547
List * partial_pathlist
Definition: pathnodes.h:692
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1641
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1082
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1262
JoinType
Definition: nodes.h:706
Relids lateral_relids
Definition: pathnodes.h:701
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:2521
#define linitial(l)
Definition: pg_list.h:174
struct Path * cheapest_total_path
Definition: pathnodes.h:694
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
List * mergeclause_list
Definition: pathnodes.h:2519
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:482
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1375
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:42
List * lcons(void *datum, List *list)
Definition: list.c:468
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
bool parallel_safe
Definition: pathnodes.h:1180
static int list_length(const List *l)
Definition: pg_list.h:149
bool consider_parallel
Definition: pathnodes.h:684
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:837
List * pathlist
Definition: pathnodes.h:690
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:711
Definition: pg_list.h:50
#define foreach_current_index(cell)
Definition: pg_list.h:382

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

References add_path(), add_path_precheck(), bms_free(), bms_overlap(), calc_non_nestloop_required_outer(), create_hashjoin_path(), initial_cost_hashjoin(), NIL, JoinPathExtraData::param_source_rels, JoinPathExtraData::restrictlist, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.

Referenced by hash_inner_and_outer().

914 {
915  Relids required_outer;
916  JoinCostWorkspace workspace;
917 
918  /*
919  * Check to see if proposed path is still parameterized, and reject if the
920  * parameterization wouldn't be sensible.
921  */
922  required_outer = calc_non_nestloop_required_outer(outer_path,
923  inner_path);
924  if (required_outer &&
925  !bms_overlap(required_outer, extra->param_source_rels))
926  {
927  /* Waste no memory when we reject a path here */
928  bms_free(required_outer);
929  return;
930  }
931 
932  /*
933  * See comments in try_nestloop_path(). Also note that hashjoin paths
934  * never have any output pathkeys, per comments in create_hashjoin_path.
935  */
936  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
937  outer_path, inner_path, extra, false);
938 
939  if (add_path_precheck(joinrel,
940  workspace.startup_cost, workspace.total_cost,
941  NIL, required_outer))
942  {
943  add_path(joinrel, (Path *)
945  joinrel,
946  jointype,
947  &workspace,
948  extra,
949  outer_path,
950  inner_path,
951  false, /* parallel_hash */
952  extra->restrictlist,
953  required_outer,
954  hashclauses));
955  }
956  else
957  {
958  /* Waste no memory when we reject a path here */
959  bms_free(required_outer);
960  }
961 }
#define NIL
Definition: pg_list.h:65
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:644
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2376
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:2563
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:3741
Relids param_source_rels
Definition: pathnodes.h:2523
void bms_free(Bitmapset *a)
Definition: bitmapset.c:208
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

753 {
754  Relids required_outer;
755  JoinCostWorkspace workspace;
756 
757  if (is_partial)
758  {
760  joinrel,
761  outer_path,
762  inner_path,
763  pathkeys,
764  mergeclauses,
765  outersortkeys,
766  innersortkeys,
767  jointype,
768  extra);
769  return;
770  }
771 
772  /*
773  * Check to see if proposed path is still parameterized, and reject if the
774  * parameterization wouldn't be sensible.
775  */
776  required_outer = calc_non_nestloop_required_outer(outer_path,
777  inner_path);
778  if (required_outer &&
779  !bms_overlap(required_outer, extra->param_source_rels))
780  {
781  /* Waste no memory when we reject a path here */
782  bms_free(required_outer);
783  return;
784  }
785 
786  /*
787  * If the given paths are already well enough ordered, we can skip doing
788  * an explicit sort.
789  */
790  if (outersortkeys &&
791  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
792  outersortkeys = NIL;
793  if (innersortkeys &&
794  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
795  innersortkeys = NIL;
796 
797  /*
798  * See comments in try_nestloop_path().
799  */
800  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
801  outer_path, inner_path,
802  outersortkeys, innersortkeys,
803  extra);
804 
805  if (add_path_precheck(joinrel,
806  workspace.startup_cost, workspace.total_cost,
807  pathkeys, required_outer))
808  {
809  add_path(joinrel, (Path *)
811  joinrel,
812  jointype,
813  &workspace,
814  extra,
815  outer_path,
816  inner_path,
817  extra->restrictlist,
818  pathkeys,
819  required_outer,
820  mergeclauses,
821  outersortkeys,
822  innersortkeys));
823  }
824  else
825  {
826  /* Waste no memory when we reject a path here */
827  bms_free(required_outer);
828  }
829 }
#define NIL
Definition: pg_list.h:65
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:644
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2376
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:2497
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:3183
Relids param_source_rels
Definition: pathnodes.h:2523
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1188
void bms_free(Bitmapset *a)
Definition: bitmapset.c:208
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
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:837

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

References add_path(), add_path_precheck(), allow_star_schema_join(), bms_free(), bms_overlap(), calc_nestloop_required_outer(), create_nestloop_path(), have_dangerous_phv(), initial_cost_nestloop(), JoinPathExtraData::param_source_rels, Path::parent, PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, reparameterize_path_by_child(), JoinPathExtraData::restrictlist, JoinCostWorkspace::startup_cost, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.

Referenced by match_unsorted_outer().

555 {
556  Relids required_outer;
557  JoinCostWorkspace workspace;
558  RelOptInfo *innerrel = inner_path->parent;
559  RelOptInfo *outerrel = outer_path->parent;
560  Relids innerrelids;
561  Relids outerrelids;
562  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
563  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
564 
565  /*
566  * Paths are parameterized by top-level parents, so run parameterization
567  * tests on the parent relids.
568  */
569  if (innerrel->top_parent_relids)
570  innerrelids = innerrel->top_parent_relids;
571  else
572  innerrelids = innerrel->relids;
573 
574  if (outerrel->top_parent_relids)
575  outerrelids = outerrel->top_parent_relids;
576  else
577  outerrelids = outerrel->relids;
578 
579  /*
580  * Check to see if proposed path is still parameterized, and reject if the
581  * parameterization wouldn't be sensible --- unless allow_star_schema_join
582  * says to allow it anyway. Also, we must reject if have_dangerous_phv
583  * doesn't like the look of it, which could only happen if the nestloop is
584  * still parameterized.
585  */
586  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
587  innerrelids, inner_paramrels);
588  if (required_outer &&
589  ((!bms_overlap(required_outer, extra->param_source_rels) &&
590  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
591  have_dangerous_phv(root, outerrelids, inner_paramrels)))
592  {
593  /* Waste no memory when we reject a path here */
594  bms_free(required_outer);
595  return;
596  }
597 
598  /*
599  * Do a precheck to quickly eliminate obviously-inferior paths. We
600  * calculate a cheap lower bound on the path's cost and then use
601  * add_path_precheck() to see if the path is clearly going to be dominated
602  * by some existing path for the joinrel. If not, do the full pushup with
603  * creating a fully valid path structure and submitting it to add_path().
604  * The latter two steps are expensive enough to make this two-phase
605  * methodology worthwhile.
606  */
607  initial_cost_nestloop(root, &workspace, jointype,
608  outer_path, inner_path, extra);
609 
610  if (add_path_precheck(joinrel,
611  workspace.startup_cost, workspace.total_cost,
612  pathkeys, required_outer))
613  {
614  /*
615  * If the inner path is parameterized, it is parameterized by the
616  * topmost parent of the outer rel, not the outer rel itself. Fix
617  * that.
618  */
619  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
620  {
621  inner_path = reparameterize_path_by_child(root, inner_path,
622  outer_path->parent);
623 
624  /*
625  * If we could not translate the path, we can't create nest loop
626  * path.
627  */
628  if (!inner_path)
629  {
630  bms_free(required_outer);
631  return;
632  }
633  }
634 
635  add_path(joinrel, (Path *)
637  joinrel,
638  jointype,
639  &workspace,
640  extra,
641  outer_path,
642  inner_path,
643  extra->restrictlist,
644  pathkeys,
645  required_outer));
646  }
647  else
648  {
649  /* Waste no memory when we reject a path here */
650  bms_free(required_outer);
651  }
652 }
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:644
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:36
Relids param_source_rels
Definition: pathnodes.h:2523
RelOptInfo * parent
Definition: pathnodes.h:1174
Path * reparameterize_path_by_child(PlannerInfo *root, Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:3958
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:2409
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1193
Relids relids
Definition: pathnodes.h:676
void bms_free(Bitmapset *a)
Definition: bitmapset.c:208
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2343
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2902
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:356
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1184
Relids top_parent_relids
Definition: pathnodes.h:751

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

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

Referenced by hash_inner_and_outer().

981 {
982  JoinCostWorkspace workspace;
983 
984  /*
985  * If the inner path is parameterized, the parameterization must be fully
986  * satisfied by the proposed outer path. Parameterized partial paths are
987  * not supported. The caller should already have verified that no lateral
988  * rels are required here.
989  */
991  if (inner_path->param_info != NULL)
992  {
993  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
994 
995  if (!bms_is_empty(inner_paramrels))
996  return;
997  }
998 
999  /*
1000  * Before creating a path, get a quick lower bound on what it is likely to
1001  * cost. Bail out right away if it looks terrible.
1002  */
1003  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1004  outer_path, inner_path, extra, parallel_hash);
1005  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
1006  return;
1007 
1008  /* Might be good enough to be worth trying, so let's try it. */
1009  add_partial_path(joinrel, (Path *)
1010  create_hashjoin_path(root,
1011  joinrel,
1012  jointype,
1013  &workspace,
1014  extra,
1015  outer_path,
1016  inner_path,
1017  parallel_hash,
1018  extra->restrictlist,
1019  NULL,
1020  hashclauses));
1021 }
#define NIL
Definition: pg_list.h:65
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:867
ParamPathInfo * param_info
Definition: pathnodes.h:1177
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:2563
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:3741
Relids lateral_relids
Definition: pathnodes.h:701
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:804
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
Relids ppi_req_outer
Definition: pathnodes.h:1133

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

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

Referenced by sort_inner_and_outer(), and try_mergejoin_path().

847 {
848  JoinCostWorkspace workspace;
849 
850  /*
851  * See comments in try_partial_hashjoin_path().
852  */
854  if (inner_path->param_info != NULL)
855  {
856  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
857 
858  if (!bms_is_empty(inner_paramrels))
859  return;
860  }
861 
862  /*
863  * If the given paths are already well enough ordered, we can skip doing
864  * an explicit sort.
865  */
866  if (outersortkeys &&
867  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
868  outersortkeys = NIL;
869  if (innersortkeys &&
870  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
871  innersortkeys = NIL;
872 
873  /*
874  * See comments in try_partial_nestloop_path().
875  */
876  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
877  outer_path, inner_path,
878  outersortkeys, innersortkeys,
879  extra);
880 
881  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
882  return;
883 
884  /* Might be good enough to be worth trying, so let's try it. */
885  add_partial_path(joinrel, (Path *)
887  joinrel,
888  jointype,
889  &workspace,
890  extra,
891  outer_path,
892  inner_path,
893  extra->restrictlist,
894  pathkeys,
895  NULL,
896  mergeclauses,
897  outersortkeys,
898  innersortkeys));
899 }
#define NIL
Definition: pg_list.h:65
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:867
ParamPathInfo * param_info
Definition: pathnodes.h:1177
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:2497
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:3183
Relids lateral_relids
Definition: pathnodes.h:701
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1188
#define Assert(condition)
Definition: c.h:804
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
Relids ppi_req_outer
Definition: pathnodes.h:1133

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

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

Referenced by consider_parallel_nestloop().

667 {
668  JoinCostWorkspace workspace;
669 
670  /*
671  * If the inner path is parameterized, the parameterization must be fully
672  * satisfied by the proposed outer path. Parameterized partial paths are
673  * not supported. The caller should already have verified that no lateral
674  * rels are required here.
675  */
677  if (inner_path->param_info != NULL)
678  {
679  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
680  RelOptInfo *outerrel = outer_path->parent;
681  Relids outerrelids;
682 
683  /*
684  * The inner and outer paths are parameterized, if at all, by the top
685  * level parents, not the child relations, so we must use those relids
686  * for our parameterization tests.
687  */
688  if (outerrel->top_parent_relids)
689  outerrelids = outerrel->top_parent_relids;
690  else
691  outerrelids = outerrel->relids;
692 
693  if (!bms_is_subset(inner_paramrels, outerrelids))
694  return;
695  }
696 
697  /*
698  * Before creating a path, get a quick lower bound on what it is likely to
699  * cost. Bail out right away if it looks terrible.
700  */
701  initial_cost_nestloop(root, &workspace, jointype,
702  outer_path, inner_path, extra);
703  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
704  return;
705 
706  /*
707  * If the inner path is parameterized, it is parameterized by the topmost
708  * parent of the outer rel, not the outer rel itself. Fix that.
709  */
710  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent))
711  {
712  inner_path = reparameterize_path_by_child(root, inner_path,
713  outer_path->parent);
714 
715  /*
716  * If we could not translate the path, we can't create nest loop path.
717  */
718  if (!inner_path)
719  return;
720  }
721 
722  /* Might be good enough to be worth trying, so let's try it. */
723  add_partial_path(joinrel, (Path *)
725  joinrel,
726  jointype,
727  &workspace,
728  extra,
729  outer_path,
730  inner_path,
731  extra->restrictlist,
732  pathkeys,
733  NULL));
734 }
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:867
ParamPathInfo * param_info
Definition: pathnodes.h:1177
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:36
Relids lateral_relids
Definition: pathnodes.h:701
RelOptInfo * parent
Definition: pathnodes.h:1174
Path * reparameterize_path_by_child(PlannerInfo *root, Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:3958
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
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:2409
Relids relids
Definition: pathnodes.h:676
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define Assert(condition)
Definition: c.h:804
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:2902
Relids ppi_req_outer
Definition: pathnodes.h:1133
Relids top_parent_relids
Definition: pathnodes.h:751

Variable Documentation

◆ set_join_pathlist_hook

set_join_pathlist_hook_type set_join_pathlist_hook = NULL

Definition at line 30 of file joinpath.c.

Referenced by add_paths_to_joinrel().