PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
joinrels.c File Reference
#include "postgres.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "utils/memutils.h"
Include dependency graph for joinrels.c:

Go to the source code of this file.

Functions

static void make_rels_by_clause_joins (PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
 
static void make_rels_by_clauseless_joins (PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
 
static bool has_join_restriction (PlannerInfo *root, RelOptInfo *rel)
 
static bool has_legal_joinclause (PlannerInfo *root, RelOptInfo *rel)
 
static bool is_dummy_rel (RelOptInfo *rel)
 
static void mark_dummy_rel (RelOptInfo *rel)
 
static bool restriction_is_constant_false (List *restrictlist, bool only_pushed_down)
 
void join_search_one_level (PlannerInfo *root, int level)
 
static bool join_is_legal (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
 
RelOptInfomake_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
 

Function Documentation

static bool has_join_restriction ( PlannerInfo root,
RelOptInfo rel 
)
static

Definition at line 1012 of file joinrels.c.

References bms_equal(), bms_is_subset(), bms_overlap(), JOIN_FULL, PlannerInfo::join_info_list, SpecialJoinInfo::jointype, RelOptInfo::lateral_referencers, RelOptInfo::lateral_relids, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NULL, PlaceHolderInfo::ph_eval_at, PlannerInfo::placeholder_list, and RelOptInfo::relids.

Referenced by join_search_one_level().

1013 {
1014  ListCell *l;
1015 
1016  if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL)
1017  return true;
1018 
1019  foreach(l, root->placeholder_list)
1020  {
1021  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1022 
1023  if (bms_is_subset(rel->relids, phinfo->ph_eval_at) &&
1024  !bms_equal(rel->relids, phinfo->ph_eval_at))
1025  return true;
1026  }
1027 
1028  foreach(l, root->join_info_list)
1029  {
1030  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1031 
1032  /* ignore full joins --- other mechanisms preserve their ordering */
1033  if (sjinfo->jointype == JOIN_FULL)
1034  continue;
1035 
1036  /* ignore if SJ is already contained in rel */
1037  if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
1038  bms_is_subset(sjinfo->min_righthand, rel->relids))
1039  continue;
1040 
1041  /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
1042  if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
1043  bms_overlap(sjinfo->min_righthand, rel->relids))
1044  return true;
1045  }
1046 
1047  return false;
1048 }
Relids ph_eval_at
Definition: relation.h:1935
List * join_info_list
Definition: relation.h:247
Relids min_righthand
Definition: relation.h:1808
Relids lateral_relids
Definition: relation.h:515
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
Relids relids
Definition: relation.h:490
Relids lateral_referencers
Definition: relation.h:526
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:1811
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * placeholder_list
Definition: relation.h:253
Relids min_lefthand
Definition: relation.h:1807
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
static bool has_legal_joinclause ( PlannerInfo root,
RelOptInfo rel 
)
static

Definition at line 1068 of file joinrels.c.

References bms_free(), bms_overlap(), bms_union(), have_relevant_joinclause(), PlannerInfo::initial_rels, join_is_legal(), lfirst, and RelOptInfo::relids.

Referenced by have_join_order_restriction().

1069 {
1070  ListCell *lc;
1071 
1072  foreach(lc, root->initial_rels)
1073  {
1074  RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc);
1075 
1076  /* ignore rels that are already in "rel" */
1077  if (bms_overlap(rel->relids, rel2->relids))
1078  continue;
1079 
1080  if (have_relevant_joinclause(root, rel, rel2))
1081  {
1082  Relids joinrelids;
1083  SpecialJoinInfo *sjinfo;
1084  bool reversed;
1085 
1086  /* join_is_legal needs relids of the union */
1087  joinrelids = bms_union(rel->relids, rel2->relids);
1088 
1089  if (join_is_legal(root, rel, rel2, joinrelids,
1090  &sjinfo, &reversed))
1091  {
1092  /* Yes, this will work */
1093  bms_free(joinrelids);
1094  return true;
1095  }
1096 
1097  bms_free(joinrelids);
1098  }
1099  }
1100 
1101  return false;
1102 }
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:327
Relids relids
Definition: relation.h:490
void bms_free(Bitmapset *a)
Definition: bitmapset.c:200
#define lfirst(lc)
Definition: pg_list.h:106
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
List * initial_rels
Definition: relation.h:264
bool have_dangerous_phv ( PlannerInfo root,
Relids  outer_relids,
Relids  inner_params 
)

Definition at line 1132 of file joinrels.c.

References bms_is_subset(), bms_overlap(), lfirst, PlaceHolderInfo::ph_eval_at, and PlannerInfo::placeholder_list.

Referenced by join_is_legal(), and try_nestloop_path().

1134 {
1135  ListCell *lc;
1136 
1137  foreach(lc, root->placeholder_list)
1138  {
1139  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1140 
1141  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1142  continue; /* ignore, could not be a nestloop param */
1143  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1144  continue; /* ignore, not relevant to this join */
1145  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1146  continue; /* safe, it can be eval'd within outerrel */
1147  /* Otherwise, it's potentially unsafe, so reject the join */
1148  return true;
1149  }
1150 
1151  /* OK to perform the join */
1152  return false;
1153 }
Relids ph_eval_at
Definition: relation.h:1935
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
#define lfirst(lc)
Definition: pg_list.h:106
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * placeholder_list
Definition: relation.h:253
bool have_join_order_restriction ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 899 of file joinrels.c.

