PostgreSQL Source Code  git master
joinpath.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * joinpath.c
4  * Routines to find all possible paths for processing a set of joins
5  *
6  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/path/joinpath.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include <math.h>
18 
19 #include "executor/executor.h"
20 #include "foreign/fdwapi.h"
21 #include "nodes/nodeFuncs.h"
22 #include "optimizer/cost.h"
23 #include "optimizer/optimizer.h"
24 #include "optimizer/pathnode.h"
25 #include "optimizer/paths.h"
26 #include "optimizer/planmain.h"
27 #include "utils/typcache.h"
28 
29 /* Hook for plugins to get control in add_paths_to_joinrel() */
30 set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
31 
32 /*
33  * Paths parameterized by a parent rel can be considered to be parameterized
34  * by any of its children, when we are performing partitionwise joins. These
35  * macros simplify checking for such cases. Beware multiple eval of args.
36  */
37 #define PATH_PARAM_BY_PARENT(path, rel) \
38  ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \
39  (rel)->top_parent_relids))
40 #define PATH_PARAM_BY_REL_SELF(path, rel) \
41  ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
42 
43 #define PATH_PARAM_BY_REL(path, rel) \
44  (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel))
45 
46 static void try_partial_mergejoin_path(PlannerInfo *root,
47  RelOptInfo *joinrel,
48  Path *outer_path,
49  Path *inner_path,
50  List *pathkeys,
51  List *mergeclauses,
52  List *outersortkeys,
53  List *innersortkeys,
54  JoinType jointype,
55  JoinPathExtraData *extra);
56 static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
57  RelOptInfo *outerrel, RelOptInfo *innerrel,
58  JoinType jointype, JoinPathExtraData *extra);
59 static inline bool clause_sides_match_join(RestrictInfo *rinfo,
60  RelOptInfo *outerrel,
61  RelOptInfo *innerrel);
62 static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,
63  RelOptInfo *outerrel, RelOptInfo *innerrel,
64  JoinType jointype, JoinPathExtraData *extra);
65 static void consider_parallel_nestloop(PlannerInfo *root,
66  RelOptInfo *joinrel,
67  RelOptInfo *outerrel,
68  RelOptInfo *innerrel,
69  JoinType jointype,
70  JoinPathExtraData *extra);
71 static void consider_parallel_mergejoin(PlannerInfo *root,
72  RelOptInfo *joinrel,
73  RelOptInfo *outerrel,
74  RelOptInfo *innerrel,
75  JoinType jointype,
76  JoinPathExtraData *extra,
77  Path *inner_cheapest_total);
78 static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
79  RelOptInfo *outerrel, RelOptInfo *innerrel,
80  JoinType jointype, JoinPathExtraData *extra);
81 static List *select_mergejoin_clauses(PlannerInfo *root,
82  RelOptInfo *joinrel,
83  RelOptInfo *outerrel,
84  RelOptInfo *innerrel,
85  List *restrictlist,
86  JoinType jointype,
87  bool *mergejoin_allowed);
88 static void generate_mergejoin_paths(PlannerInfo *root,
89  RelOptInfo *joinrel,
90  RelOptInfo *innerrel,
91  Path *outerpath,
92  JoinType jointype,
93  JoinPathExtraData *extra,
94  bool useallclauses,
95  Path *inner_cheapest_total,
96  List *merge_pathkeys,
97  bool is_partial);
98 
99 
100 /*
101  * add_paths_to_joinrel
102  * Given a join relation and two component rels from which it can be made,
103  * consider all possible paths that use the two component rels as outer
104  * and inner rel respectively. Add these paths to the join rel's pathlist
105  * if they survive comparison with other paths (and remove any existing
106  * paths that are dominated by these paths).
107  *
108  * Modifies the pathlist field of the joinrel node to contain the best
109  * paths found so far.
110  *
111  * jointype is not necessarily the same as sjinfo->jointype; it might be
112  * "flipped around" if we are considering joining the rels in the opposite
113  * direction from what's indicated in sjinfo.
114  *
115  * Also, this routine and others in this module accept the special JoinTypes
116  * JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should
117  * unique-ify the outer or inner relation and then apply a regular inner
118  * join. These values are not allowed to propagate outside this module,
119  * however. Path cost estimation code may need to recognize that it's
120  * dealing with such a case --- the combination of nominal jointype INNER
121  * with sjinfo->jointype == JOIN_SEMI indicates that.
122  */
123 void
124 add_paths_to_joinrel(PlannerInfo *root,
125  RelOptInfo *joinrel,
126  RelOptInfo *outerrel,
127  RelOptInfo *innerrel,
128  JoinType jointype,
129  SpecialJoinInfo *sjinfo,
130  List *restrictlist)
131 {
132  JoinPathExtraData extra;
133  bool mergejoin_allowed = true;
134  ListCell *lc;
135  Relids joinrelids;
136 
137  /*
138  * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
139  * between child relations, even if there is a SpecialJoinInfo node for
140  * the join between the topmost parents. So, while calculating Relids set
141  * representing the restriction, consider relids of topmost parent of
142  * partitions.
143  */
144  if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
145  joinrelids = joinrel->top_parent_relids;
146  else
147  joinrelids = joinrel->relids;
148 
149  extra.restrictlist = restrictlist;
150  extra.mergeclause_list = NIL;
151  extra.sjinfo = sjinfo;
152  extra.param_source_rels = NULL;
153 
154  /*
155  * See if the inner relation is provably unique for this outer rel.
156  *
157  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
158  * matter since the executor can make the equivalent optimization anyway;
159  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
160  * must be considering a semijoin whose inner side is not provably unique
161  * (else reduce_unique_semijoins would've simplified it), so there's no
162  * point in calling innerrel_is_unique. However, if the LHS covers all of
163  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
164  * because the path produced by create_unique_path will be unique relative
165  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
166  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
167  * letting that value escape this module.
168  */
169  switch (jointype)
170  {
171  case JOIN_SEMI:
172  case JOIN_ANTI:
173 
174  /*
175  * XXX it may be worth proving this to allow a Memoize to be
176  * considered for Nested Loop Semi/Anti Joins.
177  */
178  extra.inner_unique = false; /* well, unproven */
179  break;
180  case JOIN_UNIQUE_INNER:
181  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
182  outerrel->relids);
183  break;
184  case JOIN_UNIQUE_OUTER:
185  extra.inner_unique = innerrel_is_unique(root,
186  joinrel->relids,
187  outerrel->relids,
188  innerrel,
189  JOIN_INNER,
190  restrictlist,
191  false);
192  break;
193  default:
194  extra.inner_unique = innerrel_is_unique(root,
195  joinrel->relids,
196  outerrel->relids,
197  innerrel,
198  jointype,
199  restrictlist,
200  false);
201  break;
202  }
203 
204  /*
205  * Find potential mergejoin clauses. We can skip this if we are not
206  * interested in doing a mergejoin. However, mergejoin may be our only
207  * way of implementing a full outer join, so override enable_mergejoin if
208  * it's a full join.
209  */
210  if (enable_mergejoin || jointype == JOIN_FULL)
211  extra.mergeclause_list = select_mergejoin_clauses(root,
212  joinrel,
213  outerrel,
214  innerrel,
215  restrictlist,
216  jointype,
217  &mergejoin_allowed);
218 
219  /*
220  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
221  * for cost estimation. These will be the same for all paths.
222  */
223  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
224  compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
225  jointype, sjinfo, restrictlist,
226  &extra.semifactors);
227 
228  /*
229  * Decide whether it's sensible to generate parameterized paths for this
230  * joinrel, and if so, which relations such paths should require. There
231  * is usually no need to create a parameterized result path unless there
232  * is a join order restriction that prevents joining one of our input rels
233  * directly to the parameter source rel instead of joining to the other
234  * input rel. (But see allow_star_schema_join().) This restriction
235  * reduces the number of parameterized paths we have to deal with at
236  * higher join levels, without compromising the quality of the resulting
237  * plan. We express the restriction as a Relids set that must overlap the
238  * parameterization of any proposed join path. Note: param_source_rels
239  * should contain only baserels, not OJ relids, so starting from
240  * all_baserels not all_query_rels is correct.
241  */
242  foreach(lc, root->join_info_list)
243  {
244  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
245 
246  /*
247  * SJ is relevant to this join if we have some part of its RHS
248  * (possibly not all of it), and haven't yet joined to its LHS. (This
249  * test is pretty simplistic, but should be sufficient considering the
250  * join has already been proven legal.) If the SJ is relevant, it
251  * presents constraints for joining to anything not in its RHS.
252  */
253  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
254  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
255  extra.param_source_rels = bms_join(extra.param_source_rels,
256  bms_difference(root->all_baserels,
257  sjinfo2->min_righthand));
258 
259  /* full joins constrain both sides symmetrically */
260  if (sjinfo2->jointype == JOIN_FULL &&
261  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
262  !bms_overlap(joinrelids, sjinfo2->min_righthand))
263  extra.param_source_rels = bms_join(extra.param_source_rels,
264  bms_difference(root->all_baserels,
265  sjinfo2->min_lefthand));
266  }
267 
268  /*
269  * However, when a LATERAL subquery is involved, there will simply not be
270  * any paths for the joinrel that aren't parameterized by whatever the
271  * subquery is parameterized by, unless its parameterization is resolved
272  * within the joinrel. So we might as well allow additional dependencies
273  * on whatever residual lateral dependencies the joinrel will have.
274  */
275  extra.param_source_rels = bms_add_members(extra.param_source_rels,
276  joinrel->lateral_relids);
277 
278  /*
279  * 1. Consider mergejoin paths where both relations must be explicitly
280  * sorted. Skip this if we can't mergejoin.
281  */
282  if (mergejoin_allowed)
283  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
284  jointype, &extra);
285 
286  /*
287  * 2. Consider paths where the outer relation need not be explicitly
288  * sorted. This includes both nestloops and mergejoins where the outer
289  * path is already ordered. Again, skip this if we can't mergejoin.
290  * (That's okay because we know that nestloop can't handle
291  * right/right-anti/full joins at all, so it wouldn't work in the
292  * prohibited cases either.)
293  */
294  if (mergejoin_allowed)
295  match_unsorted_outer(root, joinrel, outerrel, innerrel,
296  jointype, &extra);
297 
298 #ifdef NOT_USED
299 
300  /*
301  * 3. Consider paths where the inner relation need not be explicitly
302  * sorted. This includes mergejoins only (nestloops were already built in
303  * match_unsorted_outer).
304  *
305  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
306  * significant difference between the inner and outer side of a mergejoin,
307  * so match_unsorted_inner creates no paths that aren't equivalent to
308  * those made by match_unsorted_outer when add_paths_to_joinrel() is
309  * invoked with the two rels given in the other order.
310  */
311  if (mergejoin_allowed)
312  match_unsorted_inner(root, joinrel, outerrel, innerrel,
313  jointype, &extra);
314 #endif
315 
316  /*
317  * 4. Consider paths where both outer and inner relations must be hashed
318  * before being joined. As above, disregard enable_hashjoin for full
319  * joins, because there may be no other alternative.
320  */
321  if (enable_hashjoin || jointype == JOIN_FULL)
322  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
323  jointype, &extra);
324 
325  /*
326  * 5. If inner and outer relations are foreign tables (or joins) belonging
327  * to the same server and assigned to the same user to check access
328  * permissions as, give the FDW a chance to push down joins.
329  */
330  if (joinrel->fdwroutine &&
331  joinrel->fdwroutine->GetForeignJoinPaths)
332  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
333  outerrel, innerrel,
334  jointype, &extra);
335 
336  /*
337  * 6. Finally, give extensions a chance to manipulate the path list. They
338  * could add new paths (such as CustomPaths) by calling add_path(), or
339  * add_partial_path() if parallel aware. They could also delete or modify
340  * paths added by the core code.
341  */
342  if (set_join_pathlist_hook)
343  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
344  jointype, &extra);
345 }
346 
347 /*
348  * We override the param_source_rels heuristic to accept nestloop paths in
349  * which the outer rel satisfies some but not all of the inner path's
350  * parameterization. This is necessary to get good plans for star-schema
351  * scenarios, in which a parameterized path for a large table may require
352  * parameters from multiple small tables that will not get joined directly to
353  * each other. We can handle that by stacking nestloops that have the small
354  * tables on the outside; but this breaks the rule the param_source_rels
355  * heuristic is based on, namely that parameters should not be passed down
356  * across joins unless there's a join-order-constraint-based reason to do so.
357  * So we ignore the param_source_rels restriction when this case applies.
358  *
359  * allow_star_schema_join() returns true if the param_source_rels restriction
360  * should be overridden, ie, it's okay to perform this join.
361  */
362 static inline bool
363 allow_star_schema_join(PlannerInfo *root,
364  Relids outerrelids,
365  Relids inner_paramrels)
366 {
367  /*
368  * It's a star-schema case if the outer rel provides some but not all of
369  * the inner rel's parameterization.
370  */
371  return (bms_overlap(inner_paramrels, outerrelids) &&
372  bms_nonempty_difference(inner_paramrels, outerrelids));
373 }
374 
375 /*
376  * If the parameterization is only partly satisfied by the outer rel,
377  * the unsatisfied part can't include any outer-join relids that could
378  * null rels of the satisfied part. That would imply that we're trying
379  * to use a clause involving a Var with nonempty varnullingrels at
380  * a join level where that value isn't yet computable.
381  *
382  * In practice, this test never finds a problem because earlier join order
383  * restrictions prevent us from attempting a join that would cause a problem.
384  * (That's unsurprising, because the code worked before we ever added
385  * outer-join relids to expression relids.) It still seems worth checking
386  * as a backstop, but we only do so in assert-enabled builds.
387  */
388 #ifdef USE_ASSERT_CHECKING
389 static inline bool
390 have_unsafe_outer_join_ref(PlannerInfo *root,
391  Relids outerrelids,
392  Relids inner_paramrels)
393 {
394  bool result = false;
395  Relids unsatisfied = bms_difference(inner_paramrels, outerrelids);
396  Relids satisfied = bms_intersect(inner_paramrels, outerrelids);
397 
398  if (bms_overlap(unsatisfied, root->outer_join_rels))
399  {
400  ListCell *lc;
401 
402  foreach(lc, root->join_info_list)
403  {
404  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
405 
406  if (!bms_is_member(sjinfo->ojrelid, unsatisfied))
407  continue; /* not relevant */
408  if (bms_overlap(satisfied, sjinfo->min_righthand) ||
409  (sjinfo->jointype == JOIN_FULL &&
410  bms_overlap(satisfied, sjinfo->min_lefthand)))
411  {
412  result = true; /* doesn't work */
413  break;
414  }
415  }
416  }
417 
418  /* Waste no memory when we reject a path here */
419  bms_free(unsatisfied);
420  bms_free(satisfied);
421 
422  return result;
423 }
424 #endif /* USE_ASSERT_CHECKING */
425 
426 /*
427  * paraminfo_get_equal_hashops
428  * Determine if the clauses in param_info and innerrel's lateral_vars
429  * can be hashed.
430  * Returns true if hashing is possible, otherwise false.
431  *
432  * Additionally, on success we collect the outer expressions and the
433  * appropriate equality operators for each hashable parameter to innerrel.
434  * These are returned in parallel lists in *param_exprs and *operators.
435  * We also set *binary_mode to indicate whether strict binary matching is
436  * required.
437  */
438 static bool
439 paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info,
440  RelOptInfo *outerrel, RelOptInfo *innerrel,
441  List **param_exprs, List **operators,
442  bool *binary_mode)
443 
444 {
445  ListCell *lc;
446 
447  *param_exprs = NIL;
448  *operators = NIL;
449  *binary_mode = false;
450 
451  /* Add join clauses from param_info to the hash key */
452  if (param_info != NULL)
453  {
454  List *clauses = param_info->ppi_clauses;
455 
456  foreach(lc, clauses)
457  {
458  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
459  OpExpr *opexpr;
460  Node *expr;
461  Oid hasheqoperator;
462 
463  opexpr = (OpExpr *) rinfo->clause;
464 
465  /*
466  * Bail if the rinfo is not compatible. We need a join OpExpr
467  * with 2 args.
468  */
469  if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 ||
470  !clause_sides_match_join(rinfo, outerrel, innerrel))
471  {
472  list_free(*operators);
473  list_free(*param_exprs);
474  return false;
475  }
476 
477  if (rinfo->outer_is_left)
478  {
479  expr = (Node *) linitial(opexpr->args);
480  hasheqoperator = rinfo->left_hasheqoperator;
481  }
482  else
483  {
484  expr = (Node *) lsecond(opexpr->args);
485  hasheqoperator = rinfo->right_hasheqoperator;
486  }
487 
488  /* can't do memoize if we can't hash the outer type */
489  if (!OidIsValid(hasheqoperator))
490  {
491  list_free(*operators);
492  list_free(*param_exprs);
493  return false;
494  }
495 
496  /*
497  * 'expr' may already exist as a parameter from a previous item in
498  * ppi_clauses. No need to include it again, however we'd better
499  * ensure we do switch into binary mode if required. See below.
500  */
501  if (!list_member(*param_exprs, expr))
502  {
503  *operators = lappend_oid(*operators, hasheqoperator);
504  *param_exprs = lappend(*param_exprs, expr);
505  }
506 
507  /*
508  * When the join operator is not hashable then it's possible that
509  * the operator will be able to distinguish something that the
510  * hash equality operator could not. For example with floating
511  * point types -0.0 and +0.0 are classed as equal by the hash
512  * function and equality function, but some other operator may be
513  * able to tell those values apart. This means that we must put
514  * memoize into binary comparison mode so that it does bit-by-bit
515  * comparisons rather than a "logical" comparison as it would
516  * using the hash equality operator.
517  */
518  if (!OidIsValid(rinfo->hashjoinoperator))
519  *binary_mode = true;
520  }
521  }
522 
523  /* Now add any lateral vars to the cache key too */
524  foreach(lc, innerrel->lateral_vars)
525  {
526  Node *expr = (Node *) lfirst(lc);
527  TypeCacheEntry *typentry;
528 
529  /* Reject if there are any volatile functions in lateral vars */
530  if (contain_volatile_functions(expr))
531  {
532  list_free(*operators);
533  list_free(*param_exprs);
534  return false;
535  }
536 
537  typentry = lookup_type_cache(exprType(expr),
538  TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR);
539 
540  /* can't use memoize without a valid hash proc and equals operator */
541  if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
542  {
543  list_free(*operators);
544  list_free(*param_exprs);
545  return false;
546  }
547 
548  /*
549  * 'expr' may already exist as a parameter from the ppi_clauses. No
550  * need to include it again, however we'd better ensure we do switch
551  * into binary mode.
552  */
553  if (!list_member(*param_exprs, expr))
554  {
555  *operators = lappend_oid(*operators, typentry->eq_opr);
556  *param_exprs = lappend(*param_exprs, expr);
557  }
558 
559  /*
560  * We must go into binary mode as we don't have too much of an idea of
561  * how these lateral Vars are being used. See comment above when we
562  * set *binary_mode for the non-lateral Var case. This could be
563  * relaxed a bit if we had the RestrictInfos and knew the operators
564  * being used, however for cases like Vars that are arguments to
565  * functions we must operate in binary mode as we don't have
566  * visibility into what the function is doing with the Vars.
567  */
568  *binary_mode = true;
569  }
570 
571  /* We're okay to use memoize */
572  return true;
573 }
574 
575 /*
576  * get_memoize_path
577  * If possible, make and return a Memoize path atop of 'inner_path'.
578  * Otherwise return NULL.
579  */
580 static Path *
581 get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
582  RelOptInfo *outerrel, Path *inner_path,
583  Path *outer_path, JoinType jointype,
584  JoinPathExtraData *extra)
585 {
586  List *param_exprs;
587  List *hash_operators;
588  ListCell *lc;
589  bool binary_mode;
590 
591  /* Obviously not if it's disabled */
592  if (!enable_memoize)
593  return NULL;
594 
595  /*
596  * We can safely not bother with all this unless we expect to perform more
597  * than one inner scan. The first scan is always going to be a cache
598  * miss. This would likely fail later anyway based on costs, so this is
599  * really just to save some wasted effort.
600  */
601  if (outer_path->parent->rows < 2)
602  return NULL;
603 
604  /*
605  * We can only have a memoize node when there's some kind of cache key,
606  * either parameterized path clauses or lateral Vars. No cache key sounds
607  * more like something a Materialize node might be more useful for.
608  */
609  if ((inner_path->param_info == NULL ||
610  inner_path->param_info->ppi_clauses == NIL) &&
611  innerrel->lateral_vars == NIL)
612  return NULL;
613 
614  /*
615  * Currently we don't do this for SEMI and ANTI joins unless they're
616  * marked as inner_unique. This is because nested loop SEMI/ANTI joins
617  * don't scan the inner node to completion, which will mean memoize cannot
618  * mark the cache entry as complete.
619  *
620  * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
621  * = true. Should we? See add_paths_to_joinrel()
622  */
623  if (!extra->inner_unique && (jointype == JOIN_SEMI ||
624  jointype == JOIN_ANTI))
625  return NULL;
626 
627  /*
628  * Memoize normally marks cache entries as complete when it runs out of
629  * tuples to read from its subplan. However, with unique joins, Nested
630  * Loop will skip to the next outer tuple after finding the first matching
631  * inner tuple. This means that we may not read the inner side of the
632  * join to completion which leaves no opportunity to mark the cache entry
633  * as complete. To work around that, when the join is unique we
634  * automatically mark cache entries as complete after fetching the first
635  * tuple. This works when the entire join condition is parameterized.
636  * Otherwise, when the parameterization is only a subset of the join
637  * condition, we can't be sure which part of it causes the join to be
638  * unique. This means there are no guarantees that only 1 tuple will be
639  * read. We cannot mark the cache entry as complete after reading the
640  * first tuple without that guarantee. This means the scope of Memoize
641  * node's usefulness is limited to only outer rows that have no join
642  * partner as this is the only case where Nested Loop would exhaust the
643  * inner scan of a unique join. Since the scope is limited to that, we
644  * just don't bother making a memoize path in this case.
645  *
646  * Lateral vars needn't be considered here as they're not considered when
647  * determining if the join is unique.
648  *
649  * XXX this could be enabled if the remaining join quals were made part of
650  * the inner scan's filter instead of the join filter. Maybe it's worth
651  * considering doing that?
652  */
653  if (extra->inner_unique &&
654  (inner_path->param_info == NULL ||
655  bms_num_members(inner_path->param_info->ppi_serials) <
656  list_length(extra->restrictlist)))
657  return NULL;
658 
659  /*
660  * We can't use a memoize node if there are volatile functions in the
661  * inner rel's target list or restrict list. A cache hit could reduce the
662  * number of calls to these functions.
663  */
664  if (contain_volatile_functions((Node *) innerrel->reltarget))
665  return NULL;
666 
667  foreach(lc, innerrel->baserestrictinfo)
668  {
669  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
670 
671  if (contain_volatile_functions((Node *) rinfo))
672  return NULL;
673  }
674 
675  /*
676  * Also check the parameterized path restrictinfos for volatile functions.
677  * Indexed functions must be immutable so shouldn't have any volatile
678  * functions, however, with a lateral join the inner scan may not be an
679  * index scan.
680  */
681  if (inner_path->param_info != NULL)
682  {
683  foreach(lc, inner_path->param_info->ppi_clauses)
684  {
685  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
686 
687  if (contain_volatile_functions((Node *) rinfo))
688  return NULL;
689  }
690  }
691 
692  /* Check if we have hash ops for each parameter to the path */
693  if (paraminfo_get_equal_hashops(root,
694  inner_path->param_info,
695  outerrel->top_parent ?
696  outerrel->top_parent : outerrel,
697  innerrel,
698  &param_exprs,
699  &hash_operators,
700  &binary_mode))
701  {
702  return (Path *) create_memoize_path(root,
703  innerrel,
704  inner_path,
705  param_exprs,
706  hash_operators,
707  extra->inner_unique,
708  binary_mode,
709  outer_path->rows);
710  }
711 
712  return NULL;
713 }
714 
715 /*
716  * try_nestloop_path
717  * Consider a nestloop join path; if it appears useful, push it into
718  * the joinrel's pathlist via add_path().
719  */
720 static void
721 try_nestloop_path(PlannerInfo *root,
722  RelOptInfo *joinrel,
723  Path *outer_path,
724  Path *inner_path,
725  List *pathkeys,
726  JoinType jointype,
727  JoinPathExtraData *extra)
728 {
729  Relids required_outer;
730  JoinCostWorkspace workspace;
731  RelOptInfo *innerrel = inner_path->parent;
732  RelOptInfo *outerrel = outer_path->parent;
733  Relids innerrelids;
734  Relids outerrelids;
735  Relids inner_paramrels = PATH_REQ_OUTER(inner_path);
736  Relids outer_paramrels = PATH_REQ_OUTER(outer_path);
737 
738  /*
739  * If we are forming an outer join at this join, it's nonsensical to use
740  * an input path that uses the outer join as part of its parameterization.
741  * (This can happen despite our join order restrictions, since those apply
742  * to what is in an input relation not what its parameters are.)
743  */
744  if (extra->sjinfo->ojrelid != 0 &&
745  (bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) ||
746  bms_is_member(extra->sjinfo->ojrelid, outer_paramrels)))
747  return;
748 
749  /*
750  * Any parameterization of the input paths refers to topmost parents of
751  * the relevant relations, because reparameterize_path_by_child() hasn't
752  * been called yet. So we must consider topmost parents of the relations
753  * being joined, too, while determining parameterization of the result and
754  * checking for disallowed parameterization cases.
755  */
756  if (innerrel->top_parent_relids)
757  innerrelids = innerrel->top_parent_relids;
758  else
759  innerrelids = innerrel->relids;
760 
761  if (outerrel->top_parent_relids)
762  outerrelids = outerrel->top_parent_relids;
763  else
764  outerrelids = outerrel->relids;
765 
766  /*
767  * Check to see if proposed path is still parameterized, and reject if the
768  * parameterization wouldn't be sensible --- unless allow_star_schema_join
769  * says to allow it anyway. Also, we must reject if have_dangerous_phv
770  * doesn't like the look of it, which could only happen if the nestloop is
771  * still parameterized.
772  */
773  required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels,
774  innerrelids, inner_paramrels);
775  if (required_outer &&
776  ((!bms_overlap(required_outer, extra->param_source_rels) &&
777  !allow_star_schema_join(root, outerrelids, inner_paramrels)) ||
778  have_dangerous_phv(root, outerrelids, inner_paramrels)))
779  {
780  /* Waste no memory when we reject a path here */
781  bms_free(required_outer);
782  return;
783  }
784 
785  /* If we got past that, we shouldn't have any unsafe outer-join refs */
786  Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels));
787 
788  /*
789  * If the inner path is parameterized, it is parameterized by the topmost
790  * parent of the outer rel, not the outer rel itself. We will need to
791  * translate the parameterization, if this path is chosen, during
792  * create_plan(). Here we just check whether we will be able to perform
793  * the translation, and if not avoid creating a nestloop path.
794  */
795  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
796  !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
797  {
798  bms_free(required_outer);
799  return;
800  }
801 
802  /*
803  * Do a precheck to quickly eliminate obviously-inferior paths. We
804  * calculate a cheap lower bound on the path's cost and then use
805  * add_path_precheck() to see if the path is clearly going to be dominated
806  * by some existing path for the joinrel. If not, do the full pushup with
807  * creating a fully valid path structure and submitting it to add_path().
808  * The latter two steps are expensive enough to make this two-phase
809  * methodology worthwhile.
810  */
811  initial_cost_nestloop(root, &workspace, jointype,
812  outer_path, inner_path, extra);
813 
814  if (add_path_precheck(joinrel,
815  workspace.startup_cost, workspace.total_cost,
816  pathkeys, required_outer))
817  {
818  add_path(joinrel, (Path *)
819  create_nestloop_path(root,
820  joinrel,
821  jointype,
822  &workspace,
823  extra,
824  outer_path,
825  inner_path,
826  extra->restrictlist,
827  pathkeys,
828  required_outer));
829  }
830  else
831  {
832  /* Waste no memory when we reject a path here */
833  bms_free(required_outer);
834  }
835 }
836 
837 /*
838  * try_partial_nestloop_path
839  * Consider a partial nestloop join path; if it appears useful, push it into
840  * the joinrel's partial_pathlist via add_partial_path().
841  */
842 static void
843 try_partial_nestloop_path(PlannerInfo *root,
844  RelOptInfo *joinrel,
845  Path *outer_path,
846  Path *inner_path,
847  List *pathkeys,
848  JoinType jointype,
849  JoinPathExtraData *extra)
850 {
851  JoinCostWorkspace workspace;
852 
853  /*
854  * If the inner path is parameterized, the parameterization must be fully
855  * satisfied by the proposed outer path. Parameterized partial paths are
856  * not supported. The caller should already have verified that no lateral
857  * rels are required here.
858  */
859  Assert(bms_is_empty(joinrel->lateral_relids));
860  if (inner_path->param_info != NULL)
861  {
862  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
863  RelOptInfo *outerrel = outer_path->parent;
864  Relids outerrelids;
865 
866  /*
867  * The inner and outer paths are parameterized, if at all, by the top
868  * level parents, not the child relations, so we must use those relids
869  * for our parameterization tests.
870  */
871  if (outerrel->top_parent_relids)
872  outerrelids = outerrel->top_parent_relids;
873  else
874  outerrelids = outerrel->relids;
875 
876  if (!bms_is_subset(inner_paramrels, outerrelids))
877  return;
878  }
879 
880  /*
881  * If the inner path is parameterized, it is parameterized by the topmost
882  * parent of the outer rel, not the outer rel itself. We will need to
883  * translate the parameterization, if this path is chosen, during
884  * create_plan(). Here we just check whether we will be able to perform
885  * the translation, and if not avoid creating a nestloop path.
886  */
887  if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) &&
888  !path_is_reparameterizable_by_child(inner_path, outer_path->parent))
889  return;
890 
891  /*
892  * Before creating a path, get a quick lower bound on what it is likely to
893  * cost. Bail out right away if it looks terrible.
894  */
895  initial_cost_nestloop(root, &workspace, jointype,
896  outer_path, inner_path, extra);
897  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
898  return;
899 
900  /* Might be good enough to be worth trying, so let's try it. */
901  add_partial_path(joinrel, (Path *)
902  create_nestloop_path(root,
903  joinrel,
904  jointype,
905  &workspace,
906  extra,
907  outer_path,
908  inner_path,
909  extra->restrictlist,
910  pathkeys,
911  NULL));
912 }
913 
914 /*
915  * try_mergejoin_path
916  * Consider a merge join path; if it appears useful, push it into
917  * the joinrel's pathlist via add_path().
918  */
919 static void
920 try_mergejoin_path(PlannerInfo *root,
921  RelOptInfo *joinrel,
922  Path *outer_path,
923  Path *inner_path,
924  List *pathkeys,
925  List *mergeclauses,
926  List *outersortkeys,
927  List *innersortkeys,
928  JoinType jointype,
929  JoinPathExtraData *extra,
930  bool is_partial)
931 {
932  Relids required_outer;
933  JoinCostWorkspace workspace;
934 
935  if (is_partial)
936  {
937  try_partial_mergejoin_path(root,
938  joinrel,
939  outer_path,
940  inner_path,
941  pathkeys,
942  mergeclauses,
943  outersortkeys,
944  innersortkeys,
945  jointype,
946  extra);
947  return;
948  }
949 
950  /*
951  * If we are forming an outer join at this join, it's nonsensical to use
952  * an input path that uses the outer join as part of its parameterization.
953  * (This can happen despite our join order restrictions, since those apply
954  * to what is in an input relation not what its parameters are.)
955  */
956  if (extra->sjinfo->ojrelid != 0 &&
957  (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
958  bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
959  return;
960 
961  /*
962  * Check to see if proposed path is still parameterized, and reject if the
963  * parameterization wouldn't be sensible.
964  */
965  required_outer = calc_non_nestloop_required_outer(outer_path,
966  inner_path);
967  if (required_outer &&
968  !bms_overlap(required_outer, extra->param_source_rels))
969  {
970  /* Waste no memory when we reject a path here */
971  bms_free(required_outer);
972  return;
973  }
974 
975  /*
976  * If the given paths are already well enough ordered, we can skip doing
977  * an explicit sort.
978  */
979  if (outersortkeys &&
980  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
981  outersortkeys = NIL;
982  if (innersortkeys &&
983  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
984  innersortkeys = NIL;
985 
986  /*
987  * See comments in try_nestloop_path().
988  */
989  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
990  outer_path, inner_path,
991  outersortkeys, innersortkeys,
992  extra);
993 
994  if (add_path_precheck(joinrel,
995  workspace.startup_cost, workspace.total_cost,
996  pathkeys, required_outer))
997  {
998  add_path(joinrel, (Path *)
999  create_mergejoin_path(root,
1000  joinrel,
1001  jointype,
1002  &workspace,
1003  extra,
1004  outer_path,
1005  inner_path,
1006  extra->restrictlist,
1007  pathkeys,
1008  required_outer,
1009  mergeclauses,
1010  outersortkeys,
1011  innersortkeys));
1012  }
1013  else
1014  {
1015  /* Waste no memory when we reject a path here */
1016  bms_free(required_outer);
1017  }
1018 }
1019 
1020 /*
1021  * try_partial_mergejoin_path
1022  * Consider a partial merge join path; if it appears useful, push it into
1023  * the joinrel's pathlist via add_partial_path().
1024  */
1025 static void
1026 try_partial_mergejoin_path(PlannerInfo *root,
1027  RelOptInfo *joinrel,
1028  Path *outer_path,
1029  Path *inner_path,
1030  List *pathkeys,
1031  List *mergeclauses,
1032  List *outersortkeys,
1033  List *innersortkeys,
1034  JoinType jointype,
1035  JoinPathExtraData *extra)
1036 {
1037  JoinCostWorkspace workspace;
1038 
1039  /*
1040  * See comments in try_partial_hashjoin_path().
1041  */
1042  Assert(bms_is_empty(joinrel->lateral_relids));
1043  if (inner_path->param_info != NULL)
1044  {
1045  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1046 
1047  if (!bms_is_empty(inner_paramrels))
1048  return;
1049  }
1050 
1051  /*
1052  * If the given paths are already well enough ordered, we can skip doing
1053  * an explicit sort.
1054  */
1055  if (outersortkeys &&
1056  pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1057  outersortkeys = NIL;
1058  if (innersortkeys &&
1059  pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1060  innersortkeys = NIL;
1061 
1062  /*
1063  * See comments in try_partial_nestloop_path().
1064  */
1065  initial_cost_mergejoin(root, &workspace, jointype, mergeclauses,
1066  outer_path, inner_path,
1067  outersortkeys, innersortkeys,
1068  extra);
1069 
1070  if (!add_partial_path_precheck(joinrel, workspace.total_cost, pathkeys))
1071  return;
1072 
1073  /* Might be good enough to be worth trying, so let's try it. */
1074  add_partial_path(joinrel, (Path *)
1075  create_mergejoin_path(root,
1076  joinrel,
1077  jointype,
1078  &workspace,
1079  extra,
1080  outer_path,
1081  inner_path,
1082  extra->restrictlist,
1083  pathkeys,
1084  NULL,
1085  mergeclauses,
1086  outersortkeys,
1087  innersortkeys));
1088 }
1089 
1090 /*
1091  * try_hashjoin_path
1092  * Consider a hash join path; if it appears useful, push it into
1093  * the joinrel's pathlist via add_path().
1094  */
1095 static void
1096 try_hashjoin_path(PlannerInfo *root,
1097  RelOptInfo *joinrel,
1098  Path *outer_path,
1099  Path *inner_path,
1100  List *hashclauses,
1101  JoinType jointype,
1102  JoinPathExtraData *extra)
1103 {
1104  Relids required_outer;
1105  JoinCostWorkspace workspace;
1106 
1107  /*
1108  * If we are forming an outer join at this join, it's nonsensical to use
1109  * an input path that uses the outer join as part of its parameterization.
1110  * (This can happen despite our join order restrictions, since those apply
1111  * to what is in an input relation not what its parameters are.)
1112  */
1113  if (extra->sjinfo->ojrelid != 0 &&
1114  (bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) ||
1115  bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path))))
1116  return;
1117 
1118  /*
1119  * Check to see if proposed path is still parameterized, and reject if the
1120  * parameterization wouldn't be sensible.
1121  */
1122  required_outer = calc_non_nestloop_required_outer(outer_path,
1123  inner_path);
1124  if (required_outer &&
1125  !bms_overlap(required_outer, extra->param_source_rels))
1126  {
1127  /* Waste no memory when we reject a path here */
1128  bms_free(required_outer);
1129  return;
1130  }
1131 
1132  /*
1133  * See comments in try_nestloop_path(). Also note that hashjoin paths
1134  * never have any output pathkeys, per comments in create_hashjoin_path.
1135  */
1136  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1137  outer_path, inner_path, extra, false);
1138 
1139  if (add_path_precheck(joinrel,
1140  workspace.startup_cost, workspace.total_cost,
1141  NIL, required_outer))
1142  {
1143  add_path(joinrel, (Path *)
1144  create_hashjoin_path(root,
1145  joinrel,
1146  jointype,
1147  &workspace,
1148  extra,
1149  outer_path,
1150  inner_path,
1151  false, /* parallel_hash */
1152  extra->restrictlist,
1153  required_outer,
1154  hashclauses));
1155  }
1156  else
1157  {
1158  /* Waste no memory when we reject a path here */
1159  bms_free(required_outer);
1160  }
1161 }
1162 
1163 /*
1164  * try_partial_hashjoin_path
1165  * Consider a partial hashjoin join path; if it appears useful, push it into
1166  * the joinrel's partial_pathlist via add_partial_path().
1167  * The outer side is partial. If parallel_hash is true, then the inner path
1168  * must be partial and will be run in parallel to create one or more shared
1169  * hash tables; otherwise the inner path must be complete and a copy of it
1170  * is run in every process to create separate identical private hash tables.
1171  */
1172 static void
1173 try_partial_hashjoin_path(PlannerInfo *root,
1174  RelOptInfo *joinrel,
1175  Path *outer_path,
1176  Path *inner_path,
1177  List *hashclauses,
1178  JoinType jointype,
1179  JoinPathExtraData *extra,
1180  bool parallel_hash)
1181 {
1182  JoinCostWorkspace workspace;
1183 
1184  /*
1185  * If the inner path is parameterized, the parameterization must be fully
1186  * satisfied by the proposed outer path. Parameterized partial paths are
1187  * not supported. The caller should already have verified that no lateral
1188  * rels are required here.
1189  */
1190  Assert(bms_is_empty(joinrel->lateral_relids));
1191  if (inner_path->param_info != NULL)
1192  {
1193  Relids inner_paramrels = inner_path->param_info->ppi_req_outer;
1194 
1195  if (!bms_is_empty(inner_paramrels))
1196  return;
1197  }
1198 
1199  /*
1200  * Before creating a path, get a quick lower bound on what it is likely to
1201  * cost. Bail out right away if it looks terrible.
1202  */
1203  initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
1204  outer_path, inner_path, extra, parallel_hash);
1205  if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
1206  return;
1207 
1208  /* Might be good enough to be worth trying, so let's try it. */
1209  add_partial_path(joinrel, (Path *)
1210  create_hashjoin_path(root,
1211  joinrel,
1212  jointype,
1213  &workspace,
1214  extra,
1215  outer_path,
1216  inner_path,
1217  parallel_hash,
1218  extra->restrictlist,
1219  NULL,
1220  hashclauses));
1221 }
1222 
1223 /*
1224  * clause_sides_match_join
1225  * Determine whether a join clause is of the right form to use in this join.
1226  *
1227  * We already know that the clause is a binary opclause referencing only the
1228  * rels in the current join. The point here is to check whether it has the
1229  * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
1230  * rather than mixing outer and inner vars on either side. If it matches,
1231  * we set the transient flag outer_is_left to identify which side is which.
1232  */
1233 static inline bool
1234 clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel,
1235  RelOptInfo *innerrel)
1236 {
1237  if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
1238  bms_is_subset(rinfo->right_relids, innerrel->relids))
1239  {
1240  /* lefthand side is outer */
1241  rinfo->outer_is_left = true;
1242  return true;
1243  }
1244  else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
1245  bms_is_subset(rinfo->right_relids, outerrel->relids))
1246  {
1247  /* righthand side is outer */
1248  rinfo->outer_is_left = false;
1249  return true;
1250  }
1251  return false; /* no good for these input relations */
1252 }
1253 
1254 /*
1255  * sort_inner_and_outer
1256  * Create mergejoin join paths by explicitly sorting both the outer and
1257  * inner join relations on each available merge ordering.
1258  *
1259  * 'joinrel' is the join relation
1260  * 'outerrel' is the outer join relation
1261  * 'innerrel' is the inner join relation
1262  * 'jointype' is the type of join to do
1263  * 'extra' contains additional input values
1264  */
1265 static void
1266 sort_inner_and_outer(PlannerInfo *root,
1267  RelOptInfo *joinrel,
1268  RelOptInfo *outerrel,
1269  RelOptInfo *innerrel,
1270  JoinType jointype,
1271  JoinPathExtraData *extra)
1272 {
1273  JoinType save_jointype = jointype;
1274  Path *outer_path;
1275  Path *inner_path;
1276  Path *cheapest_partial_outer = NULL;
1277  Path *cheapest_safe_inner = NULL;
1278  List *all_pathkeys;
1279  ListCell *l;
1280 
1281  /*
1282  * We only consider the cheapest-total-cost input paths, since we are
1283  * assuming here that a sort is required. We will consider
1284  * cheapest-startup-cost input paths later, and only if they don't need a
1285  * sort.
1286  *
1287  * This function intentionally does not consider parameterized input
1288  * paths, except when the cheapest-total is parameterized. If we did so,
1289  * we'd have a combinatorial explosion of mergejoin paths of dubious
1290  * value. This interacts with decisions elsewhere that also discriminate
1291  * against mergejoins with parameterized inputs; see comments in
1292  * src/backend/optimizer/README.
1293  */
1294  outer_path = outerrel->cheapest_total_path;
1295  inner_path = innerrel->cheapest_total_path;
1296 
1297  /*
1298  * If either cheapest-total path is parameterized by the other rel, we
1299  * can't use a mergejoin. (There's no use looking for alternative input
1300  * paths, since these should already be the least-parameterized available
1301  * paths.)
1302  */
1303  if (PATH_PARAM_BY_REL(outer_path, innerrel) ||
1304  PATH_PARAM_BY_REL(inner_path, outerrel))
1305  return;
1306 
1307  /*
1308  * If unique-ification is requested, do it and then handle as a plain
1309  * inner join.
1310  */
1311  if (jointype == JOIN_UNIQUE_OUTER)
1312  {
1313  outer_path = (Path *) create_unique_path(root, outerrel,
1314  outer_path, extra->sjinfo);
1315  Assert(outer_path);
1316  jointype = JOIN_INNER;
1317  }
1318  else if (jointype == JOIN_UNIQUE_INNER)
1319  {
1320  inner_path = (Path *) create_unique_path(root, innerrel,
1321  inner_path, extra->sjinfo);
1322  Assert(inner_path);
1323  jointype = JOIN_INNER;
1324  }
1325 
1326  /*
1327  * If the joinrel is parallel-safe, we may be able to consider a partial
1328  * merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
1329  * outer path will be partial, and therefore we won't be able to properly
1330  * guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1331  * and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1332  * Also, the resulting path must not be parameterized.
1333  */
1334  if (joinrel->consider_parallel &&
1335  save_jointype != JOIN_UNIQUE_OUTER &&
1336  save_jointype != JOIN_FULL &&
1337  save_jointype != JOIN_RIGHT &&
1338  save_jointype != JOIN_RIGHT_ANTI &&
1339  outerrel->partial_pathlist != NIL &&
1340  bms_is_empty(joinrel->lateral_relids))
1341  {
1342  cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist);
1343 
1344  if (inner_path->parallel_safe)
1345  cheapest_safe_inner = inner_path;
1346  else if (save_jointype != JOIN_UNIQUE_INNER)
1347  cheapest_safe_inner =
1348  get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1349  }
1350 
1351  /*
1352  * Each possible ordering of the available mergejoin clauses will generate
1353  * a differently-sorted result path at essentially the same cost. We have
1354  * no basis for choosing one over another at this level of joining, but
1355  * some sort orders may be more useful than others for higher-level
1356  * mergejoins, so it's worth considering multiple orderings.
1357  *
1358  * Actually, it's not quite true that every mergeclause ordering will
1359  * generate a different path order, because some of the clauses may be
1360  * partially redundant (refer to the same EquivalenceClasses). Therefore,
1361  * what we do is convert the mergeclause list to a list of canonical
1362  * pathkeys, and then consider different orderings of the pathkeys.
1363  *
1364  * Generating a path for *every* permutation of the pathkeys doesn't seem
1365  * like a winning strategy; the cost in planning time is too high. For
1366  * now, we generate one path for each pathkey, listing that pathkey first
1367  * and the rest in random order. This should allow at least a one-clause
1368  * mergejoin without re-sorting against any other possible mergejoin
1369  * partner path. But if we've not guessed the right ordering of secondary
1370  * keys, we may end up evaluating clauses as qpquals when they could have
1371  * been done as mergeclauses. (In practice, it's rare that there's more
1372  * than two or three mergeclauses, so expending a huge amount of thought
1373  * on that is probably not worth it.)
1374  *
1375  * The pathkey order returned by select_outer_pathkeys_for_merge() has
1376  * some heuristics behind it (see that function), so be sure to try it
1377  * exactly as-is as well as making variants.
1378  */
1379  all_pathkeys = select_outer_pathkeys_for_merge(root,
1380  extra->mergeclause_list,
1381  joinrel);
1382 
1383  foreach(l, all_pathkeys)
1384  {
1385  PathKey *front_pathkey = (PathKey *) lfirst(l);
1386  List *cur_mergeclauses;
1387  List *outerkeys;
1388  List *innerkeys;
1389  List *merge_pathkeys;
1390 
1391  /* Make a pathkey list with this guy first */
1392  if (l != list_head(all_pathkeys))
1393  outerkeys = lcons(front_pathkey,
1394  list_delete_nth_cell(list_copy(all_pathkeys),
1395  foreach_current_index(l)));
1396  else
1397  outerkeys = all_pathkeys; /* no work at first one... */
1398 
1399  /* Sort the mergeclauses into the corresponding ordering */
1400  cur_mergeclauses =
1401  find_mergeclauses_for_outer_pathkeys(root,
1402  outerkeys,
1403  extra->mergeclause_list);
1404 
1405  /* Should have used them all... */
1406  Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list));
1407 
1408  /* Build sort pathkeys for the inner side */
1409  innerkeys = make_inner_pathkeys_for_merge(root,
1410  cur_mergeclauses,
1411  outerkeys);
1412 
1413  /* Build pathkeys representing output sort order */
1414  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1415  outerkeys);
1416 
1417  /*
1418  * And now we can make the path.
1419  *
1420  * Note: it's possible that the cheapest paths will already be sorted
1421  * properly. try_mergejoin_path will detect that case and suppress an
1422  * explicit sort step, so we needn't do so here.
1423  */
1424  try_mergejoin_path(root,
1425  joinrel,
1426  outer_path,
1427  inner_path,
1428  merge_pathkeys,
1429  cur_mergeclauses,
1430  outerkeys,
1431  innerkeys,
1432  jointype,
1433  extra,
1434  false);
1435 
1436  /*
1437  * If we have partial outer and parallel safe inner path then try
1438  * partial mergejoin path.
1439  */
1440  if (cheapest_partial_outer && cheapest_safe_inner)
1441  try_partial_mergejoin_path(root,
1442  joinrel,
1443  cheapest_partial_outer,
1444  cheapest_safe_inner,
1445  merge_pathkeys,
1446  cur_mergeclauses,
1447  outerkeys,
1448  innerkeys,
1449  jointype,
1450  extra);
1451  }
1452 }
1453 
1454 /*
1455  * generate_mergejoin_paths
1456  * Creates possible mergejoin paths for input outerpath.
1457  *
1458  * We generate mergejoins if mergejoin clauses are available. We have
1459  * two ways to generate the inner path for a mergejoin: sort the cheapest
1460  * inner path, or use an inner path that is already suitably ordered for the
1461  * merge. If we have several mergeclauses, it could be that there is no inner
1462  * path (or only a very expensive one) for the full list of mergeclauses, but
1463  * better paths exist if we truncate the mergeclause list (thereby discarding
1464  * some sort key requirements). So, we consider truncations of the
1465  * mergeclause list as well as the full list. (Ideally we'd consider all
1466  * subsets of the mergeclause list, but that seems way too expensive.)
1467  */
1468 static void
1469 generate_mergejoin_paths(PlannerInfo *root,
1470  RelOptInfo *joinrel,
1471  RelOptInfo *innerrel,
1472  Path *outerpath,
1473  JoinType jointype,
1474  JoinPathExtraData *extra,
1475  bool useallclauses,
1476  Path *inner_cheapest_total,
1477  List *merge_pathkeys,
1478  bool is_partial)
1479 {
1480  List *mergeclauses;
1481  List *innersortkeys;
1482  List *trialsortkeys;
1483  Path *cheapest_startup_inner;
1484  Path *cheapest_total_inner;
1485  JoinType save_jointype = jointype;
1486  int num_sortkeys;
1487  int sortkeycnt;
1488 
1489  if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER)
1490  jointype = JOIN_INNER;
1491 
1492  /* Look for useful mergeclauses (if any) */
1493  mergeclauses =
1494  find_mergeclauses_for_outer_pathkeys(root,
1495  outerpath->pathkeys,
1496  extra->mergeclause_list);
1497 
1498  /*
1499  * Done with this outer path if no chance for a mergejoin.
1500  *
1501  * Special corner case: for "x FULL JOIN y ON true", there will be no join
1502  * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1503  * but since mergejoin is our only join type that supports FULL JOIN
1504  * without any join clauses, it's necessary to generate a clauseless
1505  * mergejoin path instead.
1506  */
1507  if (mergeclauses == NIL)
1508  {
1509  if (jointype == JOIN_FULL)
1510  /* okay to try for mergejoin */ ;
1511  else
1512  return;
1513  }
1514  if (useallclauses &&
1515  list_length(mergeclauses) != list_length(extra->mergeclause_list))
1516  return;
1517 
1518  /* Compute the required ordering of the inner path */
1519  innersortkeys = make_inner_pathkeys_for_merge(root,
1520  mergeclauses,
1521  outerpath->pathkeys);
1522 
1523  /*
1524  * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1525  * a sort will be needed, only cheapest total cost matters. (But
1526  * try_mergejoin_path will do the right thing if inner_cheapest_total is
1527  * already correctly sorted.)
1528  */
1529  try_mergejoin_path(root,
1530  joinrel,
1531  outerpath,
1532  inner_cheapest_total,
1533  merge_pathkeys,
1534  mergeclauses,
1535  NIL,
1536  innersortkeys,
1537  jointype,
1538  extra,
1539  is_partial);
1540 
1541  /* Can't do anything else if inner path needs to be unique'd */
1542  if (save_jointype == JOIN_UNIQUE_INNER)
1543  return;
1544 
1545  /*
1546  * Look for presorted inner paths that satisfy the innersortkey list ---
1547  * or any truncation thereof, if we are allowed to build a mergejoin using
1548  * a subset of the merge clauses. Here, we consider both cheap startup
1549  * cost and cheap total cost.
1550  *
1551  * Currently we do not consider parameterized inner paths here. This
1552  * interacts with decisions elsewhere that also discriminate against
1553  * mergejoins with parameterized inputs; see comments in
1554  * src/backend/optimizer/README.
1555  *
1556  * As we shorten the sortkey list, we should consider only paths that are
1557  * strictly cheaper than (in particular, not the same as) any path found
1558  * in an earlier iteration. Otherwise we'd be intentionally using fewer
1559  * merge keys than a given path allows (treating the rest as plain
1560  * joinquals), which is unlikely to be a good idea. Also, eliminating
1561  * paths here on the basis of compare_path_costs is a lot cheaper than
1562  * building the mergejoin path only to throw it away.
1563  *
1564  * If inner_cheapest_total is well enough sorted to have not required a
1565  * sort in the path made above, we shouldn't make a duplicate path with
1566  * it, either. We handle that case with the same logic that handles the
1567  * previous consideration, by initializing the variables that track
1568  * cheapest-so-far properly. Note that we do NOT reject
1569  * inner_cheapest_total if we find it matches some shorter set of
1570  * pathkeys. That case corresponds to using fewer mergekeys to avoid
1571  * sorting inner_cheapest_total, whereas we did sort it above, so the
1572  * plans being considered are different.
1573  */
1574  if (pathkeys_contained_in(innersortkeys,
1575  inner_cheapest_total->pathkeys))
1576  {
1577  /* inner_cheapest_total didn't require a sort */
1578  cheapest_startup_inner = inner_cheapest_total;
1579  cheapest_total_inner = inner_cheapest_total;
1580  }
1581  else
1582  {
1583  /* it did require a sort, at least for the full set of keys */
1584  cheapest_startup_inner = NULL;
1585  cheapest_total_inner = NULL;
1586  }
1587  num_sortkeys = list_length(innersortkeys);
1588  if (num_sortkeys > 1 && !useallclauses)
1589  trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */
1590  else
1591  trialsortkeys = innersortkeys; /* won't really truncate */
1592 
1593  for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--)
1594  {
1595  Path *innerpath;
1596  List *newclauses = NIL;
1597 
1598  /*
1599  * Look for an inner path ordered well enough for the first
1600  * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1601  * destructively, which is why we made a copy...
1602  */
1603  trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
1604  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1605  trialsortkeys,
1606  NULL,
1607  TOTAL_COST,
1608  is_partial);
1609  if (innerpath != NULL &&
1610  (cheapest_total_inner == NULL ||
1611  compare_path_costs(innerpath, cheapest_total_inner,
1612  TOTAL_COST) < 0))
1613  {
1614  /* Found a cheap (or even-cheaper) sorted path */
1615  /* Select the right mergeclauses, if we didn't already */
1616  if (sortkeycnt < num_sortkeys)
1617  {
1618  newclauses =
1619  trim_mergeclauses_for_inner_pathkeys(root,
1620  mergeclauses,
1621  trialsortkeys);
1622  Assert(newclauses != NIL);
1623  }
1624  else
1625  newclauses = mergeclauses;
1626  try_mergejoin_path(root,
1627  joinrel,
1628  outerpath,
1629  innerpath,
1630  merge_pathkeys,
1631  newclauses,
1632  NIL,
1633  NIL,
1634  jointype,
1635  extra,
1636  is_partial);
1637  cheapest_total_inner = innerpath;
1638  }
1639  /* Same on the basis of cheapest startup cost ... */
1640  innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
1641  trialsortkeys,
1642  NULL,
1643  STARTUP_COST,
1644  is_partial);
1645  if (innerpath != NULL &&
1646  (cheapest_startup_inner == NULL ||
1647  compare_path_costs(innerpath, cheapest_startup_inner,
1648  STARTUP_COST) < 0))
1649  {
1650  /* Found a cheap (or even-cheaper) sorted path */
1651  if (innerpath != cheapest_total_inner)
1652  {
1653  /*
1654  * Avoid rebuilding clause list if we already made one; saves
1655  * memory in big join trees...
1656  */
1657  if (newclauses == NIL)
1658  {
1659  if (sortkeycnt < num_sortkeys)
1660  {
1661  newclauses =
1662  trim_mergeclauses_for_inner_pathkeys(root,
1663  mergeclauses,
1664  trialsortkeys);
1665  Assert(newclauses != NIL);
1666  }
1667  else
1668  newclauses = mergeclauses;
1669  }
1670  try_mergejoin_path(root,
1671  joinrel,
1672  outerpath,
1673  innerpath,
1674  merge_pathkeys,
1675  newclauses,
1676  NIL,
1677  NIL,
1678  jointype,
1679  extra,
1680  is_partial);
1681  }
1682  cheapest_startup_inner = innerpath;
1683  }
1684 
1685  /*
1686  * Don't consider truncated sortkeys if we need all clauses.
1687  */
1688  if (useallclauses)
1689  break;
1690  }
1691 }
1692 
1693 /*
1694  * match_unsorted_outer
1695  * Creates possible join paths for processing a single join relation
1696  * 'joinrel' by employing either iterative substitution or
1697  * mergejoining on each of its possible outer paths (considering
1698  * only outer paths that are already ordered well enough for merging).
1699  *
1700  * We always generate a nestloop path for each available outer path.
1701  * In fact we may generate as many as five: one on the cheapest-total-cost
1702  * inner path, one on the same with materialization, one on the
1703  * cheapest-startup-cost inner path (if different), one on the
1704  * cheapest-total inner-indexscan path (if any), and one on the
1705  * cheapest-startup inner-indexscan path (if different).
1706  *
1707  * We also consider mergejoins if mergejoin clauses are available. See
1708  * detailed comments in generate_mergejoin_paths.
1709  *
1710  * 'joinrel' is the join relation
1711  * 'outerrel' is the outer join relation
1712  * 'innerrel' is the inner join relation
1713  * 'jointype' is the type of join to do
1714  * 'extra' contains additional input values
1715  */
1716 static void
1717 match_unsorted_outer(PlannerInfo *root,
1718  RelOptInfo *joinrel,
1719  RelOptInfo *outerrel,
1720  RelOptInfo *innerrel,
1721  JoinType jointype,
1722  JoinPathExtraData *extra)
1723 {
1724  JoinType save_jointype = jointype;
1725  bool nestjoinOK;
1726  bool useallclauses;
1727  Path *inner_cheapest_total = innerrel->cheapest_total_path;
1728  Path *matpath = NULL;
1729  ListCell *lc1;
1730 
1731  /*
1732  * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1733  * are doing a right, right-anti or full mergejoin, we must use *all* the
1734  * mergeclauses as join clauses, else we will not have a valid plan.
1735  * (Although these two flags are currently inverses, keep them separate
1736  * for clarity and possible future changes.)
1737  */
1738  switch (jointype)
1739  {
1740  case JOIN_INNER:
1741  case JOIN_LEFT:
1742  case JOIN_SEMI:
1743  case JOIN_ANTI:
1744  nestjoinOK = true;
1745  useallclauses = false;
1746  break;
1747  case JOIN_RIGHT:
1748  case JOIN_RIGHT_ANTI:
1749  case JOIN_FULL:
1750  nestjoinOK = false;
1751  useallclauses = true;
1752  break;
1753  case JOIN_UNIQUE_OUTER:
1754  case JOIN_UNIQUE_INNER:
1755  jointype = JOIN_INNER;
1756  nestjoinOK = true;
1757  useallclauses = false;
1758  break;
1759  default:
1760  elog(ERROR, "unrecognized join type: %d",
1761  (int) jointype);
1762  nestjoinOK = false; /* keep compiler quiet */
1763  useallclauses = false;
1764  break;
1765  }
1766 
1767  /*
1768  * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1769  * we will consider it below as a member of cheapest_parameterized_paths,
1770  * but the other possibilities considered in this routine aren't usable.
1771  */
1772  if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel))
1773  inner_cheapest_total = NULL;
1774 
1775  /*
1776  * If we need to unique-ify the inner path, we will consider only the
1777  * cheapest-total inner.
1778  */
1779  if (save_jointype == JOIN_UNIQUE_INNER)
1780  {
1781  /* No way to do this with an inner path parameterized by outer rel */
1782  if (inner_cheapest_total == NULL)
1783  return;
1784  inner_cheapest_total = (Path *)
1785  create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo);
1786  Assert(inner_cheapest_total);
1787  }
1788  else if (nestjoinOK)
1789  {
1790  /*
1791  * Consider materializing the cheapest inner path, unless
1792  * enable_material is off or the path in question materializes its
1793  * output anyway.
1794  */
1795  if (enable_material && inner_cheapest_total != NULL &&
1796  !ExecMaterializesOutput(inner_cheapest_total->pathtype))
1797  matpath = (Path *)
1798  create_material_path(innerrel, inner_cheapest_total);
1799  }
1800 
1801  foreach(lc1, outerrel->pathlist)
1802  {
1803  Path *outerpath = (Path *) lfirst(lc1);
1804  List *merge_pathkeys;
1805 
1806  /*
1807  * We cannot use an outer path that is parameterized by the inner rel.
1808  */
1809  if (PATH_PARAM_BY_REL(outerpath, innerrel))
1810  continue;
1811 
1812  /*
1813  * If we need to unique-ify the outer path, it's pointless to consider
1814  * any but the cheapest outer. (XXX we don't consider parameterized
1815  * outers, nor inners, for unique-ified cases. Should we?)
1816  */
1817  if (save_jointype == JOIN_UNIQUE_OUTER)
1818  {
1819  if (outerpath != outerrel->cheapest_total_path)
1820  continue;
1821  outerpath = (Path *) create_unique_path(root, outerrel,
1822  outerpath, extra->sjinfo);
1823  Assert(outerpath);
1824  }
1825 
1826  /*
1827  * The result will have this sort order (even if it is implemented as
1828  * a nestloop, and even if some of the mergeclauses are implemented by
1829  * qpquals rather than as true mergeclauses):
1830  */
1831  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1832  outerpath->pathkeys);
1833 
1834  if (save_jointype == JOIN_UNIQUE_INNER)
1835  {
1836  /*
1837  * Consider nestloop join, but only with the unique-ified cheapest
1838  * inner path
1839  */
1840  try_nestloop_path(root,
1841  joinrel,
1842  outerpath,
1843  inner_cheapest_total,
1844  merge_pathkeys,
1845  jointype,
1846  extra);
1847  }
1848  else if (nestjoinOK)
1849  {
1850  /*
1851  * Consider nestloop joins using this outer path and various
1852  * available paths for the inner relation. We consider the
1853  * cheapest-total paths for each available parameterization of the
1854  * inner relation, including the unparameterized case.
1855  */
1856  ListCell *lc2;
1857 
1858  foreach(lc2, innerrel->cheapest_parameterized_paths)
1859  {
1860  Path *innerpath = (Path *) lfirst(lc2);
1861  Path *mpath;
1862 
1863  try_nestloop_path(root,
1864  joinrel,
1865  outerpath,
1866  innerpath,
1867  merge_pathkeys,
1868  jointype,
1869  extra);
1870 
1871  /*
1872  * Try generating a memoize path and see if that makes the
1873  * nested loop any cheaper.
1874  */
1875  mpath = get_memoize_path(root, innerrel, outerrel,
1876  innerpath, outerpath, jointype,
1877  extra);
1878  if (mpath != NULL)
1879  try_nestloop_path(root,
1880  joinrel,
1881  outerpath,
1882  mpath,
1883  merge_pathkeys,
1884  jointype,
1885  extra);
1886  }
1887 
1888  /* Also consider materialized form of the cheapest inner path */
1889  if (matpath != NULL)
1890  try_nestloop_path(root,
1891  joinrel,
1892  outerpath,
1893  matpath,
1894  merge_pathkeys,
1895  jointype,
1896  extra);
1897  }
1898 
1899  /* Can't do anything else if outer path needs to be unique'd */
1900  if (save_jointype == JOIN_UNIQUE_OUTER)
1901  continue;
1902 
1903  /* Can't do anything else if inner rel is parameterized by outer */
1904  if (inner_cheapest_total == NULL)
1905  continue;
1906 
1907  /* Generate merge join paths */
1908  generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
1909  save_jointype, extra, useallclauses,
1910  inner_cheapest_total, merge_pathkeys,
1911  false);
1912  }
1913 
1914  /*
1915  * Consider partial nestloop and mergejoin plan if outerrel has any
1916  * partial path and the joinrel is parallel-safe. However, we can't
1917  * handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1918  * therefore we won't be able to properly guarantee uniqueness. Nor can
1919  * we handle joins needing lateral rels, since partial paths must not be
1920  * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
1921  * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1922  */
1923  if (joinrel->consider_parallel &&
1924  save_jointype != JOIN_UNIQUE_OUTER &&
1925  save_jointype != JOIN_FULL &&
1926  save_jointype != JOIN_RIGHT &&
1927  save_jointype != JOIN_RIGHT_ANTI &&
1928  outerrel->partial_pathlist != NIL &&
1929  bms_is_empty(joinrel->lateral_relids))
1930  {
1931  if (nestjoinOK)
1932  consider_parallel_nestloop(root, joinrel, outerrel, innerrel,
1933  save_jointype, extra);
1934 
1935  /*
1936  * If inner_cheapest_total is NULL or non parallel-safe then find the
1937  * cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1938  * can't use any alternative inner path.
1939  */
1940  if (inner_cheapest_total == NULL ||
1941  !inner_cheapest_total->parallel_safe)
1942  {
1943  if (save_jointype == JOIN_UNIQUE_INNER)
1944  return;
1945 
1946  inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
1947  }
1948 
1949  if (inner_cheapest_total)
1950  consider_parallel_mergejoin(root, joinrel, outerrel, innerrel,
1951  save_jointype, extra,
1952  inner_cheapest_total);
1953  }
1954 }
1955 
1956 /*
1957  * consider_parallel_mergejoin
1958  * Try to build partial paths for a joinrel by joining a partial path
1959  * for the outer relation to a complete path for the inner relation.
1960  *
1961  * 'joinrel' is the join relation
1962  * 'outerrel' is the outer join relation
1963  * 'innerrel' is the inner join relation
1964  * 'jointype' is the type of join to do
1965  * 'extra' contains additional input values
1966  * 'inner_cheapest_total' cheapest total path for innerrel
1967  */
1968 static void
1969 consider_parallel_mergejoin(PlannerInfo *root,
1970  RelOptInfo *joinrel,
1971  RelOptInfo *outerrel,
1972  RelOptInfo *innerrel,
1973  JoinType jointype,
1974  JoinPathExtraData *extra,
1975  Path *inner_cheapest_total)
1976 {
1977  ListCell *lc1;
1978 
1979  /* generate merge join path for each partial outer path */
1980  foreach(lc1, outerrel->partial_pathlist)
1981  {
1982  Path *outerpath = (Path *) lfirst(lc1);
1983  List *merge_pathkeys;
1984 
1985  /*
1986  * Figure out what useful ordering any paths we create will have.
1987  */
1988  merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
1989  outerpath->pathkeys);
1990 
1991  generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype,
1992  extra, false, inner_cheapest_total,
1993  merge_pathkeys, true);
1994  }
1995 }
1996 
1997 /*
1998  * consider_parallel_nestloop
1999  * Try to build partial paths for a joinrel by joining a partial path for the
2000  * outer relation to a complete path for the inner relation.
2001  *
2002  * 'joinrel' is the join relation
2003  * 'outerrel' is the outer join relation
2004  * 'innerrel' is the inner join relation
2005  * 'jointype' is the type of join to do
2006  * 'extra' contains additional input values
2007  */
2008 static void
2009 consider_parallel_nestloop(PlannerInfo *root,
2010  RelOptInfo *joinrel,
2011  RelOptInfo *outerrel,
2012  RelOptInfo *innerrel,
2013  JoinType jointype,
2014  JoinPathExtraData *extra)
2015 {
2016  JoinType save_jointype = jointype;
2017  ListCell *lc1;
2018 
2019  if (jointype == JOIN_UNIQUE_INNER)
2020  jointype = JOIN_INNER;
2021 
2022  foreach(lc1, outerrel->partial_pathlist)
2023  {
2024  Path *outerpath = (Path *) lfirst(lc1);
2025  List *pathkeys;
2026  ListCell *lc2;
2027 
2028  /* Figure out what useful ordering any paths we create will have. */
2029  pathkeys = build_join_pathkeys(root, joinrel, jointype,
2030  outerpath->pathkeys);
2031 
2032  /*
2033  * Try the cheapest parameterized paths; only those which will produce
2034  * an unparameterized path when joined to this outerrel will survive
2035  * try_partial_nestloop_path. The cheapest unparameterized path is
2036  * also in this list.
2037  */
2038  foreach(lc2, innerrel->cheapest_parameterized_paths)
2039  {
2040  Path *innerpath = (Path *) lfirst(lc2);
2041  Path *mpath;
2042 
2043  /* Can't join to an inner path that is not parallel-safe */
2044  if (!innerpath->parallel_safe)
2045  continue;
2046 
2047  /*
2048  * If we're doing JOIN_UNIQUE_INNER, we can only use the inner's
2049  * cheapest_total_path, and we have to unique-ify it. (We might
2050  * be able to relax this to allow other safe, unparameterized
2051  * inner paths, but right now create_unique_path is not on board
2052  * with that.)
2053  */
2054  if (save_jointype == JOIN_UNIQUE_INNER)
2055  {
2056  if (innerpath != innerrel->cheapest_total_path)
2057  continue;
2058  innerpath = (Path *) create_unique_path(root, innerrel,
2059  innerpath,
2060  extra->sjinfo);
2061  Assert(innerpath);
2062  }
2063 
2064  try_partial_nestloop_path(root, joinrel, outerpath, innerpath,
2065  pathkeys, jointype, extra);
2066 
2067  /*
2068  * Try generating a memoize path and see if that makes the nested
2069  * loop any cheaper.
2070  */
2071  mpath = get_memoize_path(root, innerrel, outerrel,
2072  innerpath, outerpath, jointype,
2073  extra);
2074  if (mpath != NULL)
2075  try_partial_nestloop_path(root, joinrel, outerpath, mpath,
2076  pathkeys, jointype, extra);
2077  }
2078  }
2079 }
2080 
2081 /*
2082  * hash_inner_and_outer
2083  * Create hashjoin join paths by explicitly hashing both the outer and
2084  * inner keys of each available hash clause.
2085  *
2086  * 'joinrel' is the join relation
2087  * 'outerrel' is the outer join relation
2088  * 'innerrel' is the inner join relation
2089  * 'jointype' is the type of join to do
2090  * 'extra' contains additional input values
2091  */
2092 static void
2093 hash_inner_and_outer(PlannerInfo *root,
2094  RelOptInfo *joinrel,
2095  RelOptInfo *outerrel,
2096  RelOptInfo *innerrel,
2097  JoinType jointype,
2098  JoinPathExtraData *extra)
2099 {
2100  JoinType save_jointype = jointype;
2101  bool isouterjoin = IS_OUTER_JOIN(jointype);
2102  List *hashclauses;
2103  ListCell *l;
2104 
2105  /*
2106  * We need to build only one hashclauses list for any given pair of outer
2107  * and inner relations; all of the hashable clauses will be used as keys.
2108  *
2109  * Scan the join's restrictinfo list to find hashjoinable clauses that are
2110  * usable with this pair of sub-relations.
2111  */
2112  hashclauses = NIL;
2113  foreach(l, extra->restrictlist)
2114  {
2115  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2116 
2117  /*
2118  * If processing an outer join, only use its own join clauses for
2119  * hashing. For inner joins we need not be so picky.
2120  */
2121  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2122  continue;
2123 
2124  if (!restrictinfo->can_join ||
2125  restrictinfo->hashjoinoperator == InvalidOid)
2126  continue; /* not hashjoinable */
2127 
2128  /*
2129  * Check if clause has the form "outer op inner" or "inner op outer".
2130  */
2131  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2132  continue; /* no good for these input relations */
2133 
2134  hashclauses = lappend(hashclauses, restrictinfo);
2135  }
2136 
2137  /* If we found any usable hashclauses, make paths */
2138  if (hashclauses)
2139  {
2140  /*
2141  * We consider both the cheapest-total-cost and cheapest-startup-cost
2142  * outer paths. There's no need to consider any but the
2143  * cheapest-total-cost inner path, however.
2144  */
2145  Path *cheapest_startup_outer = outerrel->cheapest_startup_path;
2146  Path *cheapest_total_outer = outerrel->cheapest_total_path;
2147  Path *cheapest_total_inner = innerrel->cheapest_total_path;
2148 
2149  /*
2150  * If either cheapest-total path is parameterized by the other rel, we
2151  * can't use a hashjoin. (There's no use looking for alternative
2152  * input paths, since these should already be the least-parameterized
2153  * available paths.)
2154  */
2155  if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) ||
2156  PATH_PARAM_BY_REL(cheapest_total_inner, outerrel))
2157  return;
2158 
2159  /* Unique-ify if need be; we ignore parameterized possibilities */
2160  if (jointype == JOIN_UNIQUE_OUTER)
2161  {
2162  cheapest_total_outer = (Path *)
2163  create_unique_path(root, outerrel,
2164  cheapest_total_outer, extra->sjinfo);
2165  Assert(cheapest_total_outer);
2166  jointype = JOIN_INNER;
2167  try_hashjoin_path(root,
2168  joinrel,
2169  cheapest_total_outer,
2170  cheapest_total_inner,
2171  hashclauses,
2172  jointype,
2173  extra);
2174  /* no possibility of cheap startup here */
2175  }
2176  else if (jointype == JOIN_UNIQUE_INNER)
2177  {
2178  cheapest_total_inner = (Path *)
2179  create_unique_path(root, innerrel,
2180  cheapest_total_inner, extra->sjinfo);
2181  Assert(cheapest_total_inner);
2182  jointype = JOIN_INNER;
2183  try_hashjoin_path(root,
2184  joinrel,
2185  cheapest_total_outer,
2186  cheapest_total_inner,
2187  hashclauses,
2188  jointype,
2189  extra);
2190  if (cheapest_startup_outer != NULL &&
2191  cheapest_startup_outer != cheapest_total_outer)
2192  try_hashjoin_path(root,
2193  joinrel,
2194  cheapest_startup_outer,
2195  cheapest_total_inner,
2196  hashclauses,
2197  jointype,
2198  extra);
2199  }
2200  else
2201  {
2202  /*
2203  * For other jointypes, we consider the cheapest startup outer
2204  * together with the cheapest total inner, and then consider
2205  * pairings of cheapest-total paths including parameterized ones.
2206  * There is no use in generating parameterized paths on the basis
2207  * of possibly cheap startup cost, so this is sufficient.
2208  */
2209  ListCell *lc1;
2210  ListCell *lc2;
2211 
2212  if (cheapest_startup_outer != NULL)
2213  try_hashjoin_path(root,
2214  joinrel,
2215  cheapest_startup_outer,
2216  cheapest_total_inner,
2217  hashclauses,
2218  jointype,
2219  extra);
2220 
2221  foreach(lc1, outerrel->cheapest_parameterized_paths)
2222  {
2223  Path *outerpath = (Path *) lfirst(lc1);
2224 
2225  /*
2226  * We cannot use an outer path that is parameterized by the
2227  * inner rel.
2228  */
2229  if (PATH_PARAM_BY_REL(outerpath, innerrel))
2230  continue;
2231 
2232  foreach(lc2, innerrel->cheapest_parameterized_paths)
2233  {
2234  Path *innerpath = (Path *) lfirst(lc2);
2235 
2236  /*
2237  * We cannot use an inner path that is parameterized by
2238  * the outer rel, either.
2239  */
2240  if (PATH_PARAM_BY_REL(innerpath, outerrel))
2241  continue;
2242 
2243  if (outerpath == cheapest_startup_outer &&
2244  innerpath == cheapest_total_inner)
2245  continue; /* already tried it */
2246 
2247  try_hashjoin_path(root,
2248  joinrel,
2249  outerpath,
2250  innerpath,
2251  hashclauses,
2252  jointype,
2253  extra);
2254  }
2255  }
2256  }
2257 
2258  /*
2259  * If the joinrel is parallel-safe, we may be able to consider a
2260  * partial hash join. However, we can't handle JOIN_UNIQUE_OUTER,
2261  * because the outer path will be partial, and therefore we won't be
2262  * able to properly guarantee uniqueness. Also, the resulting path
2263  * must not be parameterized.
2264  */
2265  if (joinrel->consider_parallel &&
2266  save_jointype != JOIN_UNIQUE_OUTER &&
2267  outerrel->partial_pathlist != NIL &&
2268  bms_is_empty(joinrel->lateral_relids))
2269  {
2270  Path *cheapest_partial_outer;
2271  Path *cheapest_partial_inner = NULL;
2272  Path *cheapest_safe_inner = NULL;
2273 
2274  cheapest_partial_outer =
2275  (Path *) linitial(outerrel->partial_pathlist);
2276 
2277  /*
2278  * Can we use a partial inner plan too, so that we can build a
2279  * shared hash table in parallel? We can't handle
2280  * JOIN_UNIQUE_INNER because we can't guarantee uniqueness.
2281  */
2282  if (innerrel->partial_pathlist != NIL &&
2283  save_jointype != JOIN_UNIQUE_INNER &&
2284  enable_parallel_hash)
2285  {
2286  cheapest_partial_inner =
2287  (Path *) linitial(innerrel->partial_pathlist);
2288  try_partial_hashjoin_path(root, joinrel,
2289  cheapest_partial_outer,
2290  cheapest_partial_inner,
2291  hashclauses, jointype, extra,
2292  true /* parallel_hash */ );
2293  }
2294 
2295  /*
2296  * Normally, given that the joinrel is parallel-safe, the cheapest
2297  * total inner path will also be parallel-safe, but if not, we'll
2298  * have to search for the cheapest safe, unparameterized inner
2299  * path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2300  * inner path. If full, right, or right-anti join, we can't use
2301  * parallelism (building the hash table in each backend) because
2302  * no one process has all the match bits.
2303  */
2304  if (save_jointype == JOIN_FULL ||
2305  save_jointype == JOIN_RIGHT ||
2306  save_jointype == JOIN_RIGHT_ANTI)
2307  cheapest_safe_inner = NULL;
2308  else if (cheapest_total_inner->parallel_safe)
2309  cheapest_safe_inner = cheapest_total_inner;
2310  else if (save_jointype != JOIN_UNIQUE_INNER)
2311  cheapest_safe_inner =
2312  get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
2313 
2314  if (cheapest_safe_inner != NULL)
2315  try_partial_hashjoin_path(root, joinrel,
2316  cheapest_partial_outer,
2317  cheapest_safe_inner,
2318  hashclauses, jointype, extra,
2319  false /* parallel_hash */ );
2320  }
2321  }
2322 }
2323 
2324 /*
2325  * select_mergejoin_clauses
2326  * Select mergejoin clauses that are usable for a particular join.
2327  * Returns a list of RestrictInfo nodes for those clauses.
2328  *
2329  * *mergejoin_allowed is normally set to true, but it is set to false if
2330  * this is a right/right-anti/full join and there are nonmergejoinable join
2331  * clauses. The executor's mergejoin machinery cannot handle such cases, so
2332  * we have to avoid generating a mergejoin plan. (Note that this flag does
2333  * NOT consider whether there are actually any mergejoinable clauses. This is
2334  * correct because in some cases we need to build a clauseless mergejoin.
2335  * Simply returning NIL is therefore not enough to distinguish safe from
2336  * unsafe cases.)
2337  *
2338  * We also mark each selected RestrictInfo to show which side is currently
2339  * being considered as outer. These are transient markings that are only
2340  * good for the duration of the current add_paths_to_joinrel() call!
2341  *
2342  * We examine each restrictinfo clause known for the join to see
2343  * if it is mergejoinable and involves vars from the two sub-relations
2344  * currently of interest.
2345  */
2346 static List *
2347 select_mergejoin_clauses(PlannerInfo *root,
2348  RelOptInfo *joinrel,
2349  RelOptInfo *outerrel,
2350  RelOptInfo *innerrel,
2351  List *restrictlist,
2352  JoinType jointype,
2353  bool *mergejoin_allowed)
2354 {
2355  List *result_list = NIL;
2356  bool isouterjoin = IS_OUTER_JOIN(jointype);
2357  bool have_nonmergeable_joinclause = false;
2358  ListCell *l;
2359 
2360  foreach(l, restrictlist)
2361  {
2362  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2363 
2364  /*
2365  * If processing an outer join, only use its own join clauses in the
2366  * merge. For inner joins we can use pushed-down clauses too. (Note:
2367  * we don't set have_nonmergeable_joinclause here because pushed-down
2368  * clauses will become otherquals not joinquals.)
2369  */
2370  if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))
2371  continue;
2372 
2373  /* Check that clause is a mergeable operator clause */
2374  if (!restrictinfo->can_join ||
2375  restrictinfo->mergeopfamilies == NIL)
2376  {
2377  /*
2378  * The executor can handle extra joinquals that are constants, but
2379  * not anything else, when doing right/right-anti/full merge join.
2380  * (The reason to support constants is so we can do FULL JOIN ON
2381  * FALSE.)
2382  */
2383  if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const))
2384  have_nonmergeable_joinclause = true;
2385  continue; /* not mergejoinable */
2386  }
2387 
2388  /*
2389  * Check if clause has the form "outer op inner" or "inner op outer".
2390  */
2391  if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
2392  {
2393  have_nonmergeable_joinclause = true;
2394  continue; /* no good for these input relations */
2395  }
2396 
2397  /*
2398  * Insist that each side have a non-redundant eclass. This
2399  * restriction is needed because various bits of the planner expect
2400  * that each clause in a merge be associable with some pathkey in a
2401  * canonical pathkey list, but redundant eclasses can't appear in
2402  * canonical sort orderings. (XXX it might be worth relaxing this,
2403  * but not enough time to address it for 8.3.)
2404  */
2405  update_mergeclause_eclasses(root, restrictinfo);
2406 
2407  if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) ||
2408  EC_MUST_BE_REDUNDANT(restrictinfo->right_ec))
2409  {
2410  have_nonmergeable_joinclause = true;
2411  continue; /* can't handle redundant eclasses */
2412  }
2413 
2414  result_list = lappend(result_list, restrictinfo);
2415  }
2416 
2417  /*
2418  * Report whether mergejoin is allowed (see comment at top of function).
2419  */
2420  switch (jointype)
2421  {
2422  case JOIN_RIGHT:
2423  case JOIN_RIGHT_ANTI:
2424  case JOIN_FULL:
2425  *mergejoin_allowed = !have_nonmergeable_joinclause;
2426  break;
2427  default:
2428  *mergejoin_allowed = true;
2429  break;
2430  }
2431 
2432  return result_list;
2433 }
innerrel_is_unique
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:1224
bms_join
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:1230
bms_is_subset
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
bms_free
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
bms_num_members
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:751
bms_is_member
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
bms_difference
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
bms_intersect
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
bms_add_members
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
bms_overlap
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
bms_nonempty_difference
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:641
bms_is_empty
#define bms_is_empty(a)
Definition: bitmapset.h:118
Assert
#define Assert(condition)
Definition: c.h:858
OidIsValid
#define OidIsValid(objectId)
Definition: c.h:775
contain_volatile_functions
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:538
initial_cost_mergejoin
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:3514
enable_memoize
bool enable_memoize
Definition: costsize.c:144
compute_semi_anti_join_factors
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:5004
enable_material
bool enable_material
Definition: costsize.c:143
initial_cost_hashjoin
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:4073
enable_hashjoin
bool enable_hashjoin
Definition: costsize.c:146
enable_mergejoin
bool enable_mergejoin
Definition: costsize.c:145
initial_cost_nestloop
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition: costsize.c:3233
enable_parallel_hash
bool enable_parallel_hash
Definition: costsize.c:151
ERROR
#define ERROR
Definition: elog.h:39
elog
#define elog(elevel,...)
Definition: elog.h:224
ExecMaterializesOutput
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:635
if
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
try_hashjoin_path
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1096
get_memoize_path
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:581
clause_sides_match_join
static bool clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, RelOptInfo *innerrel)
Definition: joinpath.c:1234
select_mergejoin_clauses
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2347
sort_inner_and_outer
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1266
add_paths_to_joinrel
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinpath.c:124
paraminfo_get_equal_hashops
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List **param_exprs, List **operators, bool *binary_mode)
Definition: joinpath.c:439
try_nestloop_path
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:721
consider_parallel_nestloop
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2009
PATH_PARAM_BY_PARENT
#define PATH_PARAM_BY_PARENT(path, rel)
Definition: joinpath.c:37
set_join_pathlist_hook
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:30
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)
Definition: joinpath.c:920
consider_parallel_mergejoin
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition: joinpath.c:1969
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)
Definition: joinpath.c:1469
hash_inner_and_outer
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2093
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)
Definition: joinpath.c:1026
PATH_PARAM_BY_REL
#define PATH_PARAM_BY_REL(path, rel)
Definition: joinpath.c:43
allow_star_schema_join
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition: joinpath.c:363
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)
Definition: joinpath.c:1173
match_unsorted_outer
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1717
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)
Definition: joinpath.c:843
have_dangerous_phv
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1304
list_truncate
List * list_truncate(List *list, int new_size)
Definition: list.c:631
lappend
List * lappend(List *list, void *datum)
Definition: list.c:339
lappend_oid
List * lappend_oid(List *list, Oid datum)
Definition: list.c:375
list_copy
List * list_copy(const List *oldlist)
Definition: list.c:1573
list_delete_nth_cell
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:767
list_free
void list_free(List *list)
Definition: list.c:1546
list_member
bool list_member(const List *list, const void *datum)
Definition: list.c:661
lcons
List * lcons(void *datum, List *list)
Definition: list.c:495
exprType
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
IsA
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
IS_OUTER_JOIN
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:337
JoinType
JoinType
Definition: nodes.h:288
JOIN_SEMI
@ JOIN_SEMI
Definition: nodes.h:307
JOIN_FULL
@ JOIN_FULL
Definition: nodes.h:295
JOIN_INNER
@ JOIN_INNER
Definition: nodes.h:293
JOIN_RIGHT
@ JOIN_RIGHT
Definition: nodes.h:296
JOIN_LEFT
@ JOIN_LEFT
Definition: nodes.h:294
JOIN_UNIQUE_OUTER
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:315
JOIN_RIGHT_ANTI
@ JOIN_RIGHT_ANTI
Definition: nodes.h:309
JOIN_UNIQUE_INNER
@ JOIN_UNIQUE_INNER
Definition: nodes.h:316
JOIN_ANTI
@ JOIN_ANTI
Definition: nodes.h:308
build_join_pathkeys
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition: pathkeys.c:1309
make_inner_pathkeys_for_merge
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition: pathkeys.c:1838
get_cheapest_path_for_pathkeys
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition: pathkeys.c:635
find_mergeclauses_for_outer_pathkeys
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition: pathkeys.c:1527
trim_mergeclauses_for_inner_pathkeys
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition: pathkeys.c:1941
select_outer_pathkeys_for_merge
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition: pathkeys.c:1642
update_mergeclause_eclasses
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1493
get_cheapest_parallel_safe_total_inner
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:714
pathkeys_contained_in
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:341
create_nestloop_path
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:2457
calc_non_nestloop_required_outer
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition: pathnode.c:2405
create_unique_path
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1654
path_is_reparameterizable_by_child
bool path_is_reparameterizable_by_child(Path *path, RelOptInfo *child_rel)
Definition: pathnode.c:4408
calc_nestloop_required_outer
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition: pathnode.c:2378
create_mergejoin_path
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:2553
create_memoize_path
MemoizePath * create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, bool binary_mode, double calls)
Definition: pathnode.c:1598
add_partial_path
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:747
create_material_path
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath)
Definition: pathnode.c:1566
create_hashjoin_path
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:2619
add_partial_path_precheck
bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys)
Definition: pathnode.c:865
add_path
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:420
compare_path_costs
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:69
add_path_precheck
bool add_path_precheck(RelOptInfo *parent_rel, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition: pathnode.c:642
EC_MUST_BE_REDUNDANT
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:1399
RINFO_IS_PUSHED_DOWN
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2709
TOTAL_COST
@ TOTAL_COST
Definition: pathnodes.h:38
STARTUP_COST
@ STARTUP_COST
Definition: pathnodes.h:38
PATH_REQ_OUTER
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1658
RELOPT_OTHER_JOINREL
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:820
set_join_pathlist_hook_type
void(* set_join_pathlist_hook_type)(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: paths.h:37
lfirst
#define lfirst(lc)
Definition: pg_list.h:172
list_length
static int list_length(const List *l)
Definition: pg_list.h:152
NIL
#define NIL
Definition: pg_list.h:68
foreach_current_index
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403
list_head
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
linitial
#define linitial(l)
Definition: pg_list.h:178
lsecond
#define lsecond(l)
Definition: pg_list.h:183
InvalidOid
#define InvalidOid
Definition: postgres_ext.h:36
Oid
unsigned int Oid
Definition: postgres_ext.h:31
root
tree ctl root
Definition: radixtree.h:1884
JoinPathExtraData::mergeclause_list
List * mergeclause_list
Definition: pathnodes.h:3219
JoinPathExtraData::param_source_rels
Relids param_source_rels
Definition: pathnodes.h:3223
JoinPathExtraData::semifactors
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3222
JoinPathExtraData::sjinfo
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3221
List
Definition: pg_list.h:54
Node
Definition: nodes.h:129
OpExpr::args
List * args
Definition: primnodes.h:806
ParamPathInfo::ppi_clauses
List * ppi_clauses
Definition: pathnodes.h:1570
Path::pathkeys
List * pathkeys
Definition: pathnodes.h:1654
Path::pathtype
NodeTag pathtype
Definition: pathnodes.h:1615
Path::rows
Cardinality rows
Definition: pathnodes.h:1649
Path::parallel_safe
bool parallel_safe
Definition: pathnodes.h:1644
RelOptInfo::baserestrictinfo
List * baserestrictinfo
Definition: pathnodes.h:975
RelOptInfo::relids
Relids relids
Definition: pathnodes.h:861
RelOptInfo::reltarget
struct PathTarget * reltarget
Definition: pathnodes.h:883
RelOptInfo::lateral_vars
List * lateral_vars
Definition: pathnodes.h:930
RelOptInfo::consider_parallel
bool consider_parallel
Definition: pathnodes.h:877
RelOptInfo::top_parent_relids
Relids top_parent_relids
Definition: pathnodes.h:999
RelOptInfo::lateral_relids
Relids lateral_relids
Definition: pathnodes.h:903
RelOptInfo::cheapest_parameterized_paths
List * cheapest_parameterized_paths
Definition: pathnodes.h:894
RelOptInfo::pathlist
List * pathlist
Definition: pathnodes.h:888
RelOptInfo::reloptkind
RelOptKind reloptkind
Definition: pathnodes.h:855
RelOptInfo::cheapest_startup_path
struct Path * cheapest_startup_path
Definition: pathnodes.h:891
RelOptInfo::cheapest_total_path
struct Path * cheapest_total_path
Definition: pathnodes.h:892
RelOptInfo::partial_pathlist
List * partial_pathlist
Definition: pathnodes.h:890
RestrictInfo::clause
Expr * clause
Definition: pathnodes.h:2552
SpecialJoinInfo::min_righthand
Relids min_righthand
Definition: pathnodes.h:2883
SpecialJoinInfo::jointype
JoinType jointype
Definition: pathnodes.h:2886
SpecialJoinInfo::min_lefthand
Relids min_lefthand
Definition: pathnodes.h:2882
lookup_type_cache
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:346
TYPECACHE_EQ_OPR
#define TYPECACHE_EQ_OPR
Definition: typcache.h:137
TYPECACHE_HASH_PROC
#define TYPECACHE_HASH_PROC
Definition: typcache.h:141