make_join_rel.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * make_join_rel.c
   4  *        Routines copied from PostgreSQL core distribution with some
   5  *        modifications.
   6  *
   7  * src/backend/optimizer/path/joinrels.c
   8  *
   9  * This file contains the following functions from corresponding files.
  10  *
  11  *      static functions:
  12  *     make_join_rel()
  13  *     populate_joinrel_with_paths()
  14  *
  15  * Portions Copyright (c) 2013-2020, NIPPON TELEGRAPH AND TELEPHONE CORPORATION
  16  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
  17  * Portions Copyright (c) 1994, Regents of the University of California
  18  *
  19  *-------------------------------------------------------------------------
  20  */
  21
  22 /*
  23  * adjust_rows: tweak estimated row numbers according to the hint.
  24  */
  25 static double
  26 adjust_rows(double rows, RowsHint *hint)
  27 {
  28         double          result = 0.0;   /* keep compiler quiet */
  29
  30         if (hint->value_type == RVT_ABSOLUTE)
  31                 result = hint->rows;
  32         else if (hint->value_type == RVT_ADD)
  33                 result = rows + hint->rows;
  34         else if (hint->value_type == RVT_SUB)
  35                 result =  rows - hint->rows;
  36         else if (hint->value_type == RVT_MULTI)
  37                 result = rows * hint->rows;
  38         else
  39                 Assert(false);  /* unrecognized rows value type */
  40
  41         hint->base.state = HINT_STATE_USED;
  42         if (result < 1.0)
  43                 ereport(WARNING,
  44                                 (errmsg("Force estimate to be at least one row, to avoid possible divide-by-zero when interpolating costs : %s",
  45                                         hint->base.hint_str)));
  46         result = clamp_row_est(result);
  47         elog(DEBUG1, "adjusted rows %d to %d", (int) rows, (int) result);
  48
  49         return result;
  50 }
  51
  52
  53 /*
  54  * make_join_rel
  55  *         Find or create a join RelOptInfo that represents the join of
  56  *         the two given rels, and add to it path information for paths
  57  *         created with the two rels as outer and inner rel.
  58  *         (The join rel may already contain paths generated from other
  59  *         pairs of rels that add up to the same set of base rels.)
  60  *
  61  * NB: will return NULL if attempted join is not valid.  This can happen
  62  * when working with outer joins, or with IN or EXISTS clauses that have been
  63  * turned into joins.
  64  */
  65 RelOptInfo *
  66 make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
  67 {
  68         Relids          joinrelids;
  69         SpecialJoinInfo *sjinfo;
  70         bool            reversed;
  71         SpecialJoinInfo sjinfo_data;
  72         RelOptInfo *joinrel;
  73         List       *restrictlist;
  74
  75         /* We should never try to join two overlapping sets of rels. */
  76         Assert(!bms_overlap(rel1->relids, rel2->relids));
  77
  78         /* Construct Relids set that identifies the joinrel. */
  79         joinrelids = bms_union(rel1->relids, rel2->relids);
  80
  81         /* Check validity and determine join type. */
  82         if (!join_is_legal(root, rel1, rel2, joinrelids,
  83                                            &sjinfo, &reversed))
  84         {
  85                 /* invalid join path */
  86                 bms_free(joinrelids);
  87                 return NULL;
  88         }
  89
  90         /* Swap rels if needed to match the join info. */
  91         if (reversed)
  92         {
  93                 RelOptInfo *trel = rel1;
  94
  95                 rel1 = rel2;
  96                 rel2 = trel;
  97         }
  98
  99         /*
 100          * If it's a plain inner join, then we won't have found anything in
 101          * join_info_list.  Make up a SpecialJoinInfo so that selectivity
 102          * estimation functions will know what's being joined.
 103          */
 104         if (sjinfo == NULL)
 105         {
 106                 sjinfo = &sjinfo_data;
 107                 sjinfo->type = T_SpecialJoinInfo;
 108                 sjinfo->min_lefthand = rel1->relids;
 109                 sjinfo->min_righthand = rel2->relids;
 110                 sjinfo->syn_lefthand = rel1->relids;
 111                 sjinfo->syn_righthand = rel2->relids;
 112                 sjinfo->jointype = JOIN_INNER;
 113                 /* we don't bother trying to make the remaining fields valid */
 114                 sjinfo->lhs_strict = false;
 115                 sjinfo->delay_upper_joins = false;
 116                 sjinfo->semi_can_btree = false;
 117                 sjinfo->semi_can_hash = false;
 118                 sjinfo->semi_operators = NIL;
 119                 sjinfo->semi_rhs_exprs = NIL;
 120         }
 121
 122         /*
 123          * Find or build the join RelOptInfo, and compute the restrictlist that
 124          * goes with this particular joining.
 125          */
 126         joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
 127                                                          &restrictlist);
 128
 129         /* !!! START: HERE IS THE PART WHICH IS ADDED FOR PG_HINT_PLAN !!! */
 130         {
 131                 RowsHint   *rows_hint = NULL;
 132                 int                     i;
 133                 RowsHint   *justforme = NULL;
 134                 RowsHint   *domultiply = NULL;
 135
 136                 /* Search for applicable rows hint for this join node */
 137                 for (i = 0; i < current_hint_state->num_hints[HINT_TYPE_ROWS]; i++)
 138                 {
 139                         rows_hint = current_hint_state->rows_hints[i];
 140
 141                         /*
 142                          * Skip this rows_hint if it is invalid from the first or it
 143                          * doesn't target any join rels.
 144                          */
 145                         if (!rows_hint->joinrelids ||
 146                                 rows_hint->base.state == HINT_STATE_ERROR)
 147                                 continue;
 148
 149                         if (bms_equal(joinrelids, rows_hint->joinrelids))
 150                         {
 151                                 /*
 152                                  * This joinrel is just the target of this rows_hint, so tweak
 153                                  * rows estimation according to the hint.
 154                                  */
 155                                 justforme = rows_hint;
 156                         }
 157                         else if (!(bms_is_subset(rows_hint->joinrelids, rel1->relids) ||
 158                                            bms_is_subset(rows_hint->joinrelids, rel2->relids)) &&
 159                                          bms_is_subset(rows_hint->joinrelids, joinrelids) &&
 160                                          rows_hint->value_type == RVT_MULTI)
 161                         {
 162                                 /*
 163                                  * If the rows_hint's target relids is not a subset of both of
 164                                  * component rels and is a subset of this joinrel, ths hint's
 165                                  * targets spread over both component rels. This menas that
 166                                  * this hint has been never applied so far and this joinrel is
 167                                  * the first (and only) chance to fire in current join tree.
 168                                  * Only the multiplication hint has the cumulative nature so we
 169                                  * apply only RVT_MULTI in this way.
 170                                  */
 171                                 domultiply = rows_hint;
 172                         }
 173                 }
 174
 175                 if (justforme)
 176                 {
 177                         /*
 178                          * If a hint just for me is found, no other adjust method is
 179                          * useles, but this cannot be more than twice becuase this joinrel
 180                          * is already adjusted by this hint.
 181                          */
 182                         if (justforme->base.state == HINT_STATE_NOTUSED)
 183                                 joinrel->rows = adjust_rows(joinrel->rows, justforme);
 184                 }
 185                 else
 186                 {
 187                         if (domultiply)
 188                         {
 189                                 /*
 190                                  * If we have multiple routes up to this joinrel which are not
 191                                  * applicable this hint, this multiply hint will applied more
 192                                  * than twice. But there's no means to know of that,
 193                                  * re-estimate the row number of this joinrel always just
 194                                  * before applying the hint. This is a bit different from
 195                                  * normal planner behavior but it doesn't harm so much.
 196                                  */
 197                                 set_joinrel_size_estimates(root, joinrel, rel1, rel2, sjinfo,
 198                                                                                    restrictlist);
 199
 200                                 joinrel->rows = adjust_rows(joinrel->rows, domultiply);
 201                         }
 202
 203                 }
 204         }
 205         /* !!! END: HERE IS THE PART WHICH IS ADDED FOR PG_HINT_PLAN !!! */
 206
 207         /*
 208          * If we've already proven this join is empty, we needn't consider any
 209          * more paths for it.
 210          */
 211         if (is_dummy_rel(joinrel))
 212         {
 213                 bms_free(joinrelids);
 214                 return joinrel;
 215         }
 216
 217         /* Add paths to the join relation. */
 218         populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
 219                                                                 restrictlist);
 220
 221         bms_free(joinrelids);
 222
 223         return joinrel;
 224 }
 225
 226
 227 /*
 228  * populate_joinrel_with_paths
 229  *        Add paths to the given joinrel for given pair of joining relations. The
 230  *        SpecialJoinInfo provides details about the join and the restrictlist
 231  *        contains the join clauses and the other clauses applicable for given pair
 232  *        of the joining relations.
 233  */
 234 static void
 235 populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
 236                                                         RelOptInfo *rel2, RelOptInfo *joinrel,
 237                                                         SpecialJoinInfo *sjinfo, List *restrictlist)
 238 {
 239         /*
 240          * Consider paths using each rel as both outer and inner.  Depending on
 241          * the join type, a provably empty outer or inner rel might mean the join
 242          * is provably empty too; in which case throw away any previously computed
 243          * paths and mark the join as dummy.  (We do it this way since it's
 244          * conceivable that dummy-ness of a multi-element join might only be
 245          * noticeable for certain construction paths.)
 246          *
 247          * Also, a provably constant-false join restriction typically means that
 248          * we can skip evaluating one or both sides of the join.  We do this by
 249          * marking the appropriate rel as dummy.  For outer joins, a
 250          * constant-false restriction that is pushed down still means the whole
 251          * join is dummy, while a non-pushed-down one means that no inner rows
 252          * will join so we can treat the inner rel as dummy.
 253          *
 254          * We need only consider the jointypes that appear in join_info_list, plus
 255          * JOIN_INNER.
 256          */
 257         switch (sjinfo->jointype)
 258         {
 259                 case JOIN_INNER:
 260                         if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 261                                 restriction_is_constant_false(restrictlist, joinrel, false))
 262                         {
 263                                 mark_dummy_rel(joinrel);
 264                                 break;
 265                         }
 266                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 267                                                                  JOIN_INNER, sjinfo,
 268                                                                  restrictlist);
 269                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 270                                                                  JOIN_INNER, sjinfo,
 271                                                                  restrictlist);
 272                         break;
 273                 case JOIN_LEFT:
 274                         if (is_dummy_rel(rel1) ||
 275                                 restriction_is_constant_false(restrictlist, joinrel, true))
 276                         {
 277                                 mark_dummy_rel(joinrel);
 278                                 break;
 279                         }
 280                         if (restriction_is_constant_false(restrictlist, joinrel, false) &&
 281                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 282                                 mark_dummy_rel(rel2);
 283                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 284                                                                  JOIN_LEFT, sjinfo,
 285                                                                  restrictlist);
 286                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 287                                                                  JOIN_RIGHT, sjinfo,
 288                                                                  restrictlist);
 289                         break;
 290                 case JOIN_FULL:
 291                         if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
 292                                 restriction_is_constant_false(restrictlist, joinrel, true))
 293                         {
 294                                 mark_dummy_rel(joinrel);
 295                                 break;
 296                         }
 297                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 298                                                                  JOIN_FULL, sjinfo,
 299                                                                  restrictlist);
 300                         add_paths_to_joinrel(root, joinrel, rel2, rel1,
 301                                                                  JOIN_FULL, sjinfo,
 302                                                                  restrictlist);
 303
 304                         /*
 305                          * If there are join quals that aren't mergeable or hashable, we
 306                          * may not be able to build any valid plan.  Complain here so that
 307                          * we can give a somewhat-useful error message.  (Since we have no
 308                          * flexibility of planning for a full join, there's no chance of
 309                          * succeeding later with another pair of input rels.)
 310                          */
 311                         if (joinrel->pathlist == NIL)
 312                                 ereport(ERROR,
 313                                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 314                                                  errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
 315                         break;
 316                 case JOIN_SEMI:
 317
 318                         /*
 319                          * We might have a normal semijoin, or a case where we don't have
 320                          * enough rels to do the semijoin but can unique-ify the RHS and
 321                          * then do an innerjoin (see comments in join_is_legal).  In the
 322                          * latter case we can't apply JOIN_SEMI joining.
 323                          */
 324                         if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 325                                 bms_is_subset(sjinfo->min_righthand, rel2->relids))
 326                         {
 327                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 328                                         restriction_is_constant_false(restrictlist, joinrel, false))
 329                                 {
 330                                         mark_dummy_rel(joinrel);
 331                                         break;
 332                                 }
 333                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 334                                                                          JOIN_SEMI, sjinfo,
 335                                                                          restrictlist);
 336                         }
 337
 338                         /*
 339                          * If we know how to unique-ify the RHS and one input rel is
 340                          * exactly the RHS (not a superset) we can consider unique-ifying
 341                          * it and then doing a regular join.  (The create_unique_path
 342                          * check here is probably redundant with what join_is_legal did,
 343                          * but if so the check is cheap because it's cached.  So test
 344                          * anyway to be sure.)
 345                          */
 346                         if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
 347                                 create_unique_path(root, rel2, rel2->cheapest_total_path,
 348                                                                    sjinfo) != NULL)
 349                         {
 350                                 if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
 351                                         restriction_is_constant_false(restrictlist, joinrel, false))
 352                                 {
 353                                         mark_dummy_rel(joinrel);
 354                                         break;
 355                                 }
 356                                 add_paths_to_joinrel(root, joinrel, rel1, rel2,
 357                                                                          JOIN_UNIQUE_INNER, sjinfo,
 358                                                                          restrictlist);
 359                                 add_paths_to_joinrel(root, joinrel, rel2, rel1,
 360                                                                          JOIN_UNIQUE_OUTER, sjinfo,
 361                                                                          restrictlist);
 362                         }
 363                         break;
 364                 case JOIN_ANTI:
 365                         if (is_dummy_rel(rel1) ||
 366                                 restriction_is_constant_false(restrictlist, joinrel, true))
 367                         {
 368                                 mark_dummy_rel(joinrel);
 369                                 break;
 370                         }
 371                         if (restriction_is_constant_false(restrictlist, joinrel, false) &&
 372                                 bms_is_subset(rel2->relids, sjinfo->syn_righthand))
 373                                 mark_dummy_rel(rel2);
 374                         add_paths_to_joinrel(root, joinrel, rel1, rel2,
 375                                                                  JOIN_ANTI, sjinfo,
 376                                                                  restrictlist);
 377                         break;
 378                 default:
 379                         /* other values not expected here */
 380                         elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
 381                         break;
 382         }
 383
 384         /* Apply partitionwise join technique, if possible. */
 385         try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist);
 386 }