References bms_is_subset(), bms_overlap(), RelOptInfo::direct_lateral_relids, has_legal_joinclause(), JOIN_FULL, PlannerInfo::join_info_list, SpecialJoinInfo::jointype, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, PlaceHolderInfo::ph_eval_at, PlannerInfo::placeholder_list, and RelOptInfo::relids.

Referenced by desirable_join(), join_search_one_level(), and make_rels_by_clause_joins().

901 {
902  bool result = false;
903  ListCell *l;
904 
905  /*
906  * If either side has a direct lateral reference to the other, attempt the
907  * join regardless of outer-join considerations.
908  */
909  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
911  return true;
912 
913  /*
914  * Likewise, if both rels are needed to compute some PlaceHolderVar,
915  * attempt the join regardless of outer-join considerations. (This is not
916  * very desirable, because a PHV with a large eval_at set will cause a lot
917  * of probably-useless joins to be considered, but failing to do this can
918  * cause us to fail to construct a plan at all.)
919  */
920  foreach(l, root->placeholder_list)
921  {
922  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
923 
924  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
925  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
926  return true;
927  }
928 
929  /*
930  * It's possible that the rels correspond to the left and right sides of a
931  * degenerate outer join, that is, one with no joinclause mentioning the
932  * non-nullable side; in which case we should force the join to occur.
933  *
934  * Also, the two rels could represent a clauseless join that has to be
935  * completed to build up the LHS or RHS of an outer join.
936  */
937  foreach(l, root->join_info_list)
938  {
939  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
940 
941  /* ignore full joins --- other mechanisms handle them */
942  if (sjinfo->jointype == JOIN_FULL)
943  continue;
944 
945  /* Can we perform the SJ with these rels? */
946  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
947  bms_is_subset(sjinfo->min_righthand, rel2->relids))
948  {
949  result = true;
950  break;
951  }
952  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
953  bms_is_subset(sjinfo->min_righthand, rel1->relids))
954  {
955  result = true;
956  break;
957  }
958 
959  /*
960  * Might we need to join these rels to complete the RHS? We have to
961  * use "overlap" tests since either rel might include a lower SJ that
962  * has been proven to commute with this one.
963  */
964  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
965  bms_overlap(sjinfo->min_righthand, rel2->relids))
966  {
967  result = true;
968  break;
969  }
970 
971  /* Likewise for the LHS. */
972  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
973  bms_overlap(sjinfo->min_lefthand, rel2->relids))
974  {
975  result = true;
976  break;
977  }
978  }
979 
980  /*
981  * We do not force the join to occur if either input rel can legally be
982  * joined to anything else using joinclauses. This essentially means that
983  * clauseless bushy joins are put off as long as possible. The reason is
984  * that when there is a join order restriction high up in the join tree
985  * (that is, with many rels inside the LHS or RHS), we would otherwise
986  * expend lots of effort considering very stupid join combinations within
987  * its LHS or RHS.
988  */
989  if (result)
990  {
991  if (has_legal_joinclause(root, rel1) ||
992  has_legal_joinclause(root, rel2))
993  result = false;
994  }
995 
996  return result;
997 }
Relids ph_eval_at
Definition: relation.h:1935
List * join_info_list
Definition: relation.h:247
Relids min_righthand
Definition: relation.h:1808
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1068
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
Relids relids
Definition: relation.h:490
Relids direct_lateral_relids
Definition: relation.h:514
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:1811
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
List * placeholder_list
Definition: relation.h:253
Relids min_lefthand
Definition: relation.h:1807
static bool is_dummy_rel ( RelOptInfo rel)
static

Definition at line 1160 of file joinrels.c.

References IS_DUMMY_REL.

Referenced by make_join_rel(), and mark_dummy_rel().

1161 {
1162  return IS_DUMMY_REL(rel);
1163 }
#define IS_DUMMY_REL(r)
Definition: relation.h:1126
static bool join_is_legal ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2,
Relids  joinrelids,
SpecialJoinInfo **  sjinfo_p,
bool reversed_p 
)
static

Definition at line 327 of file joinrels.c.

