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 static double
  28 adjust_rows(double rows, RowsHint *hint)
  29 {
  30         double          result = 0.0;   /* keep compiler quiet */
  31
  32         if (hint->value_type == RVT_ABSOLUTE)
  33                 result = hint->rows;
  34         else if (hint->value_type == RVT_ADD)
  35                 result = rows + hint->rows;
  36         else if (hint->value_type == RVT_SUB)
  37                 result =  rows - hint->rows;
  38         else if (hint->value_type == RVT_MULTI)
  39                 result = rows * hint->rows;
  40         else
  41                 Assert(false);  /* unrecognized rows value type */
  42
  43         hint->base.state = HINT_STATE_USED;
  44         result = clamp_row_est(result);
  45         elog(DEBUG1, "adjusted rows %d to %d", (int) rows, (int) result);
  46
  47         return result;
  48 }
  49
  50 RelOptInfo *
  51 make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
  52 {
  53         Relids          joinrelids;
  54         SpecialJoinInfo *sjinfo;
  55         bool            reversed;
  56         SpecialJoinInfo sjinfo_data;
  57         RelOptInfo *joinrel;
  58         List       *restrictlist;
  59
  60         RowsHint   *rows_hint = NULL;
  61         int                     i;
  62
  63         /* We should never try to join two overlapping sets of rels. */
  64         Assert(!bms_overlap(rel1->relids, rel2->relids));
  65
  66         /* Construct Relids set that identifies the joinrel. */
  67         joinrelids = bms_union(rel1->relids, rel2->relids);
  68
  69         /* Check validity and determine join type. */
  70         if (!join_is_legal(root, rel1, rel2, joinrelids,
  71                                            &sjinfo, &reversed))
  72         {
  73                 /* invalid join path */
  74                 bms_free(joinrelids);
  75                 return NULL;
  76         }
  77
  78         /* Swap rels if needed to match the join info. */
  79         if (reversed)
  80         {
  81                 RelOptInfo *trel = rel1;
  82
  83                 rel1 = rel2;
  84                 rel2 = trel;
  85         }
  86
  87         /*
  88          * If it's a plain inner join, then we won't have found anything in
  89          * join_info_list.      Make up a SpecialJoinInfo so that selectivity
  90          * estimation functions will know what's being joined.
  91          */
  92         if (sjinfo == NULL)
  93         {
  94                 sjinfo = &sjinfo_data;
  95                 sjinfo->type = T_SpecialJoinInfo;
  96                 sjinfo->min_lefthand = rel1->relids;
  97                 sjinfo->min_righthand = rel2->relids;
  98                 sjinfo->syn_lefthand = rel1->relids;
  99                 sjinfo->syn_righthand = rel2->relids;
 100                 sjinfo->jointype = JOIN_INNER;
 101                 /* we don't bother trying to make the remaining fields valid */
 102                 sjinfo->lhs_strict = false;
 103                 sjinfo->delay_upper_joins = false;
 104                 sjinfo->join_quals = NIL;
 105         }
 106
 107         /*
 108          * Find or build the join RelOptInfo, and compute the restrictlist that
 109          * goes with this particular joining.
 110          */
 111         joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
 112                                                          &restrictlist);
 113
 114         /* Apply appropriate Rows hint to the join node, if any. */
 115         for (i = 0; i < current_hint->num_hints[HINT_TYPE_ROWS]; i++)
 116         {
 117                 rows_hint = current_hint->rows_hints[i];
 118
 119                 if (bms_equal(joinrelids, rows_hint->joinrelids))
 120                 {
 121                         /*
 122                          * This join RelOptInfo is exactly a Rows hint specifies, so adjust
 123                          * rows estimateion with the hint's content.  Here we never have
 124                          * another hint which has same relation combination, so we can skip
 125                          * rest of hints.
 126                          */
 127                         if (rows_hint->base.state == HINT_STATE_NOTUSED)
 128                                 joinrel->rows = adjust_rows(joinrel->rows, rows_hint);
 129                 }
 130                 else if (bms_is_subset(rows_hint->joinrelids, rel1->relids) ||
 131                                  bms_is_subset(rows_hint->joinrelids, rel2->relids))
 132                 {
 133                         /*
 134                          * Otherwise if the relation combination specified in thee Rows
 135                          * hint is subset of the set of join elements, re-estimate rows and
 136                          * costs again to reflect the adjustment done in down.  This is
 137                          * necessary for the first permutation of the combination the
 138                          * relations, but it's difficult to determine that this is the
 139                          * first, so do this everytime.
 140                          */
 141                         set_joinrel_size_estimates(root, joinrel, rel1, rel2, sjinfo,
 142                                                                            restrictlist);
 143                 }
 144                 else if (bms_is_subset(rows_hint->joinrelids, joinrelids))
 145                 {
 146                         /*
 147                          * If the combination specifed in the Rows hints is subset of the
 148                          * join relation and spreads over both children,
 149                          *
 150                          * We do adjust rows estimation only when the value type was
 151                          * multiplication, because other value types are meanless.
 152                          */
 153                         if (rows_hint->value_type == RVT_MULTI)
 154                         {
 155                                 set_joinrel_size_estimates(root, joinrel, rel1, rel2, sjinfo,
 156                                                                                    restrictlist);
 157                                 joinrel->rows = adjust_rows(joinrel->rows, rows_hint);
 158                         }
 159                 }
 160         }
 161
 162         /*
 163          * If we've already proven this join is empty, we needn't consider any
 164          * more paths for it.
 165          */
 166         if (is_dummy_rel(joinrel))
 167         {
 168                 bms_free(joinrelids);
 169                 return joinrel;
 170         }
 171
 172         /*
 173          * Consider paths using each rel as both outer and inner.  Depending on
 174          * the join type, a provably empty outer or inner rel might mean the join
 175          * is provably empty too; in which case throw away any previously computed
 176          * paths and mark the join as dummy.  (We do it this way since it's
 177          * conceivable that dummy-ness of a multi-element join might only be
 178          * noticeable for certain construction paths.)
 179          *
 180          * Also, a provably constant-false join restriction typically means that
 181          * we can skip evaluating one or both sides of the join.  We do this by
 182          * marking the appropriate rel as dummy.  For outer joins, a
 183          * constant-false restriction that is pushed down still means the whole
 184          * join is dummy, while a non-pushed-down one means that no inner rows
 185          * will join so we can treat the inner rel as dummy.
 186          *
 187          * We need only consider the jointypes that appear in join_info_list, plus
 188          * JOIN_INNER.
 189          */
 190         switch (sjinfo->jointype)
 191         {
 192                 case JOIN_INNER:
 193                         if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 194                                 restriction_is_constant_false(restrictlist, false))
 195                         {
 196                                 mark_dummy_rel(joinrel);
 197                                 break;
 198                         }
 199                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 200                                                                  JOIN_INNER, sjinfo,
 201                                                                  restrictlist);
 202                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 203                                                                  JOIN_INNER, sjinfo,
 204                                                                  restrictlist);
 205                         break;
 206                 case JOIN_LEFT:
 207                         if (is_dummy_rel(rel1) ||
 208                                 restriction_is_constant_false(restrictlist, true))
 209                         {
 210                                 mark_dummy_rel(joinrel);
 211                                 break;
 212                         }
 213                         if (restriction_is_constant_false(restrictlist, false) &&
 214                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 215                                 mark_dummy_rel(rel2);
 216                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 217                                                                  JOIN_LEFT, sjinfo,
 218                                                                  restrictlist);
 219                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 220                                                                  JOIN_RIGHT, sjinfo,
 221                                                                  restrictlist);
 222                         break;
 223                 case JOIN_FULL:
 224                         if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
 225                                 restriction_is_constant_false(restrictlist, true))
 226                         {
 227                                 mark_dummy_rel(joinrel);
 228                                 break;
 229                         }
 230                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 231                                                                  JOIN_FULL, sjinfo,
 232                                                                  restrictlist);
 233                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 234                                                                  JOIN_FULL, sjinfo,
 235                                                                  restrictlist);
 236
 237                         /*
 238                          * If there are join quals that aren't mergeable or hashable, we
 239                          * may not be able to build any valid plan.  Complain here so that
 240                          * we can give a somewhat-useful error message.  (Since we have no
 241                          * flexibility of planning for a full join, there's no chance of
 242                          * succeeding later with another pair of input rels.)
 243                          */
 244                         if (joinrel->pathlist == NIL)
 245                                 ereport(ERROR,
 246                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 247                                                  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
 248                         break;
 249                 case JOIN_SEMI:
 250
 251                         /*
 252                          * We might have a normal semijoin, or a case where we don't have
 253                          * enough rels to do the semijoin but can unique-ify the RHS and
 254                          * then do an innerjoin (see comments in join_is_legal).  In the
 255                          * latter case we can't apply JOIN_SEMI joining.
 256                          */
 257                         if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 258                                 bms_is_subset(sjinfo->min_righthand, rel2->relids))
 259                         {
 260                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 261                                         restriction_is_constant_false(restrictlist, false))
 262                                 {
 263                                         mark_dummy_rel(joinrel);
 264                                         break;
 265                                 }
 266                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 267                                                                          JOIN_SEMI, sjinfo,
 268                                                                          restrictlist);
 269                         }
 270
 271                         /*
 272                          * If we know how to unique-ify the RHS and one input rel is
 273                          * exactly the RHS (not a superset) we can consider unique-ifying
 274                          * it and then doing a regular join.  (The create_unique_path
 275                          * check here is probably redundant with what join_is_legal did,
 276                          * but if so the check is cheap because it's cached.  So test
 277                          * anyway to be sure.)
 278                          */
 279                         if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
 280                                 create_unique_path(root, rel2, rel2->cheapest_total_path,
 281                                                                    sjinfo) != NULL)
 282                         {
 283                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 284                                         restriction_is_constant_false(restrictlist, false))
 285                                 {
 286                                         mark_dummy_rel(joinrel);
 287                                         break;
 288                                 }
 289                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 290                                                                          JOIN_UNIQUE_INNER, sjinfo,
 291                                                                          restrictlist);
 292                                 add_paths_to_joinrel(root, joinrel, rel2, rel1,
 293                                                                          JOIN_UNIQUE_OUTER, sjinfo,
 294                                                                          restrictlist);
 295                         }
 296                         break;
 297                 case JOIN_ANTI:
 298                         if (is_dummy_rel(rel1) ||
 299                                 restriction_is_constant_false(restrictlist, true))
 300                         {
 301                                 mark_dummy_rel(joinrel);
 302                                 break;
 303                         }
 304                         if (restriction_is_constant_false(restrictlist, false) &&
 305                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 306                                 mark_dummy_rel(rel2);
 307                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 308                                                                  JOIN_ANTI, sjinfo,
 309                                                                  restrictlist);
 310                         break;
 311                 default:
 312                         /* other values not expected here */
 313                         elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
 314                         break;
 315         }
 316
 317         bms_free(joinrelids);
 318
 319         return joinrel;
 320 }