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  * adjust_rows: tweak estimated row numbers according to the hint.
  18 */
  19 static double
  20 adjust_rows(double rows, RowsHint *hint)
  21 {
  22         double          result = 0.0;   /* keep compiler quiet */
  23
  24         if (hint->value_type == RVT_ABSOLUTE)
  25                 result = hint->rows;
  26         else if (hint->value_type == RVT_ADD)
  27                 result = rows + hint->rows;
  28         else if (hint->value_type == RVT_SUB)
  29                 result =  rows - hint->rows;
  30         else if (hint->value_type == RVT_MULTI)
  31                 result = rows * hint->rows;
  32         else
  33                 Assert(false);  /* unrecognized rows value type */
  34
  35         hint->base.state = HINT_STATE_USED;
  36         if (result < 1.0)
  37                 ereport(WARNING,
  38                                 (errmsg("Force estimate to be at least one row, to avoid possible divide-by-zero when interpolating costs : %s",
  39                                         hint->base.hint_str)));
  40         result = clamp_row_est(result);
  41         elog(DEBUG1, "adjusted rows %d to %d", (int) rows, (int) result);
  42
  43         return result;
  44 }
  45
  46 /*
  47  * make_join_rel
  48  *         Find or create a join RelOptInfo that represents the join of
  49  *         the two given rels, and add to it path information for paths
  50  *         created with the two rels as outer and inner rel.
  51  *         (The join rel may already contain paths generated from other
  52  *         pairs of rels that add up to the same set of base rels.)
  53  *
  54  * NB: will return NULL if attempted join is not valid.  This can happen
  55  * when working with outer joins, or with IN or EXISTS clauses that have been
  56  * turned into joins.
  57  */
  58 RelOptInfo *
  59 make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
  60 {
  61         Relids          joinrelids;
  62         SpecialJoinInfo *sjinfo;
  63         bool            reversed;
  64         SpecialJoinInfo sjinfo_data;
  65         RelOptInfo *joinrel;
  66         List       *restrictlist;
  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         /* !!! START: HERE IS THE PART WHICH ADDED FOR PG_HINT_PLAN !!! */
 120         {
 121                 RowsHint   *rows_hint = NULL;
 122                 int                     i;
 123                 RowsHint   *justforme = NULL;
 124                 RowsHint   *domultiply = NULL;
 125
 126                 /* Search for applicable rows hint for this join node */
 127                 for (i = 0; i < current_hint->num_hints[HINT_TYPE_ROWS]; i++)
 128                 {
 129                         rows_hint = current_hint->rows_hints[i];
 130
 131                         /*
 132                          * Skip this rows_hint if it is invalid from the first or it
 133                          * doesn't target any join rels.
 134                          */
 135                         if (!rows_hint->joinrelids ||
 136                                 rows_hint->base.state == HINT_STATE_ERROR)
 137                                 continue;
 138
 139                         if (bms_equal(joinrelids, rows_hint->joinrelids))
 140                         {
 141                                 /*
 142                                  * This joinrel is just the target of this rows_hint, so tweak
 143                                  * rows estimation according to the hint.
 144                                  */
 145                                 justforme = rows_hint;
 146                         }
 147                         else if (!(bms_is_subset(rows_hint->joinrelids, rel1->relids) ||
 148                                            bms_is_subset(rows_hint->joinrelids, rel2->relids)) &&
 149                                          bms_is_subset(rows_hint->joinrelids, joinrelids) &&
 150                                          rows_hint->value_type == RVT_MULTI)
 151                         {
 152                                 /*
 153                                  * If the rows_hint's target relids is not a subset of both of
 154                                  * component rels and is a subset of this joinrel, ths hint's
 155                                  * targets spread over both component rels. This menas that
 156                                  * this hint has been never applied so far and this joinrel is
 157                                  * the first (and only) chance to fire in current join tree.
 158                                  * Only the multiplication hint has the cumulative nature so we
 159                                  * apply only RVT_MULTI in this way.
 160                                  */
 161                                 domultiply = rows_hint;
 162                         }
 163                 }
 164
 165                 if (justforme)
 166                 {
 167                         /*
 168                          * If a hint just for me is found, no other adjust method is
 169                          * useles, but this cannot be more than twice becuase this joinrel
 170                          * is already adjusted by this hint.
 171                          */
 172                         if (justforme->base.state == HINT_STATE_NOTUSED)
 173                                 joinrel->rows = adjust_rows(joinrel->rows, justforme);
 174                 }
 175                 else
 176                 {
 177                         if (domultiply)
 178                         {
 179                                 /*
 180                                  * If we have multiple routes up to this joinrel which are not
 181                                  * applicable this hint, this multiply hint will applied more
 182                                  * than twice. But there's no means to know of that,
 183                                  * re-estimate the row number of this joinrel always just
 184                                  * before applying the hint. This is a bit different from
 185                                  * normal planner behavior but it doesn't harm so much.
 186                                  */
 187                                 set_joinrel_size_estimates(root, joinrel, rel1, rel2, sjinfo,
 188                                                                                    restrictlist);
 189
 190                                 joinrel->rows = adjust_rows(joinrel->rows, domultiply);
 191                         }
 192
 193                 }
 194         }
 195         /* !!! END: HERE IS THE PART WHICH ADDED FOR PG_HINT_PLAN !!! */
 196
 197         /*
 198          * If we've already proven this join is empty, we needn't consider any
 199          * more paths for it.
 200          */
 201         if (is_dummy_rel(joinrel))
 202         {
 203                 bms_free(joinrelids);
 204                 return joinrel;
 205         }
 206
 207         /*
 208          * Consider paths using each rel as both outer and inner.  Depending on
 209          * the join type, a provably empty outer or inner rel might mean the join
 210          * is provably empty too; in which case throw away any previously computed
 211          * paths and mark the join as dummy.  (We do it this way since it's
 212          * conceivable that dummy-ness of a multi-element join might only be
 213          * noticeable for certain construction paths.)
 214          *
 215          * Also, a provably constant-false join restriction typically means that
 216          * we can skip evaluating one or both sides of the join.  We do this by
 217          * marking the appropriate rel as dummy.  For outer joins, a
 218          * constant-false restriction that is pushed down still means the whole
 219          * join is dummy, while a non-pushed-down one means that no inner rows
 220          * will join so we can treat the inner rel as dummy.
 221          *
 222          * We need only consider the jointypes that appear in join_info_list, plus
 223          * JOIN_INNER.
 224          */
 225         switch (sjinfo->jointype)
 226         {
 227                 case JOIN_INNER:
 228                         if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 229                                 restriction_is_constant_false(restrictlist, false))
 230                         {
 231                                 mark_dummy_rel(joinrel);
 232                                 break;
 233                         }
 234                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 235                                                                  JOIN_INNER, sjinfo,
 236                                                                  restrictlist);
 237                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 238                                                                  JOIN_INNER, sjinfo,
 239                                                                  restrictlist);
 240                         break;
 241                 case JOIN_LEFT:
 242                         if (is_dummy_rel(rel1) ||
 243                                 restriction_is_constant_false(restrictlist, true))
 244                         {
 245                                 mark_dummy_rel(joinrel);
 246                                 break;
 247                         }
 248                         if (restriction_is_constant_false(restrictlist, false) &&
 249                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 250                                 mark_dummy_rel(rel2);
 251                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 252                                                                  JOIN_LEFT, sjinfo,
 253                                                                  restrictlist);
 254                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 255                                                                  JOIN_RIGHT, sjinfo,
 256                                                                  restrictlist);
 257                         break;
 258                 case JOIN_FULL:
 259                         if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
 260                                 restriction_is_constant_false(restrictlist, true))
 261                         {
 262                                 mark_dummy_rel(joinrel);
 263                                 break;
 264                         }
 265                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 266                                                                  JOIN_FULL, sjinfo,
 267                                                                  restrictlist);
 268                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 269                                                                  JOIN_FULL, sjinfo,
 270                                                                  restrictlist);
 271
 272                         /*
 273                          * If there are join quals that aren't mergeable or hashable, we
 274                          * may not be able to build any valid plan.  Complain here so that
 275                          * we can give a somewhat-useful error message.  (Since we have no
 276                          * flexibility of planning for a full join, there's no chance of
 277                          * succeeding later with another pair of input rels.)
 278                          */
 279                         if (joinrel->pathlist == NIL)
 280                                 ereport(ERROR,
 281                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 282                                                  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
 283                         break;
 284                 case JOIN_SEMI:
 285
 286                         /*
 287                          * We might have a normal semijoin, or a case where we don't have
 288                          * enough rels to do the semijoin but can unique-ify the RHS and
 289                          * then do an innerjoin (see comments in join_is_legal).  In the
 290                          * latter case we can't apply JOIN_SEMI joining.
 291                          */
 292                         if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 293                                 bms_is_subset(sjinfo->min_righthand, rel2->relids))
 294                         {
 295                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 296                                         restriction_is_constant_false(restrictlist, false))
 297                                 {
 298                                         mark_dummy_rel(joinrel);
 299                                         break;
 300                                 }
 301                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 302                                                                          JOIN_SEMI, sjinfo,
 303                                                                          restrictlist);
 304                         }
 305
 306                         /*
 307                          * If we know how to unique-ify the RHS and one input rel is
 308                          * exactly the RHS (not a superset) we can consider unique-ifying
 309                          * it and then doing a regular join.  (The create_unique_path
 310                          * check here is probably redundant with what join_is_legal did,
 311                          * but if so the check is cheap because it's cached.  So test
 312                          * anyway to be sure.)
 313                          */
 314                         if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
 315                                 create_unique_path(root, rel2, rel2->cheapest_total_path,
 316                                                                    sjinfo) != NULL)
 317                         {
 318                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 319                                         restriction_is_constant_false(restrictlist, false))
 320                                 {
 321                                         mark_dummy_rel(joinrel);
 322                                         break;
 323                                 }
 324                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 325                                                                          JOIN_UNIQUE_INNER, sjinfo,
 326                                                                          restrictlist);
 327                                 add_paths_to_joinrel(root, joinrel, rel2, rel1,
 328                                                                          JOIN_UNIQUE_OUTER, sjinfo,
 329                                                                          restrictlist);
 330                         }
 331                         break;
 332                 case JOIN_ANTI:
 333                         if (is_dummy_rel(rel1) ||
 334                                 restriction_is_constant_false(restrictlist, true))
 335                         {
 336                                 mark_dummy_rel(joinrel);
 337                                 break;
 338                         }
 339                         if (restriction_is_constant_false(restrictlist, false) &&
 340                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 341                                 mark_dummy_rel(rel2);
 342                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 343                                                                  JOIN_ANTI, sjinfo,
 344                                                                  restrictlist);
 345                         break;
 346                 default:
 347                         /* other values not expected here */
 348                         elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
 349                         break;
 350         }
 351
 352         bms_free(joinrelids);
 353
 354         return joinrel;
 355 }