References bms_add_members(), bms_copy(), bms_equal(), bms_is_subset(), bms_overlap(), RelOptInfo::cheapest_total_path, create_unique_path(), RelOptInfo::direct_lateral_relids, PlannerInfo::hasLateralRTEs, have_dangerous_phv(), JOIN_FULL, PlannerInfo::join_info_list, JOIN_LEFT, JOIN_SEMI, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, SpecialJoinInfo::lhs_strict, min_join_parameterization(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NULL, RelOptInfo::relids, and SpecialJoinInfo::syn_righthand.

Referenced by has_legal_joinclause(), and make_join_rel().

330 {
331  SpecialJoinInfo *match_sjinfo;
332  bool reversed;
333  bool unique_ified;
334  bool must_be_leftjoin;
335  ListCell *l;
336 
337  /*
338  * Ensure output params are set on failure return. This is just to
339  * suppress uninitialized-variable warnings from overly anal compilers.
340  */
341  *sjinfo_p = NULL;
342  *reversed_p = false;
343 
344  /*
345  * If we have any special joins, the proposed join might be illegal; and
346  * in any case we have to determine its join type. Scan the join info
347  * list for matches and conflicts.
348  */
349  match_sjinfo = NULL;
350  reversed = false;
351  unique_ified = false;
352  must_be_leftjoin = false;
353 
354  foreach(l, root->join_info_list)
355  {
356  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
357 
358  /*
359  * This special join is not relevant unless its RHS overlaps the
360  * proposed join. (Check this first as a fast path for dismissing
361  * most irrelevant SJs quickly.)
362  */
363  if (!bms_overlap(sjinfo->min_righthand, joinrelids))
364  continue;
365 
366  /*
367  * Also, not relevant if proposed join is fully contained within RHS
368  * (ie, we're still building up the RHS).
369  */
370  if (bms_is_subset(joinrelids, sjinfo->min_righthand))
371  continue;
372 
373  /*
374  * Also, not relevant if SJ is already done within either input.
375  */
376  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
377  bms_is_subset(sjinfo->min_righthand, rel1->relids))
378  continue;
379  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
380  bms_is_subset(sjinfo->min_righthand, rel2->relids))
381  continue;
382 
383  /*
384  * If it's a semijoin and we already joined the RHS to any other rels
385  * within either input, then we must have unique-ified the RHS at that
386  * point (see below). Therefore the semijoin is no longer relevant in
387  * this join path.
388  */
389  if (sjinfo->jointype == JOIN_SEMI)
390  {
391  if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
392  !bms_equal(sjinfo->syn_righthand, rel1->relids))
393  continue;
394  if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
395  !bms_equal(sjinfo->syn_righthand, rel2->relids))
396  continue;
397  }
398 
399  /*
400  * If one input contains min_lefthand and the other contains
401  * min_righthand, then we can perform the SJ at this join.
402  *
403  * Reject if we get matches to more than one SJ; that implies we're
404  * considering something that's not really valid.
405  */
406  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
407  bms_is_subset(sjinfo->min_righthand, rel2->relids))
408  {
409  if (match_sjinfo)
410  return false; /* invalid join path */
411  match_sjinfo = sjinfo;
412  reversed = false;
413  }
414  else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
415  bms_is_subset(sjinfo->min_righthand, rel1->relids))
416  {
417  if (match_sjinfo)
418  return false; /* invalid join path */
419  match_sjinfo = sjinfo;
420  reversed = true;
421  }
422  else if (sjinfo->jointype == JOIN_SEMI &&
423  bms_equal(sjinfo->syn_righthand, rel2->relids) &&
424  create_unique_path(root, rel2, rel2->cheapest_total_path,
425  sjinfo) != NULL)
426  {
427  /*----------
428  * For a semijoin, we can join the RHS to anything else by
429  * unique-ifying the RHS (if the RHS can be unique-ified).
430  * We will only get here if we have the full RHS but less
431  * than min_lefthand on the LHS.
432  *
433  * The reason to consider such a join path is exemplified by
434  * SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
435  * If we insist on doing this as a semijoin we will first have
436  * to form the cartesian product of A*B. But if we unique-ify
437  * C then the semijoin becomes a plain innerjoin and we can join
438  * in any order, eg C to A and then to B. When C is much smaller
439  * than A and B this can be a huge win. So we allow C to be
440  * joined to just A or just B here, and then make_join_rel has
441  * to handle the case properly.
442  *
443  * Note that actually we'll allow unique-ified C to be joined to
444  * some other relation D here, too. That is legal, if usually not
445  * very sane, and this routine is only concerned with legality not
446  * with whether the join is good strategy.
447  *----------
448  */
449  if (match_sjinfo)
450  return false; /* invalid join path */
451  match_sjinfo = sjinfo;
452  reversed = false;
453  unique_ified = true;
454  }
455  else if (sjinfo->jointype == JOIN_SEMI &&
456  bms_equal(sjinfo->syn_righthand, rel1->relids) &&
457  create_unique_path(root, rel1, rel1->cheapest_total_path,
458  sjinfo) != NULL)
459  {
460  /* Reversed semijoin case */
461  if (match_sjinfo)
462  return false; /* invalid join path */
463  match_sjinfo = sjinfo;
464  reversed = true;
465  unique_ified = true;
466  }
467  else
468  {
469  /*
470  * Otherwise, the proposed join overlaps the RHS but isn't a valid
471  * implementation of this SJ. But don't panic quite yet: the RHS
472  * violation might have occurred previously, in one or both input
473  * relations, in which case we must have previously decided that
474  * it was OK to commute some other SJ with this one. If we need
475  * to perform this join to finish building up the RHS, rejecting
476  * it could lead to not finding any plan at all. (This can occur
477  * because of the heuristics elsewhere in this file that postpone
478  * clauseless joins: we might not consider doing a clauseless join
479  * within the RHS until after we've performed other, validly
480  * commutable SJs with one or both sides of the clauseless join.)
481  * This consideration boils down to the rule that if both inputs
482  * overlap the RHS, we can allow the join --- they are either
483  * fully within the RHS, or represent previously-allowed joins to
484  * rels outside it.
485  */
486  if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
487  bms_overlap(rel2->relids, sjinfo->min_righthand))
488  continue; /* assume valid previous violation of RHS */
489 
490  /*
491  * The proposed join could still be legal, but only if we're
492  * allowed to associate it into the RHS of this SJ. That means
493  * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
494  * not FULL) and the proposed join must not overlap the LHS.
495  */
496  if (sjinfo->jointype != JOIN_LEFT ||
497  bms_overlap(joinrelids, sjinfo->min_lefthand))
498  return false; /* invalid join path */
499 
500  /*
501  * To be valid, the proposed join must be a LEFT join; otherwise
502  * it can't associate into this SJ's RHS. But we may not yet have
503  * found the SpecialJoinInfo matching the proposed join, so we
504  * can't test that yet. Remember the requirement for later.
505  */
506  must_be_leftjoin = true;
507  }
508  }
509 
510  /*
511  * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
512  * proposed join can't associate into an SJ's RHS.
513  *
514  * Also, fail if the proposed join's predicate isn't strict; we're
515  * essentially checking to see if we can apply outer-join identity 3, and
516  * that's a requirement. (This check may be redundant with checks in
517  * make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
518  */
519  if (must_be_leftjoin &&
520  (match_sjinfo == NULL ||
521  match_sjinfo->jointype != JOIN_LEFT ||
522  !match_sjinfo->lhs_strict))
523  return false; /* invalid join path */
524 
525  /*
526  * We also have to check for constraints imposed by LATERAL references.
527  */
528  if (root->hasLateralRTEs)
529  {
530  bool lateral_fwd;
531  bool lateral_rev;
532  Relids join_lateral_rels;
533 
534  /*
535  * The proposed rels could each contain lateral references to the
536  * other, in which case the join is impossible. If there are lateral
537  * references in just one direction, then the join has to be done with
538  * a nestloop with the lateral referencer on the inside. If the join
539  * matches an SJ that cannot be implemented by such a nestloop, the
540  * join is impossible.
541  *
542  * Also, if the lateral reference is only indirect, we should reject
543  * the join; whatever rel(s) the reference chain goes through must be
544  * joined to first.
545  *
546  * Another case that might keep us from building a valid plan is the
547  * implementation restriction described by have_dangerous_phv().
548  */
549  lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids);
550  lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids);
551  if (lateral_fwd && lateral_rev)
552  return false; /* have lateral refs in both directions */
553  if (lateral_fwd)
554  {
555  /* has to be implemented as nestloop with rel1 on left */
556  if (match_sjinfo &&
557  (reversed ||
558  unique_ified ||
559  match_sjinfo->jointype == JOIN_FULL))
560  return false; /* not implementable as nestloop */
561  /* check there is a direct reference from rel2 to rel1 */
562  if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids))
563  return false; /* only indirect refs, so reject */
564  /* check we won't have a dangerous PHV */
565  if (have_dangerous_phv(root, rel1->relids, rel2->lateral_relids))
566  return false; /* might be unable to handle required PHV */
567  }
568  else if (lateral_rev)
569  {
570  /* has to be implemented as nestloop with rel2 on left */
571  if (match_sjinfo &&
572  (!reversed ||
573  unique_ified ||
574  match_sjinfo->jointype == JOIN_FULL))
575  return false; /* not implementable as nestloop */
576  /* check there is a direct reference from rel1 to rel2 */
577  if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids))
578  return false; /* only indirect refs, so reject */
579  /* check we won't have a dangerous PHV */
580  if (have_dangerous_phv(root, rel2->relids, rel1->lateral_relids))
581  return false; /* might be unable to handle required PHV */
582  }
583 
584  /*
585  * LATERAL references could also cause problems later on if we accept
586  * this join: if the join's minimum parameterization includes any rels
587  * that would have to be on the inside of an outer join with this join
588  * rel, then it's never going to be possible to build the complete
589  * query using this join. We should reject this join not only because
590  * it'll save work, but because if we don't, the clauseless-join
591  * heuristics might think that legality of this join means that some
592  * other join rel need not be formed, and that could lead to failure
593  * to find any plan at all. We have to consider not only rels that
594  * are directly on the inner side of an OJ with the joinrel, but also
595  * ones that are indirectly so, so search to find all such rels.
596  */
597  join_lateral_rels = min_join_parameterization(root, joinrelids,
598  rel1, rel2);
599  if (join_lateral_rels)
600  {
601  Relids join_plus_rhs = bms_copy(joinrelids);
602  bool more;
603 
604  do
605  {
606  more = false;
607  foreach(l, root->join_info_list)
608  {
609  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
610 
611  if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) &&
612  !bms_is_subset(sjinfo->min_righthand, join_plus_rhs))
613  {
614  join_plus_rhs = bms_add_members(join_plus_rhs,
615  sjinfo->min_righthand);
616  more = true;
617  }
618  /* full joins constrain both sides symmetrically */
619  if (sjinfo->jointype == JOIN_FULL &&
620  bms_overlap(sjinfo->min_righthand, join_plus_rhs) &&
621  !bms_is_subset(sjinfo->min_lefthand, join_plus_rhs))
622  {
623  join_plus_rhs = bms_add_members(join_plus_rhs,
624  sjinfo->min_lefthand);
625  more = true;
626  }
627  }
628  } while (more);
629  if (bms_overlap(join_plus_rhs, join_lateral_rels))
630  return false; /* will not be able to join to some RHS rel */
631  }
632  }
633 
634  /* Otherwise, it's a valid join */
635  *sjinfo_p = match_sjinfo;
636  *reversed_p = reversed;
637  return true;
638 }
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:110
List * join_info_list
Definition: relation.h:247
Relids min_righthand
Definition: relation.h:1808
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1424
Relids syn_righthand
Definition: relation.h:1810
Relids lateral_relids
Definition: relation.h:515
bool hasLateralRTEs
Definition: relation.h:295
Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel)
Definition: relnode.c:580
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
struct Path * cheapest_total_path
Definition: relation.h:508
Relids relids
Definition: relation.h:490
Relids direct_lateral_relids
Definition: relation.h:514
#define NULL
Definition: c.h:226
#define lfirst(lc)
Definition: pg_list.h:106
JoinType jointype
Definition: relation.h:1811
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
Relids min_lefthand
Definition: relation.h:1807
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:725
bool have_dangerous_phv(PlannerInfo *root, Relids outer_relids, Relids inner_params)
Definition: joinrels.c:1132
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
void join_search_one_level ( PlannerInfo root,
int  level 
)

