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