make_join_rel.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * make_join_rel.c
   4  *        Routines copied from PostgreSQL core distribution.
   5  *
   6  * src/backend/optimizer/path/joinrels.c
   7  *     make_join_rel()
   8  *
   9  * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
  10  * Portions Copyright (c) 1994, Regents of the University of California
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 /*
  16  * make_join_rel
  17  *         Find or create a join RelOptInfo that represents the join of
  18  *         the two given rels, and add to it path information for paths
  19  *         created with the two rels as outer and inner rel.
  20  *         (The join rel may already contain paths generated from other
  21  *         pairs of rels that add up to the same set of base rels.)
  22  *
  23  * NB: will return NULL if attempted join is not valid.  This can happen
  24  * when working with outer joins, or with IN or EXISTS clauses that have been
  25  * turned into joins.
  26  */
  27 RelOptInfo *
  28 make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
  29 {
  30         Relids          joinrelids;
  31         SpecialJoinInfo *sjinfo;
  32         bool            reversed;
  33         SpecialJoinInfo sjinfo_data;
  34         RelOptInfo *joinrel;
  35         List       *restrictlist;
  36
  37         /* We should never try to join two overlapping sets of rels. */
  38         Assert(!bms_overlap(rel1->relids, rel2->relids));
  39
  40         /* Construct Relids set that identifies the joinrel. */
  41         joinrelids = bms_union(rel1->relids, rel2->relids);
  42
  43         /* Check validity and determine join type. */
  44         if (!join_is_legal(root, rel1, rel2, joinrelids,
  45                                            &sjinfo, &reversed))
  46         {
  47                 /* invalid join path */
  48                 bms_free(joinrelids);
  49                 return NULL;
  50         }
  51
  52         /* Swap rels if needed to match the join info. */
  53         if (reversed)
  54         {
  55                 RelOptInfo *trel = rel1;
  56
  57                 rel1 = rel2;
  58                 rel2 = trel;
  59         }
  60
  61         /*
  62          * If it's a plain inner join, then we won't have found anything in
  63          * join_info_list.      Make up a SpecialJoinInfo so that selectivity
  64          * estimation functions will know what's being joined.
  65          */
  66         if (sjinfo == NULL)
  67         {
  68                 sjinfo = &sjinfo_data;
  69                 sjinfo->type = T_SpecialJoinInfo;
  70                 sjinfo->min_lefthand = rel1->relids;
  71                 sjinfo->min_righthand = rel2->relids;
  72                 sjinfo->syn_lefthand = rel1->relids;
  73                 sjinfo->syn_righthand = rel2->relids;
  74                 sjinfo->jointype = JOIN_INNER;
  75                 /* we don't bother trying to make the remaining fields valid */
  76                 sjinfo->lhs_strict = false;
  77                 sjinfo->delay_upper_joins = false;
  78                 sjinfo->join_quals = NIL;
  79         }
  80
  81         /*
  82          * Find or build the join RelOptInfo, and compute the restrictlist that
  83          * goes with this particular joining.
  84          */
  85         joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
  86                                                          &restrictlist);
  87
  88         /*
  89          * If we've already proven this join is empty, we needn't consider any
  90          * more paths for it.
  91          */
  92         if (is_dummy_rel(joinrel))
  93         {
  94                 bms_free(joinrelids);
  95                 return joinrel;
  96         }
  97
  98         /*
  99          * Consider paths using each rel as both outer and inner.  Depending on
 100          * the join type, a provably empty outer or inner rel might mean the join
 101          * is provably empty too; in which case throw away any previously computed
 102          * paths and mark the join as dummy.  (We do it this way since it's
 103          * conceivable that dummy-ness of a multi-element join might only be
 104          * noticeable for certain construction paths.)
 105          *
 106          * Also, a provably constant-false join restriction typically means that
 107          * we can skip evaluating one or both sides of the join.  We do this by
 108          * marking the appropriate rel as dummy.  For outer joins, a
 109          * constant-false restriction that is pushed down still means the whole
 110          * join is dummy, while a non-pushed-down one means that no inner rows
 111          * will join so we can treat the inner rel as dummy.
 112          *
 113          * We need only consider the jointypes that appear in join_info_list, plus
 114          * JOIN_INNER.
 115          */
 116         switch (sjinfo->jointype)
 117         {
 118                 case JOIN_INNER:
 119                         if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 120                                 restriction_is_constant_false(restrictlist, false))
 121                         {
 122                                 mark_dummy_rel(joinrel);
 123                                 break;
 124                         }
 125                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 126                                                                  JOIN_INNER, sjinfo,
 127                                                                  restrictlist);
 128                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 129                                                                  JOIN_INNER, sjinfo,
 130                                                                  restrictlist);
 131                         break;
 132                 case JOIN_LEFT:
 133                         if (is_dummy_rel(rel1) ||
 134                                 restriction_is_constant_false(restrictlist, true))
 135                         {
 136                                 mark_dummy_rel(joinrel);
 137                                 break;
 138                         }
 139                         if (restriction_is_constant_false(restrictlist, false) &&
 140                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 141                                 mark_dummy_rel(rel2);
 142                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 143                                                                  JOIN_LEFT, sjinfo,
 144                                                                  restrictlist);
 145                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 146                                                                  JOIN_RIGHT, sjinfo,
 147                                                                  restrictlist);
 148                         break;
 149                 case JOIN_FULL:
 150                         if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
 151                                 restriction_is_constant_false(restrictlist, true))
 152                         {
 153                                 mark_dummy_rel(joinrel);
 154                                 break;
 155                         }
 156                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 157                                                                  JOIN_FULL, sjinfo,
 158                                                                  restrictlist);
 159                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 160                                                                  JOIN_FULL, sjinfo,
 161                                                                  restrictlist);
 162
 163                         /*
 164                          * If there are join quals that aren't mergeable or hashable, we
 165                          * may not be able to build any valid plan.  Complain here so that
 166                          * we can give a somewhat-useful error message.  (Since we have no
 167                          * flexibility of planning for a full join, there's no chance of
 168                          * succeeding later with another pair of input rels.)
 169                          */
 170                         if (joinrel->pathlist == NIL)
 171                                 ereport(ERROR,
 172                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 173                                                  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
 174                         break;
 175                 case JOIN_SEMI:
 176
 177                         /*
 178                          * We might have a normal semijoin, or a case where we don't have
 179                          * enough rels to do the semijoin but can unique-ify the RHS and
 180                          * then do an innerjoin (see comments in join_is_legal).  In the
 181                          * latter case we can't apply JOIN_SEMI joining.
 182                          */
 183                         if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 184                                 bms_is_subset(sjinfo->min_righthand, rel2->relids))
 185                         {
 186                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 187                                         restriction_is_constant_false(restrictlist, false))
 188                                 {
 189                                         mark_dummy_rel(joinrel);
 190                                         break;
 191                                 }
 192                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 193                                                                          JOIN_SEMI, sjinfo,
 194                                                                          restrictlist);
 195                         }
 196
 197                         /*
 198                          * If we know how to unique-ify the RHS and one input rel is
 199                          * exactly the RHS (not a superset) we can consider unique-ifying
 200                          * it and then doing a regular join.  (The create_unique_path
 201                          * check here is probably redundant with what join_is_legal did,
 202                          * but if so the check is cheap because it's cached.  So test
 203                          * anyway to be sure.)
 204                          */
 205                         if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
 206                                 create_unique_path(root, rel2, rel2->cheapest_total_path,
 207                                                                    sjinfo) != NULL)
 208                         {
 209                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 210                                         restriction_is_constant_false(restrictlist, false))
 211                                 {
 212                                         mark_dummy_rel(joinrel);
 213                                         break;
 214                                 }
 215                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 216                                                                          JOIN_UNIQUE_INNER, sjinfo,
 217                                                                          restrictlist);
 218                                 add_paths_to_joinrel(root, joinrel, rel2, rel1,
 219                                                                          JOIN_UNIQUE_OUTER, sjinfo,
 220                                                                          restrictlist);
 221                         }
 222                         break;
 223                 case JOIN_ANTI:
 224                         if (is_dummy_rel(rel1) ||
 225                                 restriction_is_constant_false(restrictlist, true))
 226                         {
 227                                 mark_dummy_rel(joinrel);
 228                                 break;
 229                         }
 230                         if (restriction_is_constant_false(restrictlist, false) &&
 231                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 232                                 mark_dummy_rel(rel2);
 233                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 234                                                                  JOIN_ANTI, sjinfo,
 235                                                                  restrictlist);
 236                         break;
 237                 default:
 238                         /* other values not expected here */
 239                         elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
 240                         break;
 241         }
 242
 243         bms_free(joinrelids);
 244
 245         return joinrel;
 246 }