Definition at line 51 of file joinrels.c.

References Assert, bms_overlap(), elog, ERROR, for_each_cell, RelOptInfo::has_eclass_joins, has_join_restriction(), PlannerInfo::hasLateralRTEs, have_join_order_restriction(), have_relevant_joinclause(), PlannerInfo::join_cur_level, PlannerInfo::join_info_list, PlannerInfo::join_rel_level, RelOptInfo::joininfo, lfirst, list_head(), lnext, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, and RelOptInfo::relids.

Referenced by standard_join_search().

52 {
53  List **joinrels = root->join_rel_level;
54  ListCell *r;
55  int k;
56 
57  Assert(joinrels[level] == NIL);
58 
59  /* Set join_cur_level so that new joinrels are added to proper list */
60  root->join_cur_level = level;
61 
62  /*
63  * First, consider left-sided and right-sided plans, in which rels of
64  * exactly level-1 member relations are joined against initial relations.
65  * We prefer to join using join clauses, but if we find a rel of level-1
66  * members that has no join clauses, we will generate Cartesian-product
67  * joins against all initial rels not already contained in it.
68  */
69  foreach(r, joinrels[level - 1])
70  {
71  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
72 
73  if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
74  has_join_restriction(root, old_rel))
75  {
76  /*
77  * There are join clauses or join order restrictions relevant to
78  * this rel, so consider joins between this rel and (only) those
79  * initial rels it is linked to by a clause or restriction.
80  *
81  * At level 2 this condition is symmetric, so there is no need to
82  * look at initial rels before this one in the list; we already
83  * considered such joins when we were at the earlier rel. (The
84  * mirror-image joins are handled automatically by make_join_rel.)
85  * In later passes (level > 2), we join rels of the previous level
86  * to each initial rel they don't already include but have a join
87  * clause or restriction with.
88  */
89  ListCell *other_rels;
90 
91  if (level == 2) /* consider remaining initial rels */
92  other_rels = lnext(r);
93  else /* consider all initial rels */
94  other_rels = list_head(joinrels[1]);
95 
97  old_rel,
98  other_rels);
99  }
100  else
101  {
102  /*
103  * Oops, we have a relation that is not joined to any other
104  * relation, either directly or by join-order restrictions.
105  * Cartesian product time.
106  *
107  * We consider a cartesian product with each not-already-included
108  * initial rel, whether it has other join clauses or not. At
109  * level 2, if there are two or more clauseless initial rels, we
110  * will redundantly consider joining them in both directions; but
111  * such cases aren't common enough to justify adding complexity to
112  * avoid the duplicated effort.
113  */
115  old_rel,
116  list_head(joinrels[1]));
117  }
118  }
119 
120  /*
121  * Now, consider "bushy plans" in which relations of k initial rels are
122  * joined to relations of level-k initial rels, for 2 <= k <= level-2.
123  *
124  * We only consider bushy-plan joins for pairs of rels where there is a
125  * suitable join clause (or join order restriction), in order to avoid
126  * unreasonable growth of planning time.
127  */
128  for (k = 2;; k++)
129  {
130  int other_level = level - k;
131 
132  /*
133  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
134  * need to go as far as the halfway point.
135  */
136  if (k > other_level)
137  break;
138 
139  foreach(r, joinrels[k])
140  {
141  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
142  ListCell *other_rels;
143  ListCell *r2;
144 
145  /*
146  * We can ignore relations without join clauses here, unless they
147  * participate in join-order restrictions --- then we might have
148  * to force a bushy join plan.
149  */
150  if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
151  !has_join_restriction(root, old_rel))
152  continue;
153 
154  if (k == other_level)
155  other_rels = lnext(r); /* only consider remaining rels */
156  else
157  other_rels = list_head(joinrels[other_level]);
158 
159  for_each_cell(r2, other_rels)
160  {
161  RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
162 
163  if (!bms_overlap(old_rel->relids, new_rel->relids))
164  {
165  /*
166  * OK, we can build a rel of the right level from this
167  * pair of rels. Do so if there is at least one relevant
168  * join clause or join order restriction.
169  */
170  if (have_relevant_joinclause(root, old_rel, new_rel) ||
171  have_join_order_restriction(root, old_rel, new_rel))
172  {
173  (void) make_join_rel(root, old_rel, new_rel);
174  }
175  }
176  }
177  }
178  }
179 
180  /*----------
181  * Last-ditch effort: if we failed to find any usable joins so far, force
182  * a set of cartesian-product joins to be generated. This handles the
183  * special case where all the available rels have join clauses but we
184  * cannot use any of those clauses yet. This can only happen when we are
185  * considering a join sub-problem (a sub-joinlist) and all the rels in the
186  * sub-problem have only join clauses with rels outside the sub-problem.
187  * An example is
188  *
189  * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
190  * WHERE a.w = c.x and b.y = d.z;
191  *
192  * If the "a INNER JOIN b" sub-problem does not get flattened into the
193  * upper level, we must be willing to make a cartesian join of a and b;
194  * but the code above will not have done so, because it thought that both
195  * a and b have joinclauses. We consider only left-sided and right-sided
196  * cartesian joins in this case (no bushy).
197  *----------
198  */
199  if (joinrels[level] == NIL)
200  {
201  /*
202  * This loop is just like the first one, except we always call
203  * make_rels_by_clauseless_joins().
204  */
205  foreach(r, joinrels[level - 1])
206  {
207  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
208 
210  old_rel,
211  list_head(joinrels[1]));
212  }
213 
214  /*----------
215  * When special joins are involved, there may be no legal way
216  * to make an N-way join for some values of N. For example consider
217  *
218  * SELECT ... FROM t1 WHERE
219  * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
220  * y IN (SELECT ... FROM t4,t5 WHERE ...)
221  *
222  * We will flatten this query to a 5-way join problem, but there are
223  * no 4-way joins that join_is_legal() will consider legal. We have
224  * to accept failure at level 4 and go on to discover a workable
225  * bushy plan at level 5.
226  *
227  * However, if there are no special joins and no lateral references
228  * then join_is_legal() should never fail, and so the following sanity
229  * check is useful.
230  *----------
231  */
232  if (joinrels[level] == NIL &&
233  root->join_info_list == NIL &&
234  !root->hasLateralRTEs)
235  elog(ERROR, "failed to build any %d-way joins", level);
236  }
237 }
bool has_eclass_joins
Definition: relation.h:551
#define NIL
Definition: pg_list.h:69
int join_cur_level
Definition: relation.h:223
List * join_info_list
Definition: relation.h:247
static void make_rels_by_clauseless_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
Definition: joinrels.c:294
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:899
static void make_rels_by_clause_joins(PlannerInfo *root, RelOptInfo *old_rel, ListCell *other_rels)
Definition: joinrels.c:260
#define ERROR
Definition: elog.h:43
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1012
bool hasLateralRTEs
Definition: relation.h:295
List * joininfo
Definition: relation.h:549
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
Relids relids
Definition: relation.h:490
#define lnext(lc)
Definition: pg_list.h:105
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:654
#define Assert(condition)
Definition: c.h:671
#define lfirst(lc)
Definition: pg_list.h:106
List ** join_rel_level
Definition: relation.h:222
#define for_each_cell(cell, initcell)
Definition: pg_list.h:163
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
RelOptInfo* make_join_rel ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 654 of file joinrels.c.

