PostgreSQL Source Code  git master
joinrels.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * joinrels.c
4  * Routines to determine which relations should be joined
5  *
6  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/path/joinrels.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include "miscadmin.h"
18 #include "optimizer/clauses.h"
19 #include "optimizer/joininfo.h"
20 #include "optimizer/pathnode.h"
21 #include "optimizer/paths.h"
22 #include "optimizer/prep.h"
24 #include "utils/lsyscache.h"
25 #include "utils/memutils.h"
26 
27 
28 static void make_rels_by_clause_joins(PlannerInfo *root,
29  RelOptInfo *old_rel,
30  ListCell *other_rels);
32  RelOptInfo *old_rel,
33  ListCell *other_rels);
34 static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
35 static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
36 static bool is_dummy_rel(RelOptInfo *rel);
37 static bool restriction_is_constant_false(List *restrictlist,
38  RelOptInfo *joinrel,
39  bool only_pushed_down);
40 static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
41  RelOptInfo *rel2, RelOptInfo *joinrel,
42  SpecialJoinInfo *sjinfo, List *restrictlist);
43 static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1,
44  RelOptInfo *rel2, RelOptInfo *joinrel,
45  SpecialJoinInfo *parent_sjinfo,
46  List *parent_restrictlist);
47 static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel,
48  bool strict_op);
49 
50 
51 /*
52  * join_search_one_level
53  * Consider ways to produce join relations containing exactly 'level'
54  * jointree items. (This is one step of the dynamic-programming method
55  * embodied in standard_join_search.) Join rel nodes for each feasible
56  * combination of lower-level rels are created and returned in a list.
57  * Implementation paths are created for each such joinrel, too.
58  *
59  * level: level of rels we want to make this time
60  * root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
61  *
62  * The result is returned in root->join_rel_level[level].
63  */
64 void
66 {
67  List **joinrels = root->join_rel_level;
68  ListCell *r;
69  int k;
70 
71  Assert(joinrels[level] == NIL);
72 
73  /* Set join_cur_level so that new joinrels are added to proper list */
74  root->join_cur_level = level;
75 
76  /*
77  * First, consider left-sided and right-sided plans, in which rels of
78  * exactly level-1 member relations are joined against initial relations.
79  * We prefer to join using join clauses, but if we find a rel of level-1
80  * members that has no join clauses, we will generate Cartesian-product
81  * joins against all initial rels not already contained in it.
82  */
83  foreach(r, joinrels[level - 1])
84  {
85  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
86 
87  if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
88  has_join_restriction(root, old_rel))
89  {
90  /*
91  * There are join clauses or join order restrictions relevant to
92  * this rel, so consider joins between this rel and (only) those
93  * initial rels it is linked to by a clause or restriction.
94  *
95  * At level 2 this condition is symmetric, so there is no need to
96  * look at initial rels before this one in the list; we already
97  * considered such joins when we were at the earlier rel. (The
98  * mirror-image joins are handled automatically by make_join_rel.)
99  * In later passes (level > 2), we join rels of the previous level
100  * to each initial rel they don't already include but have a join
101  * clause or restriction with.
102  */
103  ListCell *other_rels;
104 
105  if (level == 2) /* consider remaining initial rels */
106  other_rels = lnext(r);
107  else /* consider all initial rels */
108  other_rels = list_head(joinrels[1]);
109 
111  old_rel,
112  other_rels);
113  }
114  else
115  {
116  /*
117  * Oops, we have a relation that is not joined to any other
118  * relation, either directly or by join-order restrictions.
119  * Cartesian product time.
120  *
121  * We consider a cartesian product with each not-already-included
122  * initial rel, whether it has other join clauses or not. At
123  * level 2, if there are two or more clauseless initial rels, we
124  * will redundantly consider joining them in both directions; but
125  * such cases aren't common enough to justify adding complexity to
126  * avoid the duplicated effort.
127  */
129  old_rel,
130  list_head(joinrels[1]));
131  }
132  }
133 
134  /*
135  * Now, consider "bushy plans" in which relations of k initial rels are
136  * joined to relations of level-k initial rels, for 2 <= k <= level-2.
137  *
138  * We only consider bushy-plan joins for pairs of rels where there is a
139  * suitable join clause (or join order restriction), in order to avoid
140  * unreasonable growth of planning time.
141  */
142  for (k = 2;; k++)
143  {
144  int other_level = level - k;
145 
146  /*
147  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
148  * need to go as far as the halfway point.
149  */
150  if (k > other_level)
151  break;
152 
153  foreach(r, joinrels[k])
154  {
155  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
156  ListCell *other_rels;
157  ListCell *r2;
158 
159  /*
160  * We can ignore relations without join clauses here, unless they
161  * participate in join-order restrictions --- then we might have
162  * to force a bushy join plan.
163  */
164  if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
165  !has_join_restriction(root, old_rel))
166  continue;
167 
168  if (k == other_level)
169  other_rels = lnext(r); /* only consider remaining rels */
170  else
171  other_rels = list_head(joinrels[other_level]);
172 
173  for_each_cell(r2, other_rels)
174  {
175  RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
176 
177  if (!bms_overlap(old_rel->relids, new_rel->relids))
178  {
179  /*
180  * OK, we can build a rel of the right level from this
181  * pair of rels. Do so if there is at least one relevant
182  * join clause or join order restriction.
183  */
184  if (have_relevant_joinclause(root, old_rel, new_rel) ||
185  have_join_order_restriction(root, old_rel, new_rel))
186  {
187  (void) make_join_rel(root, old_rel, new_rel);
188  }
189  }
190  }
191  }
192  }
193 
194  /*----------
195  * Last-ditch effort: if we failed to find any usable joins so far, force
196  * a set of cartesian-product joins to be generated. This handles the
197  * special case where all the available rels have join clauses but we
198  * cannot use any of those clauses yet. This can only happen when we are
199  * considering a join sub-problem (a sub-joinlist) and all the rels in the
200  * sub-problem have only join clauses with rels outside the sub-problem.
201  * An example is
202  *
203  * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
204  * WHERE a.w = c.x and b.y = d.z;
205  *
206  * If the "a INNER JOIN b" sub-problem does not get flattened into the
207  * upper level, we must be willing to make a cartesian join of a and b;
208  * but the code above will not have done so, because it thought that both
209  * a and b have joinclauses. We consider only left-sided and right-sided
210  * cartesian joins in this case (no bushy).
211  *----------
212  */
213  if (joinrels[level] == NIL)
214  {
215  /*
216  * This loop is just like the first one, except we always call
217  * make_rels_by_clauseless_joins().
218  */
219  foreach(r, joinrels[level - 1])
220  {
221  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
222 
224  old_rel,
225  list_head(joinrels[1]));
226  }
227 
228  /*----------
229  * When special joins are involved, there may be no legal way
230  * to make an N-way join for some values of N. For example consider
231  *
232  * SELECT ... FROM t1 WHERE
233  * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
234  * y IN (SELECT ... FROM t4,t5 WHERE ...)
235  *
236  * We will flatten this query to a 5-way join problem, but there are
237  * no 4-way joins that join_is_legal() will consider legal. We have
238  * to accept failure at level 4 and go on to discover a workable
239  * bushy plan at level 5.
240  *
241  * However, if there are no special joins and no lateral references
242  * then join_is_legal() should never fail, and so the following sanity
243  * check is useful.
244  *----------
245  */
246  if (joinrels[level] == NIL &&
247  root->join_info_list == NIL &&
248  !root->hasLateralRTEs)
249  elog(ERROR, "failed to build any %d-way joins", level);
250  }
251 }
252 
253 /*
254  * make_rels_by_clause_joins
255  * Build joins between the given relation 'old_rel' and other relations
256  * that participate in join clauses that 'old_rel' also participates in
257  * (or participate in join-order restrictions with it).
258  * The join rels are returned in root->join_rel_level[join_cur_level].
259  *
260  * Note: at levels above 2 we will generate the same joined relation in
261  * multiple ways --- for example (a join b) join c is the same RelOptInfo as
262  * (b join c) join a, though the second case will add a different set of Paths
263  * to it. This is the reason for using the join_rel_level mechanism, which
264  * automatically ensures that each new joinrel is only added to the list once.
265  *
266  * 'old_rel' is the relation entry for the relation to be joined
267  * 'other_rels': the first cell in a linked list containing the other
268  * rels to be considered for joining
269  *
270  * Currently, this is only used with initial rels in other_rels, but it
271  * will work for joining to joinrels too.
272  */
273 static void
275  RelOptInfo *old_rel,
276  ListCell *other_rels)
277 {
278  ListCell *l;
279 
280  for_each_cell(l, other_rels)
281  {
282  RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
283 
284  if (!bms_overlap(old_rel->relids, other_rel->relids) &&
285  (have_relevant_joinclause(root, old_rel, other_rel) ||
286  have_join_order_restriction(root, old_rel, other_rel)))
287  {
288  (void) make_join_rel(root, old_rel, other_rel);
289  }
290  }
291 }
292 
293 /*
294  * make_rels_by_clauseless_joins
295  * Given a relation 'old_rel' and a list of other relations
296  * 'other_rels', create a join relation between 'old_rel' and each
297  * member of 'other_rels' that isn't already included in 'old_rel'.
298  * The join rels are returned in root->join_rel_level[join_cur_level].
299  *
300  * 'old_rel' is the relation entry for the relation to be joined
301  * 'other_rels': the first cell of a linked list containing the
302  * other rels to be considered for joining
303  *
304  * Currently, this is only used with initial rels in other_rels, but it would
305  * work for joining to joinrels too.
306  */
307 static void
309  RelOptInfo *old_rel,
310  ListCell *other_rels)
311 {
312  ListCell *l;
313 
314  for_each_cell(l, other_rels)
315  {
316  RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
317 
318  if (!bms_overlap(other_rel->relids, old_rel->relids))
319  {
320  (void) make_join_rel(root, old_rel, other_rel);
321  }
322  }
323 }
324 
325 
326 /*
327  * join_is_legal
328  * Determine whether a proposed join is legal given the query's
329  * join order constraints; and if it is, determine the join type.
330  *
331  * Caller must supply not only the two rels, but the union of their relids.
332  * (We could simplify the API by computing joinrelids locally, but this
333  * would be redundant work in the normal path through make_join_rel.)
334  *
335  * On success, *sjinfo_p is set to NULL if this is to be a plain inner join,
336  * else it's set to point to the associated SpecialJoinInfo node. Also,
337  * *reversed_p is set true if the given relations need to be swapped to
338  * match the SpecialJoinInfo node.
339  */
340 static bool
342  Relids joinrelids,
343  SpecialJoinInfo **sjinfo_p, bool *reversed_p)
344 {
345  SpecialJoinInfo *match_sjinfo;
346  bool reversed;
347  bool unique_ified;
348  bool must_be_leftjoin;
349  ListCell *l;
350 
351  /*
352  * Ensure output params are set on failure return. This is just to
353  * suppress uninitialized-variable warnings from overly anal compilers.
354  */
355  *sjinfo_p = NULL;
356  *reversed_p = false;
357 
358  /*
359  * If we have any special joins, the proposed join might be illegal; and
360  * in any case we have to determine its join type. Scan the join info
361  * list for matches and conflicts.
362  */
363  match_sjinfo = NULL;
364  reversed = false;
365  unique_ified = false;
366  must_be_leftjoin = false;
367 
368  foreach(l, root->join_info_list)
369  {
370  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
371 
372  /*
373  * This special join is not relevant unless its RHS overlaps the
374  * proposed join. (Check this first as a fast path for dismissing
375  * most irrelevant SJs quickly.)
376  */
377  if (!bms_overlap(sjinfo->min_righthand, joinrelids))
378  continue;
379 
380  /*
381  * Also, not relevant if proposed join is fully contained within RHS
382  * (ie, we're still building up the RHS).
383  */
384  if (bms_is_subset(joinrelids, sjinfo->min_righthand))
385  continue;
386 
387  /*
388  * Also, not relevant if SJ is already done within either input.
389  */
390  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
391  bms_is_subset(sjinfo->min_righthand, rel1->relids))
392  continue;
393  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
394  bms_is_subset(sjinfo->min_righthand, rel2->relids))
395  continue;
396 
397  /*
398  * If it's a semijoin and we already joined the RHS to any other rels
399  * within either input, then we must have unique-ified the RHS at that
400  * point (see below). Therefore the semijoin is no longer relevant in
401  * this join path.
402  */
403  if (sjinfo->jointype == JOIN_SEMI)
404  {
405  if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
406  !bms_equal(sjinfo->syn_righthand, rel1->relids))
407  continue;
408  if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
409  !bms_equal(sjinfo->syn_righthand, rel2->relids))
410  continue;
411  }
412 
413  /*
414  * If one input contains min_lefthand and the other contains
415  * min_righthand, then we can perform the SJ at this join.
416  *
417  * Reject if we get matches to more than one SJ; that implies we're
418  * considering something that's not really valid.
419  */
420  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
421  bms_is_subset(sjinfo->min_righthand, rel2->relids))
422  {
423  if (match_sjinfo)
424  return false; /* invalid join path */
425  match_sjinfo = sjinfo;
426  reversed = false;
427  }
428  else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
429  bms_is_subset(sjinfo->min_righthand, rel1->relids))
430  {
431  if (match_sjinfo)
432  return false; /* invalid join path */
433  match_sjinfo = sjinfo;
434  reversed = true;
435  }
436  else if (sjinfo->jointype == JOIN_SEMI &&
437  bms_equal(sjinfo->syn_righthand, rel2->relids) &&
438  create_unique_path(root, rel2, rel2->cheapest_total_path,
439  sjinfo) != NULL)
440  {
441  /*----------
442  * For a semijoin, we can join the RHS to anything else by
443  * unique-ifying the RHS (if the RHS can be unique-ified).
444  * We will only get here if we have the full RHS but less
445  * than min_lefthand on the LHS.
446  *
447  * The reason to consider such a join path is exemplified by
448  * SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
449  * If we insist on doing this as a semijoin we will first have
450  * to form the cartesian product of A*B. But if we unique-ify
451  * C then the semijoin becomes a plain innerjoin and we can join
452  * in any order, eg C to A and then to B. When C is much smaller
453  * than A and B this can be a huge win. So we allow C to be
454  * joined to just A or just B here, and then make_join_rel has
455  * to handle the case properly.
456  *
457  * Note that actually we'll allow unique-ified C to be joined to
458  * some other relation D here, too. That is legal, if usually not
459  * very sane, and this routine is only concerned with legality not
460  * with whether the join is good strategy.
461  *----------
462  */
463  if (match_sjinfo)
464  return false; /* invalid join path */
465  match_sjinfo = sjinfo;
466  reversed = false;
467  unique_ified = true;
468  }
469  else if (sjinfo->jointype == JOIN_SEMI &&
470  bms_equal(sjinfo->syn_righthand, rel1->relids) &&
471  create_unique_path(root, rel1, rel1->cheapest_total_path,
472  sjinfo) != NULL)
473  {
474  /* Reversed semijoin case */
475  if (match_sjinfo)
476  return false; /* invalid join path */
477  match_sjinfo = sjinfo;
478  reversed = true;
479  unique_ified = true;
480  }
481  else
482  {
483  /*
484  * Otherwise, the proposed join overlaps the RHS but isn't a valid
485  * implementation of this SJ. But don't panic quite yet: the RHS
486  * violation might have occurred previously, in one or both input
487  * relations, in which case we must have previously decided that
488  * it was OK to commute some other SJ with this one. If we need
489  * to perform this join to finish building up the RHS, rejecting
490  * it could lead to not finding any plan at all. (This can occur
491  * because of the heuristics elsewhere in this file that postpone
492  * clauseless joins: we might not consider doing a clauseless join
493  * within the RHS until after we've performed other, validly
494  * commutable SJs with one or both sides of the clauseless join.)
495  * This consideration boils down to the rule that if both inputs
496  * overlap the RHS, we can allow the join --- they are either
497  * fully within the RHS, or represent previously-allowed joins to
498  * rels outside it.
499  */
500  if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
501  bms_overlap(rel2->relids, sjinfo->min_righthand))
502  continue; /* assume valid previous violation of RHS */
503 
504  /*
505  * The proposed join could still be legal, but only if we're
506  * allowed to associate it into the RHS of this SJ. That means
507  * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
508  * not FULL) and the proposed join must not overlap the LHS.
509  */
510  if (sjinfo->jointype != JOIN_LEFT ||
511  bms_overlap(joinrelids, sjinfo->min_lefthand))
512  return false; /* invalid join path */
513 
514  /*
515  * To be valid, the proposed join must be a LEFT join; otherwise
516  * it can't associate into this SJ's RHS. But we may not yet have
517  * found the SpecialJoinInfo matching the proposed join, so we
518  * can't test that yet. Remember the requirement for later.
519  */
520  must_be_leftjoin = true;
521  }
522  }
523 
524  /*
525  * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
526  * proposed join can't associate into an SJ's RHS.
527  *
528  * Also, fail if the proposed join's predicate isn't strict; we're
529  * essentially checking to see if we can apply outer-join identity 3, and
530  * that's a requirement. (This check may be redundant with checks in
531  * make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
532  */
533  if (must_be_leftjoin &&
534  (match_sjinfo == NULL ||
535  match_sjinfo->jointype != JOIN_LEFT ||
536  !match_sjinfo->lhs_strict))
537  return false; /* invalid join path */
538 
539  /*
540  * We also have to check for constraints imposed by LATERAL references.
541  */
542  if (root->hasLateralRTEs)
543  {
544  bool lateral_fwd;
545  bool lateral_rev;
546  Relids join_lateral_rels;
547 
548  /*
549  * The proposed rels could each contain lateral references to the
550  * other, in which case the join is impossible. If there are lateral
551  * references in just one direction, then the join has to be done with
552  * a nestloop with the lateral referencer on the inside. If the join
553  * matches an SJ that cannot be implemented by such a nestloop, the
554  * join is impossible.
555  *
556  * Also, if the lateral reference is only indirect, we should reject
557  * the join; whatever rel(s) the reference chain goes through must be
558  * joined to first.
559  *
560  * Another case that might keep us from building a valid plan is the
561  * implementation restriction described by have_dangerous_phv().
562  */
563  lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids);
564  lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids);
565  if (lateral_fwd && lateral_rev)
566  return false; /* have lateral refs in both directions */
567  if (lateral_fwd)
568  {
569  /* has to be implemented as nestloop with rel1 on left */
570  if (match_sjinfo &&
571  (reversed ||
572  unique_ified ||
573  match_sjinfo->jointype == JOIN_FULL))
574  return false; /* not implementable as nestloop */
575  /* check there is a direct reference from rel2 to rel1 */
576  if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids))
577  return false; /* only indirect refs, so reject */
578  /* check we won't have a dangerous PHV */
579  if (have_dangerous_phv(root, rel1->relids, rel2->lateral_relids))
580  return false; /* might be unable to handle required PHV */
581  }
582  else if (lateral_rev)
583  {
584  /* has to be implemented as nestloop with rel2 on left */
585  if (match_sjinfo &&
586  (!reversed ||
587  unique_ified ||
588  match_sjinfo->jointype == JOIN_FULL))
589  return false; /* not implementable as nestloop */
590  /* check there is a direct reference from rel1 to rel2 */
591  if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids))
592  return false; /* only indirect refs, so reject */
593  /* check we won't have a dangerous PHV */
594  if (have_dangerous_phv(root, rel2->relids, rel1->lateral_relids))
595  return false; /* might be unable to handle required PHV */
596  }
597 
598  /*
599  * LATERAL references could also cause problems later on if we accept
600  * this join: if the join's minimum parameterization includes any rels
601  * that would have to be on the inside of an outer join with this join
602  * rel, then it's never going to be possible to build the complete
603  * query using this join. We should reject this join not only because
604  * it'll save work, but because if we don't, the clauseless-join
605  * heuristics might think that legality of this join means that some
606  * other join rel need not be formed, and that could lead to failure
607  * to find any plan at all. We have to consider not only rels that
608  * are directly on the inner side of an OJ with the joinrel, but also
609  * ones that are indirectly so, so search to find all such rels.
610  */
611  join_lateral_rels = min_join_parameterization(root, joinrelids,
612  rel1, rel2);
613  if (join_lateral_rels)
614  {
615  Relids join_plus_rhs = bms_copy(joinrelids);
616  bool more;
617 
618  do
619  {
620  more = false;
621  foreach(l, root->join_info_list)
622  {
623  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
624 
625  if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) &&
626  !bms_is_subset(sjinfo->min_righthand, join_plus_rhs))
627  {
628  join_plus_rhs = bms_add_members(join_plus_rhs,
629  sjinfo->min_righthand);
630  more = true;
631  }
632  /* full joins constrain both sides symmetrically */
633  if (sjinfo->jointype == JOIN_FULL &&
634  bms_overlap(sjinfo->min_righthand, join_plus_rhs) &&
635  !bms_is_subset(sjinfo->min_lefthand, join_plus_rhs))
636  {
637  join_plus_rhs = bms_add_members(join_plus_rhs,
638  sjinfo->min_lefthand);
639  more = true;
640  }
641  }
642  } while (more);
643  if (bms_overlap(join_plus_rhs, join_lateral_rels))
644  return false; /* will not be able to join to some RHS rel */
645  }
646  }
647 
648  /* Otherwise, it's a valid join */
649  *sjinfo_p = match_sjinfo;
650  *reversed_p = reversed;
651  return true;
652 }
653 
654 
655 /*
656  * make_join_rel
657  * Find or create a join RelOptInfo that represents the join of
658  * the two given rels, and add to it path information for paths
659  * created with the two rels as outer and inner rel.
660  * (The join rel may already contain paths generated from other
661  * pairs of rels that add up to the same set of base rels.)
662  *
663  * NB: will return NULL if attempted join is not valid. This can happen
664  * when working with outer joins, or with IN or EXISTS clauses that have been
665  * turned into joins.
666  */
667 RelOptInfo *
669 {
670  Relids joinrelids;
671  SpecialJoinInfo *sjinfo;
672  bool reversed;
673  SpecialJoinInfo sjinfo_data;
674  RelOptInfo *joinrel;
675  List *restrictlist;
676 
677  /* We should never try to join two overlapping sets of rels. */
678  Assert(!bms_overlap(rel1->relids, rel2->relids));
679 
680  /* Construct Relids set that identifies the joinrel. */
681  joinrelids = bms_union(rel1->relids, rel2->relids);
682 
683  /* Check validity and determine join type. */
684  if (!join_is_legal(root, rel1, rel2, joinrelids,
685  &sjinfo, &reversed))
686  {
687  /* invalid join path */
688  bms_free(joinrelids);
689  return NULL;
690  }
691 
692  /* Swap rels if needed to match the join info. */
693  if (reversed)
694  {
695  RelOptInfo *trel = rel1;
696 
697  rel1 = rel2;
698  rel2 = trel;
699  }
700 
701  /*
702  * If it's a plain inner join, then we won't have found anything in
703  * join_info_list. Make up a SpecialJoinInfo so that selectivity
704  * estimation functions will know what's being joined.
705  */
706  if (sjinfo == NULL)
707  {
708  sjinfo = &sjinfo_data;
709  sjinfo->type = T_SpecialJoinInfo;
710  sjinfo->min_lefthand = rel1->relids;
711  sjinfo->min_righthand = rel2->relids;
712  sjinfo->syn_lefthand = rel1->relids;
713  sjinfo->syn_righthand = rel2->relids;
714  sjinfo->jointype = JOIN_INNER;
715  /* we don't bother trying to make the remaining fields valid */
716  sjinfo->lhs_strict = false;
717  sjinfo->delay_upper_joins = false;
718  sjinfo->semi_can_btree = false;
719  sjinfo->semi_can_hash = false;
720  sjinfo->semi_operators = NIL;
721  sjinfo->semi_rhs_exprs = NIL;
722  }
723 
724  /*
725  * Find or build the join RelOptInfo, and compute the restrictlist that
726  * goes with this particular joining.
727  */
728  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
729  &restrictlist);
730 
731  /*
732  * If we've already proven this join is empty, we needn't consider any
733  * more paths for it.
734  */
735  if (is_dummy_rel(joinrel))
736  {
737  bms_free(joinrelids);
738  return joinrel;
739  }
740 
741  /* Add paths to the join relation. */
742  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
743  restrictlist);
744 
745  bms_free(joinrelids);
746 
747  return joinrel;
748 }
749 
750 /*
751  * populate_joinrel_with_paths
752  * Add paths to the given joinrel for given pair of joining relations. The
753  * SpecialJoinInfo provides details about the join and the restrictlist
754  * contains the join clauses and the other clauses applicable for given pair
755  * of the joining relations.
756  */
757 static void
759  RelOptInfo *rel2, RelOptInfo *joinrel,
760  SpecialJoinInfo *sjinfo, List *restrictlist)
761 {
762  /*
763  * Consider paths using each rel as both outer and inner. Depending on
764  * the join type, a provably empty outer or inner rel might mean the join
765  * is provably empty too; in which case throw away any previously computed
766  * paths and mark the join as dummy. (We do it this way since it's
767  * conceivable that dummy-ness of a multi-element join might only be
768  * noticeable for certain construction paths.)
769  *
770  * Also, a provably constant-false join restriction typically means that
771  * we can skip evaluating one or both sides of the join. We do this by
772  * marking the appropriate rel as dummy. For outer joins, a
773  * constant-false restriction that is pushed down still means the whole
774  * join is dummy, while a non-pushed-down one means that no inner rows
775  * will join so we can treat the inner rel as dummy.
776  *
777  * We need only consider the jointypes that appear in join_info_list, plus
778  * JOIN_INNER.
779  */
780  switch (sjinfo->jointype)
781  {
782  case JOIN_INNER:
783  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
784  restriction_is_constant_false(restrictlist, joinrel, false))
785  {
786  mark_dummy_rel(joinrel);
787  break;
788  }
789  add_paths_to_joinrel(root, joinrel, rel1, rel2,
790  JOIN_INNER, sjinfo,
791  restrictlist);
792  add_paths_to_joinrel(root, joinrel, rel2, rel1,
793  JOIN_INNER, sjinfo,
794  restrictlist);
795  break;
796  case JOIN_LEFT:
797  if (is_dummy_rel(rel1) ||
798  restriction_is_constant_false(restrictlist, joinrel, true))
799  {
800  mark_dummy_rel(joinrel);
801  break;
802  }
803  if (restriction_is_constant_false(restrictlist, joinrel, false) &&
804  bms_is_subset(rel2->relids, sjinfo->syn_righthand))
805  mark_dummy_rel(rel2);
806  add_paths_to_joinrel(root, joinrel, rel1, rel2,
807  JOIN_LEFT, sjinfo,
808  restrictlist);
809  add_paths_to_joinrel(root, joinrel, rel2, rel1,
810  JOIN_RIGHT, sjinfo,
811  restrictlist);
812  break;
813  case JOIN_FULL:
814  if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
815  restriction_is_constant_false(restrictlist, joinrel, true))
816  {
817  mark_dummy_rel(joinrel);
818  break;
819  }
820  add_paths_to_joinrel(root, joinrel, rel1, rel2,
821  JOIN_FULL, sjinfo,
822  restrictlist);
823  add_paths_to_joinrel(root, joinrel, rel2, rel1,
824  JOIN_FULL, sjinfo,
825  restrictlist);
826 
827  /*
828  * If there are join quals that aren't mergeable or hashable, we
829  * may not be able to build any valid plan. Complain here so that
830  * we can give a somewhat-useful error message. (Since we have no
831  * flexibility of planning for a full join, there's no chance of
832  * succeeding later with another pair of input rels.)
833  */
834  if (joinrel->pathlist == NIL)
835  ereport(ERROR,
836  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
837  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
838  break;
839  case JOIN_SEMI:
840 
841  /*
842  * We might have a normal semijoin, or a case where we don't have
843  * enough rels to do the semijoin but can unique-ify the RHS and
844  * then do an innerjoin (see comments in join_is_legal). In the
845  * latter case we can't apply JOIN_SEMI joining.
846  */
847  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
848  bms_is_subset(sjinfo->min_righthand, rel2->relids))
849  {
850  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
851  restriction_is_constant_false(restrictlist, joinrel, false))
852  {
853  mark_dummy_rel(joinrel);
854  break;
855  }
856  add_paths_to_joinrel(root, joinrel, rel1, rel2,
857  JOIN_SEMI, sjinfo,
858  restrictlist);
859  }
860 
861  /*
862  * If we know how to unique-ify the RHS and one input rel is
863  * exactly the RHS (not a superset) we can consider unique-ifying
864  * it and then doing a regular join. (The create_unique_path
865  * check here is probably redundant with what join_is_legal did,
866  * but if so the check is cheap because it's cached. So test
867  * anyway to be sure.)
868  */
869  if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
870  create_unique_path(root, rel2, rel2->cheapest_total_path,
871  sjinfo) != NULL)
872  {
873  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
874  restriction_is_constant_false(restrictlist, joinrel, false))
875  {
876  mark_dummy_rel(joinrel);
877  break;
878  }
879  add_paths_to_joinrel(root, joinrel, rel1, rel2,
880  JOIN_UNIQUE_INNER, sjinfo,
881  restrictlist);
882  add_paths_to_joinrel(root, joinrel, rel2, rel1,
883  JOIN_UNIQUE_OUTER, sjinfo,
884  restrictlist);
885  }
886  break;
887  case JOIN_ANTI:
888  if (is_dummy_rel(rel1) ||
889  restriction_is_constant_false(restrictlist, joinrel, true))
890  {
891  mark_dummy_rel(joinrel);
892  break;
893  }
894  if (restriction_is_constant_false(restrictlist, joinrel, false) &&
895  bms_is_subset(rel2->relids, sjinfo->syn_righthand))
896  mark_dummy_rel(rel2);
897  add_paths_to_joinrel(root, joinrel, rel1, rel2,
898  JOIN_ANTI, sjinfo,
899  restrictlist);
900  break;
901  default:
902  /* other values not expected here */
903  elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
904  break;
905  }
906 
907  /* Apply partitionwise join technique, if possible. */
908  try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist);
909 }
910 
911 
912 /*
913  * have_join_order_restriction
914  * Detect whether the two relations should be joined to satisfy
915  * a join-order restriction arising from special or lateral joins.
916  *
917  * In practice this is always used with have_relevant_joinclause(), and so
918  * could be merged with that function, but it seems clearer to separate the
919  * two concerns. We need this test because there are degenerate cases where
920  * a clauseless join must be performed to satisfy join-order restrictions.
921  * Also, if one rel has a lateral reference to the other, or both are needed
922  * to compute some PHV, we should consider joining them even if the join would
923  * be clauseless.
924  *
925  * Note: this is only a problem if one side of a degenerate outer join
926  * contains multiple rels, or a clauseless join is required within an
927  * IN/EXISTS RHS; else we will find a join path via the "last ditch" case in
928  * join_search_one_level(). We could dispense with this test if we were
929  * willing to try bushy plans in the "last ditch" case, but that seems much
930  * less efficient.
931  */
932 bool
934  RelOptInfo *rel1, RelOptInfo *rel2)
935 {
936  bool result = false;
937  ListCell *l;
938 
939  /*
940  * If either side has a direct lateral reference to the other, attempt the
941  * join regardless of outer-join considerations.
942  */
943  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
945  return true;
946 
947  /*
948  * Likewise, if both rels are needed to compute some PlaceHolderVar,
949  * attempt the join regardless of outer-join considerations. (This is not
950  * very desirable, because a PHV with a large eval_at set will cause a lot
951  * of probably-useless joins to be considered, but failing to do this can
952  * cause us to fail to construct a plan at all.)
953  */
954  foreach(l, root->placeholder_list)
955  {
956  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
957 
958  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
959  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
960  return true;
961  }
962 
963  /*
964  * It's possible that the rels correspond to the left and right sides of a
965  * degenerate outer join, that is, one with no joinclause mentioning the
966  * non-nullable side; in which case we should force the join to occur.
967  *
968  * Also, the two rels could represent a clauseless join that has to be
969  * completed to build up the LHS or RHS of an outer join.
970  */
971  foreach(l, root->join_info_list)
972  {
973  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
974 
975  /* ignore full joins --- other mechanisms handle them */
976  if (sjinfo->jointype == JOIN_FULL)
977  continue;
978 
979  /* Can we perform the SJ with these rels? */
980  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
981  bms_is_subset(sjinfo->min_righthand, rel2->relids))
982  {
983  result = true;
984  break;
985  }
986  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
987  bms_is_subset(sjinfo->min_righthand, rel1->relids))
988  {
989  result = true;
990  break;
991  }
992 
993  /*
994  * Might we need to join these rels to complete the RHS? We have to
995  * use "overlap" tests since either rel might include a lower SJ that
996  * has been proven to commute with this one.
997  */
998  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
999  bms_overlap(sjinfo->min_righthand, rel2->relids))
1000  {
1001  result = true;
1002  break;
1003  }
1004 
1005  /* Likewise for the LHS. */
1006  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1007  bms_overlap(sjinfo->min_lefthand, rel2->relids))
1008  {
1009  result = true;
1010  break;
1011  }
1012  }
1013 
1014  /*
1015  * We do not force the join to occur if either input rel can legally be
1016  * joined to anything else using joinclauses. This essentially means that
1017  * clauseless bushy joins are put off as long as possible. The reason is
1018  * that when there is a join order restriction high up in the join tree
1019  * (that is, with many rels inside the LHS or RHS), we would otherwise
1020  * expend lots of effort considering very stupid join combinations within
1021  * its LHS or RHS.
1022  */
1023  if (result)
1024  {
1025  if (has_legal_joinclause(root, rel1) ||
1026  has_legal_joinclause(root, rel2))
1027  result = false;
1028  }
1029 
1030  return result;
1031 }
1032 
1033 
1034 /*
1035  * has_join_restriction
1036  * Detect whether the specified relation has join-order restrictions,
1037  * due to being inside an outer join or an IN (sub-SELECT),
1038  * or participating in any LATERAL references or multi-rel PHVs.
1039  *
1040  * Essentially, this tests whether have_join_order_restriction() could
1041  * succeed with this rel and some other one. It's OK if we sometimes
1042  * say "true" incorrectly. (Therefore, we don't bother with the relatively
1043  * expensive has_legal_joinclause test.)
1044  */
1045 static bool
1047 {
1048  ListCell *l;
1049 
1050  if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL)
1051  return true;
1052 
1053  foreach(l, root->placeholder_list)
1054  {
1055  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1056 
1057  if (bms_is_subset(rel->relids, phinfo->ph_eval_at) &&
1058  !bms_equal(rel->relids, phinfo->ph_eval_at))
1059  return true;
1060  }
1061 
1062  foreach(l, root->join_info_list)
1063  {
1064  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1065 
1066  /* ignore full joins --- other mechanisms preserve their ordering */
1067  if (sjinfo->jointype == JOIN_FULL)
1068  continue;
1069 
1070  /* ignore if SJ is already contained in rel */
1071  if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
1072  bms_is_subset(sjinfo->min_righthand, rel->relids))
1073  continue;
1074 
1075  /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
1076  if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
1077  bms_overlap(sjinfo->min_righthand, rel->relids))
1078  return true;
1079  }
1080 
1081  return false;
1082 }
1083 
1084 
1085 /*
1086  * has_legal_joinclause
1087  * Detect whether the specified relation can legally be joined
1088  * to any other rels using join clauses.
1089  *
1090  * We consider only joins to single other relations in the current
1091  * initial_rels list. This is sufficient to get a "true" result in most real
1092  * queries, and an occasional erroneous "false" will only cost a bit more
1093  * planning time. The reason for this limitation is that considering joins to
1094  * other joins would require proving that the other join rel can legally be
1095  * formed, which seems like too much trouble for something that's only a
1096  * heuristic to save planning time. (Note: we must look at initial_rels
1097  * and not all of the query, since when we are planning a sub-joinlist we
1098  * may be forced to make clauseless joins within initial_rels even though
1099  * there are join clauses linking to other parts of the query.)
1100  */
1101 static bool
1103 {
1104  ListCell *lc;
1105 
1106  foreach(lc, root->initial_rels)
1107  {
1108  RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc);
1109 
1110  /* ignore rels that are already in "rel" */
1111  if (bms_overlap(rel->relids, rel2->relids))
1112  continue;
1113 
1114  if (have_relevant_joinclause(root, rel, rel2))
1115  {
1116  Relids joinrelids;
1117  SpecialJoinInfo *sjinfo;
1118  bool reversed;
1119 
1120  /* join_is_legal needs relids of the union */
1121  joinrelids = bms_union(rel->relids, rel2->relids);
1122 
1123  if (join_is_legal(root, rel, rel2, joinrelids,
1124  &sjinfo, &reversed))
1125  {
1126  /* Yes, this will work */
1127  bms_free(joinrelids);
1128  return true;
1129  }
1130 
1131  bms_free(joinrelids);
1132  }
1133  }
1134 
1135  return false;
1136 }
1137 
1138 
1139 /*
1140  * There's a pitfall for creating parameterized nestloops: suppose the inner
1141  * rel (call it A) has a parameter that is a PlaceHolderVar, and that PHV's
1142  * minimum eval_at set includes the outer rel (B) and some third rel (C).
1143  * We might think we could create a B/A nestloop join that's parameterized by
1144  * C. But we would end up with a plan in which the PHV's expression has to be
1145  * evaluated as a nestloop parameter at the B/A join; and the executor is only
1146  * set up to handle simple Vars as NestLoopParams. Rather than add complexity
1147  * and overhead to the executor for such corner cases, it seems better to
1148  * forbid the join. (Note that we can still make use of A's parameterized
1149  * path with pre-joined B+C as the outer rel. have_join_order_restriction()
1150  * ensures that we will consider making such a join even if there are not
1151  * other reasons to do so.)
1152  *
1153  * So we check whether any PHVs used in the query could pose such a hazard.
1154  * We don't have any simple way of checking whether a risky PHV would actually
1155  * be used in the inner plan, and the case is so unusual that it doesn't seem
1156  * worth working very hard on it.
1157  *
1158  * This needs to be checked in two places. If the inner rel's minimum
1159  * parameterization would trigger the restriction, then join_is_legal() should
1160  * reject the join altogether, because there will be no workable paths for it.
1161  * But joinpath.c has to check again for every proposed nestloop path, because
1162  * the inner path might have more than the minimum parameterization, causing
1163  * some PHV to be dangerous for it that otherwise wouldn't be.
1164  */
1165 bool
1167  Relids outer_relids, Relids inner_params)
1168 {
1169  ListCell *lc;
1170 
1171  foreach(lc, root->placeholder_list)
1172  {
1173  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1174 
1175  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1176  continue; /* ignore, could not be a nestloop param */
1177  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1178  continue; /* ignore, not relevant to this join */
1179  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1180  continue; /* safe, it can be eval'd within outerrel */
1181  /* Otherwise, it's potentially unsafe, so reject the join */
1182  return true;
1183  }
1184 
1185  /* OK to perform the join */
1186  return false;
1187 }
1188 
1189 
1190 /*
1191  * is_dummy_rel --- has relation been proven empty?
1192  */
1193 static bool
1195 {
1196  return IS_DUMMY_REL(rel);
1197 }
1198 
1199 /*
1200  * Mark a relation as proven empty.
1201  *
1202  * During GEQO planning, this can get invoked more than once on the same
1203  * baserel struct, so it's worth checking to see if the rel is already marked
1204  * dummy.
1205  *
1206  * Also, when called during GEQO join planning, we are in a short-lived
1207  * memory context. We must make sure that the dummy path attached to a
1208  * baserel survives the GEQO cycle, else the baserel is trashed for future
1209  * GEQO cycles. On the other hand, when we are marking a joinrel during GEQO,
1210  * we don't want the dummy path to clutter the main planning context. Upshot
1211  * is that the best solution is to explicitly make the dummy path in the same
1212  * context the given RelOptInfo is in.
1213  */
1214 void
1216 {
1217  MemoryContext oldcontext;
1218 
1219  /* Already marked? */
1220  if (is_dummy_rel(rel))
1221  return;
1222 
1223  /* No, so choose correct context to make the dummy path in */
1224  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1225 
1226  /* Set dummy size estimate */
1227  rel->rows = 0;
1228 
1229  /* Evict any previously chosen paths */
1230  rel->pathlist = NIL;
1231  rel->partial_pathlist = NIL;
1232 
1233  /* Set up the dummy path */
1234  add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL, NULL,
1235  0, false, NIL, -1));
1236 
1237  /* Set or update cheapest_total_path and related fields */
1238  set_cheapest(rel);
1239 
1240  MemoryContextSwitchTo(oldcontext);
1241 }
1242 
1243 
1244 /*
1245  * restriction_is_constant_false --- is a restrictlist just FALSE?
1246  *
1247  * In cases where a qual is provably constant FALSE, eval_const_expressions
1248  * will generally have thrown away anything that's ANDed with it. In outer
1249  * join situations this will leave us computing cartesian products only to
1250  * decide there's no match for an outer row, which is pretty stupid. So,
1251  * we need to detect the case.
1252  *
1253  * If only_pushed_down is true, then consider only quals that are pushed-down
1254  * from the point of view of the joinrel.
1255  */
1256 static bool
1258  RelOptInfo *joinrel,
1259  bool only_pushed_down)
1260 {
1261  ListCell *lc;
1262 
1263  /*
1264  * Despite the above comment, the restriction list we see here might
1265  * possibly have other members besides the FALSE constant, since other
1266  * quals could get "pushed down" to the outer join level. So we check
1267  * each member of the list.
1268  */
1269  foreach(lc, restrictlist)
1270  {
1271  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1272 
1273  if (only_pushed_down && !RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
1274  continue;
1275 
1276  if (rinfo->clause && IsA(rinfo->clause, Const))
1277  {
1278  Const *con = (Const *) rinfo->clause;
1279 
1280  /* constant NULL is as good as constant FALSE for our purposes */
1281  if (con->constisnull)
1282  return true;
1283  if (!DatumGetBool(con->constvalue))
1284  return true;
1285  }
1286  }
1287  return false;
1288 }
1289 
1290 /*
1291  * Assess whether join between given two partitioned relations can be broken
1292  * down into joins between matching partitions; a technique called
1293  * "partitionwise join"
1294  *
1295  * Partitionwise join is possible when a. Joining relations have same
1296  * partitioning scheme b. There exists an equi-join between the partition keys
1297  * of the two relations.
1298  *
1299  * Partitionwise join is planned as follows (details: optimizer/README.)
1300  *
1301  * 1. Create the RelOptInfos for joins between matching partitions i.e
1302  * child-joins and add paths to them.
1303  *
1304  * 2. Construct Append or MergeAppend paths across the set of child joins.
1305  * This second phase is implemented by generate_partitionwise_join_paths().
1306  *
1307  * The RelOptInfo, SpecialJoinInfo and restrictlist for each child join are
1308  * obtained by translating the respective parent join structures.
1309  */
1310 static void
1312  RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo,
1313  List *parent_restrictlist)
1314 {
1315  int nparts;
1316  int cnt_parts;
1317 
1318  /* Guard against stack overflow due to overly deep partition hierarchy. */
1320 
1321  /* Nothing to do, if the join relation is not partitioned. */
1322  if (!IS_PARTITIONED_REL(joinrel))
1323  return;
1324 
1325  /*
1326  * Since this join relation is partitioned, all the base relations
1327  * participating in this join must be partitioned and so are all the
1328  * intermediate join relations.
1329  */
1332 
1333  /*
1334  * The partition scheme of the join relation should match that of the
1335  * joining relations.
1336  */
1337  Assert(joinrel->part_scheme == rel1->part_scheme &&
1338  joinrel->part_scheme == rel2->part_scheme);
1339 
1340  /*
1341  * Since we allow partitionwise join only when the partition bounds of the
1342  * joining relations exactly match, the partition bounds of the join
1343  * should match those of the joining relations.
1344  */
1346  joinrel->part_scheme->parttyplen,
1347  joinrel->part_scheme->parttypbyval,
1348  joinrel->boundinfo, rel1->boundinfo));
1350  joinrel->part_scheme->parttyplen,
1351  joinrel->part_scheme->parttypbyval,
1352  joinrel->boundinfo, rel2->boundinfo));
1353 
1354  nparts = joinrel->nparts;
1355 
1356  /*
1357  * Create child-join relations for this partitioned join, if those don't
1358  * exist. Add paths to child-joins for a pair of child relations
1359  * corresponding to the given pair of parent relations.
1360  */
1361  for (cnt_parts = 0; cnt_parts < nparts; cnt_parts++)
1362  {
1363  RelOptInfo *child_rel1 = rel1->part_rels[cnt_parts];
1364  RelOptInfo *child_rel2 = rel2->part_rels[cnt_parts];
1365  SpecialJoinInfo *child_sjinfo;
1366  List *child_restrictlist;
1367  RelOptInfo *child_joinrel;
1368  Relids child_joinrelids;
1369  AppendRelInfo **appinfos;
1370  int nappinfos;
1371 
1372  /* We should never try to join two overlapping sets of rels. */
1373  Assert(!bms_overlap(child_rel1->relids, child_rel2->relids));
1374  child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids);
1375  appinfos = find_appinfos_by_relids(root, child_joinrelids, &nappinfos);
1376 
1377  /*
1378  * Construct SpecialJoinInfo from parent join relations's
1379  * SpecialJoinInfo.
1380  */
1381  child_sjinfo = build_child_join_sjinfo(root, parent_sjinfo,
1382  child_rel1->relids,
1383  child_rel2->relids);
1384 
1385  /*
1386  * Construct restrictions applicable to the child join from those
1387  * applicable to the parent join.
1388  */
1389  child_restrictlist =
1390  (List *) adjust_appendrel_attrs(root,
1391  (Node *) parent_restrictlist,
1392  nappinfos, appinfos);
1393  pfree(appinfos);
1394 
1395  child_joinrel = joinrel->part_rels[cnt_parts];
1396  if (!child_joinrel)
1397  {
1398  child_joinrel = build_child_join_rel(root, child_rel1, child_rel2,
1399  joinrel, child_restrictlist,
1400  child_sjinfo,
1401  child_sjinfo->jointype);
1402  joinrel->part_rels[cnt_parts] = child_joinrel;
1403  }
1404 
1405  Assert(bms_equal(child_joinrel->relids, child_joinrelids));
1406 
1407  populate_joinrel_with_paths(root, child_rel1, child_rel2,
1408  child_joinrel, child_sjinfo,
1409  child_restrictlist);
1410  }
1411 }
1412 
1413 /*
1414  * Returns true if there exists an equi-join condition for each pair of
1415  * partition keys from given relations being joined.
1416  */
1417 bool
1419  RelOptInfo *rel1, RelOptInfo *rel2,
1420  JoinType jointype, List *restrictlist)
1421 {
1422  PartitionScheme part_scheme = rel1->part_scheme;
1423  ListCell *lc;
1424  int cnt_pks;
1425  bool pk_has_clause[PARTITION_MAX_KEYS];
1426  bool strict_op;
1427 
1428  /*
1429  * This function should be called when the joining relations have same
1430  * partitioning scheme.
1431  */
1432  Assert(rel1->part_scheme == rel2->part_scheme);
1433  Assert(part_scheme);
1434 
1435  memset(pk_has_clause, 0, sizeof(pk_has_clause));
1436  foreach(lc, restrictlist)
1437  {
1438  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1439  OpExpr *opexpr;
1440  Expr *expr1;
1441  Expr *expr2;
1442  int ipk1;
1443  int ipk2;
1444 
1445  /* If processing an outer join, only use its own join clauses. */
1446  if (IS_OUTER_JOIN(jointype) &&
1447  RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
1448  continue;
1449 
1450  /* Skip clauses which can not be used for a join. */
1451  if (!rinfo->can_join)
1452  continue;
1453 
1454  /* Skip clauses which are not equality conditions. */
1455  if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
1456  continue;
1457 
1458  opexpr = (OpExpr *) rinfo->clause;
1459  Assert(is_opclause(opexpr));
1460 
1461  /*
1462  * The equi-join between partition keys is strict if equi-join between
1463  * at least one partition key is using a strict operator. See
1464  * explanation about outer join reordering identity 3 in
1465  * optimizer/README
1466  */
1467  strict_op = op_strict(opexpr->opno);
1468 
1469  /* Match the operands to the relation. */
1470  if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
1471  bms_is_subset(rinfo->right_relids, rel2->relids))
1472  {
1473  expr1 = linitial(opexpr->args);
1474  expr2 = lsecond(opexpr->args);
1475  }
1476  else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
1477  bms_is_subset(rinfo->right_relids, rel1->relids))
1478  {
1479  expr1 = lsecond(opexpr->args);
1480  expr2 = linitial(opexpr->args);
1481  }
1482  else
1483  continue;
1484 
1485  /*
1486  * Only clauses referencing the partition keys are useful for
1487  * partitionwise join.
1488  */
1489  ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
1490  if (ipk1 < 0)
1491  continue;
1492  ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
1493  if (ipk2 < 0)
1494  continue;
1495 
1496  /*
1497  * If the clause refers to keys at different ordinal positions, it can
1498  * not be used for partitionwise join.
1499  */
1500  if (ipk1 != ipk2)
1501  continue;
1502 
1503  /*
1504  * The clause allows partitionwise join if only it uses the same
1505  * operator family as that specified by the partition key.
1506  */
1508  {
1509  if (!op_in_opfamily(rinfo->hashjoinoperator,
1510  part_scheme->partopfamily[ipk1]))
1511  continue;
1512  }
1513  else if (!list_member_oid(rinfo->mergeopfamilies,
1514  part_scheme->partopfamily[ipk1]))
1515  continue;
1516 
1517  /* Mark the partition key as having an equi-join clause. */
1518  pk_has_clause[ipk1] = true;
1519  }
1520 
1521  /* Check whether every partition key has an equi-join condition. */
1522  for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
1523  {
1524  if (!pk_has_clause[cnt_pks])
1525  return false;
1526  }
1527 
1528  return true;
1529 }
1530 
1531 /*
1532  * Find the partition key from the given relation matching the given
1533  * expression. If found, return the index of the partition key, else return -1.
1534  */
1535 static int
1536 match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
1537 {
1538  int cnt;
1539 
1540  /* This function should be called only for partitioned relations. */
1541  Assert(rel->part_scheme);
1542 
1543  /* Remove any relabel decorations. */
1544  while (IsA(expr, RelabelType))
1545  expr = (Expr *) (castNode(RelabelType, expr))->arg;
1546 
1547  for (cnt = 0; cnt < rel->part_scheme->partnatts; cnt++)
1548  {
1549  ListCell *lc;
1550 
1551  Assert(rel->partexprs);
1552  foreach(lc, rel->partexprs[cnt])
1553  {
1554  if (equal(lfirst(lc), expr))
1555  return cnt;
1556  }
1557 
1558  if (!strict_op)
1559  continue;
1560 
1561  /*
1562  * If it's a strict equi-join a NULL partition key on one side will
1563  * not join a NULL partition key on the other side. So, rows with NULL
1564  * partition key from a partition on one side can not join with those
1565  * from a non-matching partition on the other side. So, search the
1566  * nullable partition keys as well.
1567  */
1568  Assert(rel->nullable_partexprs);
1569  foreach(lc, rel->nullable_partexprs[cnt])
1570  {
1571  if (equal(lfirst(lc), expr))
1572  return cnt;
1573  }
1574  }
1575 
1576  return -1;
1577 }
Datum constvalue
Definition: primnodes.h:197
bool has_eclass_joins
Definition: relation.h:678
SpecialJoinInfo * build_child_join_sjinfo(PlannerInfo *root, SpecialJoinInfo *parent_sjinfo, Relids left_relids, Relids right_relids)
Definition: prepunion.c:2574
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1194
bool op_in_opfamily(Oid opno, Oid opfamily)
Definition: lsyscache.c:63
bool semi_can_btree
Definition: relation.h:2074
int join_cur_level
Definition: relation.h:240
bool op_strict(Oid opno)
Definition: lsyscache.c:1266
AppendPath * create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *partial_subpaths, Relids required_outer, int parallel_workers, bool parallel_aware, List *partitioned_rels, double rows)
Definition: pathnode.c:1219
#define IsA(nodeptr, _type_)
Definition: nodes.h:568
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:133
Relids ph_eval_at
Definition: relation.h:2194
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:758
List * join_info_list
Definition: relation.h:264
Relids min_righthand
Definition: relation.h:2067
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2986
#define castNode(_type_, nodeptr)
Definition: nodes.h:586
#define IS_PARTITIONED_REL(rel)
Definition: relation.h:706
static void make_rels_by_clauseless_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
Definition: joinrels.c:308
NodeTag type
Definition: relation.h:2065
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:730
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:933
Definition: nodes.h:517
int errcode(int sqlerrcode)
Definition: elog.c:575
List * partial_pathlist
Definition: relation.h:628
#define PARTITION_MAX_KEYS
Relids left_relids
Definition: relation.h:1907
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1522
List ** nullable_partexprs
Definition: relation.h:691
#define OidIsValid(objectId)
Definition: c.h:605
List * mergeopfamilies
Definition: relation.h:1925
#define lsecond(l)
Definition: pg_list.h:116
Relids syn_lefthand
Definition: relation.h:2068
JoinType
Definition: nodes.h:681
Relids syn_righthand
Definition: relation.h:2069
static void make_rels_by_clause_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
Definition: joinrels.c:274
Relids lateral_relids
Definition: relation.h:637
void pfree(void *pointer)
Definition: mcxt.c:1031
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: relation.h:1957
List ** partexprs
Definition: relation.h:690
#define linitial(l)
Definition: pg_list.h:111
#define ERROR
Definition: elog.h:43
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1102
#define is_opclause(clause)
Definition: clauses.h:20
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1046
List * semi_rhs_exprs
Definition: relation.h:2077
bool semi_can_hash
Definition: relation.h:2075
bool hasLateralRTEs
Definition: relation.h:316
#define IS_DUMMY_REL(r)
Definition: relation.h:1317
Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel)
Definition: relnode.c:815
bool can_join
Definition: relation.h:1886
RelOptInfo * build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, SpecialJoinInfo *sjinfo, JoinType jointype)
Definition: relnode.c:686
int16 * parttyplen
Definition: relation.h:371
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:374
#define lfirst_node(type, lc)
Definition: pg_list.h:109
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:341
struct Path * cheapest_total_path
Definition: relation.h:630
List * joininfo
Definition: relation.h:676
void check_stack_depth(void)
Definition: postgres.c:3159
int nparts
Definition: relation.h:685
#define DatumGetBool(X)
Definition: postgres.h:378
#define REL_HAS_ALL_PART_PROPS(rel)
Definition: relation.h:714
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
Definition: joinrels.c:1536
Relids relids
Definition: relation.h:612
void join_search_one_level(PlannerInfo *root, int level)
Definition: joinrels.c:65
#define lnext(lc)
Definition: pg_list.h:105
#define ereport(elevel, rest)
Definition: elog.h:122
Relids lateral_referencers
Definition: relation.h:648
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: prepunion.c:2047
Expr * clause
Definition: relation.h:1880
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:668
Relids direct_lateral_relids
Definition: relation.h:636
bool delay_upper_joins
Definition: relation.h:2072
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1215
struct PartitionBoundInfoData * boundinfo
Definition: relation.h:686
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:482
AppendRelInfo ** find_appinfos_by_relids(PlannerInfo *root, Relids relids, int *nappinfos)
Definition: prepunion.c:2618
#define PARTITION_STRATEGY_HASH
Definition: parsenodes.h:798
double rows
Definition: relation.h:615
static bool restriction_is_constant_false(List *restrictlist, RelOptInfo *joinrel, bool only_pushed_down)
Definition: joinrels.c:1257
void bms_free(Bitmapset *a)
Definition: bitmapset.c:267
Relids right_relids
Definition: relation.h:1908
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:505
#define Assert(condition)
Definition: c.h:699
#define lfirst(lc)
Definition: pg_list.h:106
static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, List *parent_restrictlist)
Definition: joinrels.c:1311
List ** join_rel_level
Definition: relation.h:239
JoinType jointype
Definition: relation.h:2070
struct RelOptInfo ** part_rels
Definition: relation.h:688
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:284
Oid hashjoinoperator
Definition: relation.h:1938
#define for_each_cell(cell, initcell)
Definition: pg_list.h:169
bool have_partkey_equi_join(RelOptInfo *joinrel, RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype, List *restrictlist)
Definition: joinrels.c:1418
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:509
int errmsg(const char *fmt,...)
Definition: elog.c:797
bool partition_bounds_equal(int partnatts, int16 *parttyplen, bool *parttypbyval, PartitionBoundInfo b1, PartitionBoundInfo b2)
Definition: partbounds.c:104
List * semi_operators
Definition: relation.h:2076
List * placeholder_list
Definition: relation.h:270
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinpath.c:117
void * arg
PartitionScheme part_scheme
Definition: relation.h:684
List * initial_rels
Definition: relation.h:284
List * pathlist
Definition: relation.h:626
Oid opno
Definition: primnodes.h:497
#define elog
Definition: elog.h:219
List * args
Definition: primnodes.h:503
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:2066
bool constisnull
Definition: primnodes.h:198
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:821
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1166
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:153
static MemoryContext GetMemoryChunkContext(void *pointer)
Definition: memutils.h:112