References add_paths_to_joinrel(), Assert, bms_equal(), bms_free(), bms_is_subset(), bms_overlap(), bms_union(), build_join_rel(), RelOptInfo::cheapest_total_path, create_unique_path(), SpecialJoinInfo::delay_upper_joins, elog, ereport, errcode(), errmsg(), ERROR, is_dummy_rel(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, join_is_legal(), JOIN_LEFT, JOIN_RIGHT, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, mark_dummy_rel(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, NULL, RelOptInfo::pathlist, RelOptInfo::relids, restriction_is_constant_false(), SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

Referenced by join_search_one_level(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), and merge_clump().

655 {
656  Relids joinrelids;
657  SpecialJoinInfo *sjinfo;
658  bool reversed;
659  SpecialJoinInfo sjinfo_data;
660  RelOptInfo *joinrel;
661  List *restrictlist;
662 
663  /* We should never try to join two overlapping sets of rels. */
664  Assert(!bms_overlap(rel1->relids, rel2->relids));
665 
666  /* Construct Relids set that identifies the joinrel. */
667  joinrelids = bms_union(rel1->relids, rel2->relids);
668 
669  /* Check validity and determine join type. */
670  if (!join_is_legal(root, rel1, rel2, joinrelids,
671  &sjinfo, &reversed))
672  {
673  /* invalid join path */
674  bms_free(joinrelids);
675  return NULL;
676  }
677 
678  /* Swap rels if needed to match the join info. */
679  if (reversed)
680  {
681  RelOptInfo *trel = rel1;
682 
683  rel1 = rel2;
684  rel2 = trel;
685  }
686 
687  /*
688  * If it's a plain inner join, then we won't have found anything in
689  * join_info_list. Make up a SpecialJoinInfo so that selectivity
690  * estimation functions will know what's being joined.
691  */
692  if (sjinfo == NULL)
693  {
694  sjinfo = &sjinfo_data;
695  sjinfo->type = T_SpecialJoinInfo;
696  sjinfo->min_lefthand = rel1->relids;
697  sjinfo->min_righthand = rel2->relids;
698  sjinfo->syn_lefthand = rel1->relids;
699  sjinfo->syn_righthand = rel2->relids;
700  sjinfo->jointype = JOIN_INNER;
701  /* we don't bother trying to make the remaining fields valid */
702  sjinfo->lhs_strict = false;
703  sjinfo->delay_upper_joins = false;
704  sjinfo->semi_can_btree = false;
705  sjinfo->semi_can_hash = false;
706  sjinfo->semi_operators = NIL;
707  sjinfo->semi_rhs_exprs = NIL;
708  }
709 
710  /*
711  * Find or build the join RelOptInfo, and compute the restrictlist that
712  * goes with this particular joining.
713  */
714  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
715  &restrictlist);
716 
717  /*
718  * If we've already proven this join is empty, we needn't consider any
719  * more paths for it.
720  */
721  if (is_dummy_rel(joinrel))
722  {
723  bms_free(joinrelids);
724  return joinrel;
725  }
726 
727  /*
728  * Consider paths using each rel as both outer and inner. Depending on
729  * the join type, a provably empty outer or inner rel might mean the join
730  * is provably empty too; in which case throw away any previously computed
731  * paths and mark the join as dummy. (We do it this way since it's
732  * conceivable that dummy-ness of a multi-element join might only be
733  * noticeable for certain construction paths.)
734  *
735  * Also, a provably constant-false join restriction typically means that
736  * we can skip evaluating one or both sides of the join. We do this by
737  * marking the appropriate rel as dummy. For outer joins, a
738  * constant-false restriction that is pushed down still means the whole
739  * join is dummy, while a non-pushed-down one means that no inner rows
740  * will join so we can treat the inner rel as dummy.
741  *
742  * We need only consider the jointypes that appear in join_info_list, plus
743  * JOIN_INNER.
744  */
745  switch (sjinfo->jointype)
746  {
747  case JOIN_INNER:
748  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
749  restriction_is_constant_false(restrictlist, false))
750  {
751  mark_dummy_rel(joinrel);
752  break;
753  }
754  add_paths_to_joinrel(root, joinrel, rel1, rel2,
755  JOIN_INNER, sjinfo,
756  restrictlist);
757  add_paths_to_joinrel(root, joinrel, rel2, rel1,
758  JOIN_INNER, sjinfo,
759  restrictlist);
760  break;
761  case JOIN_LEFT:
762  if (is_dummy_rel(rel1) ||
763  restriction_is_constant_false(restrictlist, true))
764  {
765  mark_dummy_rel(joinrel);
766  break;
767  }
768  if (restriction_is_constant_false(restrictlist, false) &&
769  bms_is_subset(rel2->relids, sjinfo->syn_righthand))
770  mark_dummy_rel(rel2);
771  add_paths_to_joinrel(root, joinrel, rel1, rel2,
772  JOIN_LEFT, sjinfo,
773  restrictlist);
774  add_paths_to_joinrel(root, joinrel, rel2, rel1,
775  JOIN_RIGHT, sjinfo,
776  restrictlist);
777  break;
778  case JOIN_FULL:
779  if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
780  restriction_is_constant_false(restrictlist, true))
781  {
782  mark_dummy_rel(joinrel);
783  break;
784  }
785  add_paths_to_joinrel(root, joinrel, rel1, rel2,
786  JOIN_FULL, sjinfo,
787  restrictlist);
788  add_paths_to_joinrel(root, joinrel, rel2, rel1,
789  JOIN_FULL, sjinfo,
790  restrictlist);
791 
792  /*
793  * If there are join quals that aren't mergeable or hashable, we
794  * may not be able to build any valid plan. Complain here so that
795  * we can give a somewhat-useful error message. (Since we have no
796  * flexibility of planning for a full join, there's no chance of
797  * succeeding later with another pair of input rels.)
798  */
799  if (joinrel->pathlist == NIL)
800  ereport(ERROR,
801  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
802  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
803  break;
804  case JOIN_SEMI:
805 
806  /*
807  * We might have a normal semijoin, or a case where we don't have
808  * enough rels to do the semijoin but can unique-ify the RHS and
809  * then do an innerjoin (see comments in join_is_legal). In the
810  * latter case we can't apply JOIN_SEMI joining.
811  */
812  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
813  bms_is_subset(sjinfo->min_righthand, rel2->relids))
814  {
815  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
816  restriction_is_constant_false(restrictlist, false))
817  {
818  mark_dummy_rel(joinrel);
819  break;
820  }
821  add_paths_to_joinrel(root, joinrel, rel1, rel2,
822  JOIN_SEMI, sjinfo,
823  restrictlist);
824  }
825 
826  /*
827  * If we know how to unique-ify the RHS and one input rel is
828  * exactly the RHS (not a superset) we can consider unique-ifying
829  * it and then doing a regular join. (The create_unique_path
830  * check here is probably redundant with what join_is_legal did,
831  * but if so the check is cheap because it's cached. So test
832  * anyway to be sure.)
833  */
834  if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
835  create_unique_path(root, rel2, rel2->cheapest_total_path,
836  sjinfo) != NULL)
837  {
838  if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
839  restriction_is_constant_false(restrictlist, false))
840  {
841  mark_dummy_rel(joinrel);
842  break;
843  }
844  add_paths_to_joinrel(root, joinrel, rel1, rel2,
845  JOIN_UNIQUE_INNER, sjinfo,
846  restrictlist);
847  add_paths_to_joinrel(root, joinrel, rel2, rel1,
848  JOIN_UNIQUE_OUTER, sjinfo,
849  restrictlist);
850  }
851  break;
852  case JOIN_ANTI:
853  if (is_dummy_rel(rel1) ||
854  restriction_is_constant_false(restrictlist, true))
855  {
856  mark_dummy_rel(joinrel);
857  break;
858  }
859  if (restriction_is_constant_false(restrictlist, false) &&
860  bms_is_subset(rel2->relids, sjinfo->syn_righthand))
861  mark_dummy_rel(rel2);
862  add_paths_to_joinrel(root, joinrel, rel1, rel2,
863  JOIN_ANTI, sjinfo,
864  restrictlist);
865  break;
866  default:
867  /* other values not expected here */
868  elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
869  break;
870  }
871 
872  bms_free(joinrelids);
873 
874  return joinrel;
875 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1160
bool semi_can_btree
Definition: relation.h:1815
static bool restriction_is_constant_false(List *restrictlist, bool only_pushed_down)
Definition: joinrels.c:1221
Relids min_righthand
Definition: relation.h:1808
NodeTag type
Definition: relation.h:1806
static void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1181
int errcode(int sqlerrcode)
Definition: elog.c:575
UniquePath * create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SpecialJoinInfo *sjinfo)
Definition: pathnode.c:1424
Relids syn_lefthand
Definition: relation.h:1809
Relids syn_righthand
Definition: relation.h:1810
#define ERROR
Definition: elog.h:43
List * semi_rhs_exprs
Definition: relation.h:1818
bool semi_can_hash
Definition: relation.h:1816
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:327
struct Path * cheapest_total_path
Definition: relation.h:508
Relids relids
Definition: relation.h:490
#define ereport(elevel, rest)
Definition: elog.h:122
bool delay_upper_joins
Definition: relation.h:1813
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:346
void bms_free(Bitmapset *a)
Definition: bitmapset.c:200
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
JoinType jointype
Definition: relation.h:1811
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
int errmsg(const char *fmt,...)
Definition: elog.c:797
List * semi_operators
Definition: relation.h:1817
void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinpath.c:88
List * pathlist
Definition: relation.h:504
#define elog
Definition: elog.h:219
Definition: pg_list.h:45
Relids min_lefthand
Definition: relation.h:1807
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:130
static void make_rels_by_clause_joins ( PlannerInfo root,
RelOptInfo old_rel,
ListCell other_rels 
)
static

Definition at line 260 of file joinrels.c.

References bms_overlap(), for_each_cell, have_join_order_restriction(), have_relevant_joinclause(), lfirst, make_join_rel(), and RelOptInfo::relids.

Referenced by join_search_one_level().

263 {
264  ListCell *l;
265 
266  for_each_cell(l, other_rels)
267  {
268  RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
269 
270  if (!bms_overlap(old_rel->relids, other_rel->relids) &&
271  (have_relevant_joinclause(root, old_rel, other_rel) ||
272  have_join_order_restriction(root, old_rel, other_rel)))
273  {
274  (void) make_join_rel(root, old_rel, other_rel);
275  }
276  }
277 }
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:899
Relids relids
Definition: relation.h:490
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:654
#define lfirst(lc)
Definition: pg_list.h:106
#define for_each_cell(cell, initcell)
Definition: pg_list.h:163
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:36
static void make_rels_by_clauseless_joins ( PlannerInfo root,
RelOptInfo old_rel,
ListCell other_rels 
)
static

Definition at line 294 of file joinrels.c.

References bms_overlap(), for_each_cell, lfirst, make_join_rel(), and RelOptInfo::relids.

Referenced by join_search_one_level().

297 {
298  ListCell *l;
299 
300  for_each_cell(l, other_rels)
301  {
302  RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
303 
304  if (!bms_overlap(other_rel->relids, old_rel->relids))
305  {
306  (void) make_join_rel(root, old_rel, other_rel);
307  }
308  }
309 }
Relids relids
Definition: relation.h:490
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:654
#define lfirst(lc)
Definition: pg_list.h:106
#define for_each_cell(cell, initcell)
Definition: pg_list.h:163
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
static void mark_dummy_rel ( RelOptInfo rel)
static

Definition at line 1181 of file joinrels.c.

References add_path(), create_append_path(), GetMemoryChunkContext(), is_dummy_rel(), MemoryContextSwitchTo(), NIL, NULL, RelOptInfo::partial_pathlist, RelOptInfo::pathlist, RelOptInfo::rows, and set_cheapest().

Referenced by make_join_rel().

1182 {
1183  MemoryContext oldcontext;
1184 
1185  /* Already marked? */
1186  if (is_dummy_rel(rel))
1187  return;
1188 
1189  /* No, so choose correct context to make the dummy path in */
1190  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1191 
1192  /* Set dummy size estimate */
1193  rel->rows = 0;
1194 
1195  /* Evict any previously chosen paths */
1196  rel->pathlist = NIL;
1197  rel->partial_pathlist = NIL;
1198 
1199  /* Set up the dummy path */
1200  add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0));
1201 
1202  /* Set or update cheapest_total_path and related fields */
1203  set_cheapest(rel);
1204 
1205  MemoryContextSwitchTo(oldcontext);
1206 }
#define NIL
Definition: pg_list.h:69
static bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1160
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:412
AppendPath * create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer, int parallel_workers)
Definition: pathnode.c:1202
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
List * partial_pathlist
Definition: relation.h:506
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:234
double rows
Definition: relation.h:493
#define NULL
Definition: c.h:226
List * pathlist
Definition: relation.h:504
Definition: relation.h:888
static MemoryContext GetMemoryChunkContext(void *pointer)
Definition: memutils.h:107
static bool restriction_is_constant_false ( List restrictlist,
bool  only_pushed_down 
)
static

Definition at line 1221 of file joinrels.c.

References castNode, RestrictInfo::clause, Const::constisnull, Const::constvalue, DatumGetBool, RestrictInfo::is_pushed_down, IsA, and lfirst.

Referenced by make_join_rel().

1222 {
1223  ListCell *lc;
1224 
1225  /*
1226  * Despite the above comment, the restriction list we see here might
1227  * possibly have other members besides the FALSE constant, since other
1228  * quals could get "pushed down" to the outer join level. So we check
1229  * each member of the list.
1230  */
1231  foreach(lc, restrictlist)
1232  {
1233  RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(lc));
1234 
1235  if (only_pushed_down && !rinfo->is_pushed_down)
1236  continue;
1237 
1238  if (rinfo->clause && IsA(rinfo->clause, Const))
1239  {
1240  Const *con = (Const *) rinfo->clause;
1241 
1242  /* constant NULL is as good as constant FALSE for our purposes */
1243  if (con->constisnull)
1244  return true;
1245  if (!DatumGetBool(con->constvalue))
1246  return true;
1247  }
1248  }
1249  return false;
1250 }
Datum constvalue
Definition: primnodes.h:174
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
#define castNode(_type_, nodeptr)
Definition: nodes.h:578
#define DatumGetBool(X)
Definition: postgres.h:401
Expr * clause
Definition: relation.h:1637
bool is_pushed_down
Definition: relation.h:1639
#define lfirst(lc)
Definition: pg_list.h:106
bool constisnull
Definition: primnodes.h:175