core.c

   1 /*
   2  * PostgreSQL 本体から流用した関数
   3  *
   4  * src/backend/optimizer/path/allpaths.c
   5  *     standard_join_search()
   6  *     set_plain_rel_pathlist()
   7  *
   8  * src/backend/optimizer/path/joinrels.c:
   9  *     join_search_one_level()
  10  *     make_rels_by_clause_joins()
  11  *     make_rels_by_clauseless_joins()
  12  *     has_join_restriction()
  13  */
  14
  15 /*
  16  * standard_join_search
  17  *        Find possible joinpaths for a query by successively finding ways
  18  *        to join component relations into join relations.
  19  *
  20  * 'levels_needed' is the number of iterations needed, ie, the number of
  21  *              independent jointree items in the query.  This is > 1.
  22  *
  23  * 'initial_rels' is a list of RelOptInfo nodes for each independent
  24  *              jointree item.  These are the components to be joined together.
  25  *              Note that levels_needed == list_length(initial_rels).
  26  *
  27  * Returns the final level of join relations, i.e., the relation that is
  28  * the result of joining all the original relations together.
  29  * At least one implementation path must be provided for this relation and
  30  * all required sub-relations.
  31  *
  32  * To support loadable plugins that modify planner behavior by changing the
  33  * join searching algorithm, we provide a hook variable that lets a plugin
  34  * replace or supplement this function.  Any such hook must return the same
  35  * final join relation as the standard code would, but it might have a
  36  * different set of implementation paths attached, and only the sub-joinrels
  37  * needed for these paths need have been instantiated.
  38  *
  39  * Note to plugin authors: the functions invoked during standard_join_search()
  40  * modify root->join_rel_list and root->join_rel_hash.  If you want to do more
  41  * than one join-order search, you'll probably need to save and restore the
  42  * original states of those data structures.  See geqo_eval() for an example.
  43  */
  44 RelOptInfo *
  45 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
  46 {
  47         int                     lev;
  48         RelOptInfo *rel;
  49
  50         /*
  51          * This function cannot be invoked recursively within any one planning
  52          * problem, so join_rel_level[] can't be in use already.
  53          */
  54         Assert(root->join_rel_level == NULL);
  55
  56         /*
  57          * We employ a simple "dynamic programming" algorithm: we first find all
  58          * ways to build joins of two jointree items, then all ways to build joins
  59          * of three items (from two-item joins and single items), then four-item
  60          * joins, and so on until we have considered all ways to join all the
  61          * items into one rel.
  62          *
  63          * root->join_rel_level[j] is a list of all the j-item rels.  Initially we
  64          * set root->join_rel_level[1] to represent all the single-jointree-item
  65          * relations.
  66          */
  67         root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
  68
  69         root->join_rel_level[1] = initial_rels;
  70
  71         for (lev = 2; lev <= levels_needed; lev++)
  72         {
  73                 ListCell   *lc;
  74
  75                 /*
  76                  * Determine all possible pairs of relations to be joined at this
  77                  * level, and build paths for making each one from every available
  78                  * pair of lower-level relations.
  79                  */
  80                 join_search_one_level(root, lev);
  81
  82                 /*
  83                  * Do cleanup work on each just-processed rel.
  84                  */
  85                 foreach(lc, root->join_rel_level[lev])
  86                 {
  87                         rel = (RelOptInfo *) lfirst(lc);
  88
  89                         /* Find and save the cheapest paths for this rel */
  90                         set_cheapest(rel);
  91
  92 #ifdef OPTIMIZER_DEBUG
  93                         debug_print_rel(root, rel);
  94 #endif
  95                 }
  96         }
  97
  98         /*
  99          * We should have a single rel at the final level.
 100          */
 101         if (root->join_rel_level[levels_needed] == NIL)
 102                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
 103         Assert(list_length(root->join_rel_level[levels_needed]) == 1);
 104
 105         rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
 106
 107         root->join_rel_level = NULL;
 108
 109         return rel;
 110 }
 111
 112 /*
 113  * set_plain_rel_pathlist
 114  *        Build access paths for a plain relation (no subquery, no inheritance)
 115  */
 116 static void
 117 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 118 {
 119         /* Consider sequential scan */
 120         add_path(rel, create_seqscan_path(root, rel));
 121
 122         /* Consider index scans */
 123         create_index_paths(root, rel);
 124
 125         /* Consider TID scans */
 126         create_tidscan_paths(root, rel);
 127
 128         /* Now find the cheapest of the paths for this rel */
 129         set_cheapest(rel);
 130 }
 131
 132 /*
 133  * join_search_one_level
 134  *        Consider ways to produce join relations containing exactly 'level'
 135  *        jointree items.  (This is one step of the dynamic-programming method
 136  *        embodied in standard_join_search.)  Join rel nodes for each feasible
 137  *        combination of lower-level rels are created and returned in a list.
 138  *        Implementation paths are created for each such joinrel, too.
 139  *
 140  * level: level of rels we want to make this time
 141  * root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
 142  *
 143  * The result is returned in root->join_rel_level[level].
 144  */
 145 void
 146 join_search_one_level(PlannerInfo *root, int level)
 147 {
 148         List      **joinrels = root->join_rel_level;
 149         ListCell   *r;
 150         int                     k;
 151
 152         Assert(joinrels[level] == NIL);
 153
 154         /* Set join_cur_level so that new joinrels are added to proper list */
 155         root->join_cur_level = level;
 156
 157         /*
 158          * First, consider left-sided and right-sided plans, in which rels of
 159          * exactly level-1 member relations are joined against initial relations.
 160          * We prefer to join using join clauses, but if we find a rel of level-1
 161          * members that has no join clauses, we will generate Cartesian-product
 162          * joins against all initial rels not already contained in it.
 163          *
 164          * In the first pass (level == 2), we try to join each initial rel to each
 165          * initial rel that appears later in joinrels[1].  (The mirror-image joins
 166          * are handled automatically by make_join_rel.)  In later passes, we try
 167          * to join rels of size level-1 from joinrels[level-1] to each initial rel
 168          * in joinrels[1].
 169          */
 170         foreach(r, joinrels[level - 1])
 171         {
 172                 RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 173                 ListCell   *other_rels;
 174
 175                 if (level == 2)
 176                         other_rels = lnext(r);          /* only consider remaining initial
 177                                                                                  * rels */
 178                 else
 179                         other_rels = list_head(joinrels[1]);            /* consider all initial
 180                                                                                                                  * rels */
 181
 182                 if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
 183                         has_join_restriction(root, old_rel))
 184                 {
 185                         /*
 186                          * Note that if all available join clauses for this rel require
 187                          * more than one other rel, we will fail to make any joins against
 188                          * it here.  In most cases that's OK; it'll be considered by
 189                          * "bushy plan" join code in a higher-level pass where we have
 190                          * those other rels collected into a join rel.
 191                          *
 192                          * See also the last-ditch case below.
 193                          */
 194                         make_rels_by_clause_joins(root,
 195                                                                           old_rel,
 196                                                                           other_rels);
 197                 }
 198                 else
 199                 {
 200                         /*
 201                          * Oops, we have a relation that is not joined to any other
 202                          * relation, either directly or by join-order restrictions.
 203                          * Cartesian product time.
 204                          */
 205                         make_rels_by_clauseless_joins(root,
 206                                                                                   old_rel,
 207                                                                                   other_rels);
 208                 }
 209         }
 210
 211         /*
 212          * Now, consider "bushy plans" in which relations of k initial rels are
 213          * joined to relations of level-k initial rels, for 2 <= k <= level-2.
 214          *
 215          * We only consider bushy-plan joins for pairs of rels where there is a
 216          * suitable join clause (or join order restriction), in order to avoid
 217          * unreasonable growth of planning time.
 218          */
 219         for (k = 2;; k++)
 220         {
 221                 int                     other_level = level - k;
 222
 223                 /*
 224                  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
 225                  * need to go as far as the halfway point.
 226                  */
 227                 if (k > other_level)
 228                         break;
 229
 230                 foreach(r, joinrels[k])
 231                 {
 232                         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 233                         ListCell   *other_rels;
 234                         ListCell   *r2;
 235
 236                         /*
 237                          * We can ignore clauseless joins here, *except* when they
 238                          * participate in join-order restrictions --- then we might have
 239                          * to force a bushy join plan.
 240                          */
 241                         if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
 242                                 !has_join_restriction(root, old_rel))
 243                                 continue;
 244
 245                         if (k == other_level)
 246                                 other_rels = lnext(r);  /* only consider remaining rels */
 247                         else
 248                                 other_rels = list_head(joinrels[other_level]);
 249
 250                         for_each_cell(r2, other_rels)
 251                         {
 252                                 RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
 253
 254                                 if (!bms_overlap(old_rel->relids, new_rel->relids))
 255                                 {
 256                                         /*
 257                                          * OK, we can build a rel of the right level from this
 258                                          * pair of rels.  Do so if there is at least one usable
 259                                          * join clause or a relevant join restriction.
 260                                          */
 261                                         if (have_relevant_joinclause(root, old_rel, new_rel) ||
 262                                                 have_join_order_restriction(root, old_rel, new_rel))
 263                                         {
 264                                                 (void) make_join_rel(root, old_rel, new_rel);
 265                                         }
 266                                 }
 267                         }
 268                 }
 269         }
 270
 271         /*
 272          * Last-ditch effort: if we failed to find any usable joins so far, force
 273          * a set of cartesian-product joins to be generated.  This handles the
 274          * special case where all the available rels have join clauses but we
 275          * cannot use any of those clauses yet.  An example is
 276          *
 277          * SELECT * FROM a,b,c WHERE (a.f1 + b.f2 + c.f3) = 0;
 278          *
 279          * The join clause will be usable at level 3, but at level 2 we have no
 280          * choice but to make cartesian joins.  We consider only left-sided and
 281          * right-sided cartesian joins in this case (no bushy).
 282          */
 283         if (joinrels[level] == NIL)
 284         {
 285                 /*
 286                  * This loop is just like the first one, except we always call
 287                  * make_rels_by_clauseless_joins().
 288                  */
 289                 foreach(r, joinrels[level - 1])
 290                 {
 291                         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 292                         ListCell   *other_rels;
 293
 294                         if (level == 2)
 295                                 other_rels = lnext(r);  /* only consider remaining initial
 296                                                                                  * rels */
 297                         else
 298                                 other_rels = list_head(joinrels[1]);    /* consider all initial
 299                                                                                                                  * rels */
 300
 301                         make_rels_by_clauseless_joins(root,
 302                                                                                   old_rel,
 303                                                                                   other_rels);
 304                 }
 305
 306                 /*----------
 307                  * When special joins are involved, there may be no legal way
 308                  * to make an N-way join for some values of N.  For example consider
 309                  *
 310                  * SELECT ... FROM t1 WHERE
 311                  *       x IN (SELECT ... FROM t2,t3 WHERE ...) AND
 312                  *       y IN (SELECT ... FROM t4,t5 WHERE ...)
 313                  *
 314                  * We will flatten this query to a 5-way join problem, but there are
 315                  * no 4-way joins that join_is_legal() will consider legal.  We have
 316                  * to accept failure at level 4 and go on to discover a workable
 317                  * bushy plan at level 5.
 318                  *
 319                  * However, if there are no special joins then join_is_legal() should
 320                  * never fail, and so the following sanity check is useful.
 321                  *----------
 322                  */
 323                 if (joinrels[level] == NIL && root->join_info_list == NIL)
 324                         elog(ERROR, "failed to build any %d-way joins", level);
 325         }
 326 }
 327
 328 /*
 329  * make_rels_by_clause_joins
 330  *        Build joins between the given relation 'old_rel' and other relations
 331  *        that participate in join clauses that 'old_rel' also participates in
 332  *        (or participate in join-order restrictions with it).
 333  *        The join rels are returned in root->join_rel_level[join_cur_level].
 334  *
 335  * Note: at levels above 2 we will generate the same joined relation in
 336  * multiple ways --- for example (a join b) join c is the same RelOptInfo as
 337  * (b join c) join a, though the second case will add a different set of Paths
 338  * to it.  This is the reason for using the join_rel_level mechanism, which
 339  * automatically ensures that each new joinrel is only added to the list once.
 340  *
 341  * 'old_rel' is the relation entry for the relation to be joined
 342  * 'other_rels': the first cell in a linked list containing the other
 343  * rels to be considered for joining
 344  *
 345  * Currently, this is only used with initial rels in other_rels, but it
 346  * will work for joining to joinrels too.
 347  */
 348 static void
 349 make_rels_by_clause_joins(PlannerInfo *root,
 350                                                   RelOptInfo *old_rel,
 351                                                   ListCell *other_rels)
 352 {
 353         ListCell   *l;
 354
 355         for_each_cell(l, other_rels)
 356         {
 357                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 358
 359                 if (!bms_overlap(old_rel->relids, other_rel->relids) &&
 360                         (have_relevant_joinclause(root, old_rel, other_rel) ||
 361                          have_join_order_restriction(root, old_rel, other_rel)))
 362                 {
 363                         (void) make_join_rel(root, old_rel, other_rel);
 364                 }
 365         }
 366 }
 367
 368 /*
 369  * make_rels_by_clauseless_joins
 370  *        Given a relation 'old_rel' and a list of other relations
 371  *        'other_rels', create a join relation between 'old_rel' and each
 372  *        member of 'other_rels' that isn't already included in 'old_rel'.
 373  *        The join rels are returned in root->join_rel_level[join_cur_level].
 374  *
 375  * 'old_rel' is the relation entry for the relation to be joined
 376  * 'other_rels': the first cell of a linked list containing the
 377  * other rels to be considered for joining
 378  *
 379  * Currently, this is only used with initial rels in other_rels, but it would
 380  * work for joining to joinrels too.
 381  */
 382 static void
 383 make_rels_by_clauseless_joins(PlannerInfo *root,
 384                                                           RelOptInfo *old_rel,
 385                                                           ListCell *other_rels)
 386 {
 387         ListCell   *l;
 388
 389         for_each_cell(l, other_rels)
 390         {
 391                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 392
 393                 if (!bms_overlap(other_rel->relids, old_rel->relids))
 394                 {
 395                         (void) make_join_rel(root, old_rel, other_rel);
 396                 }
 397         }
 398 }
 399
 400 /*
 401  * has_join_restriction
 402  *              Detect whether the specified relation has join-order restrictions
 403  *              due to being inside an outer join or an IN (sub-SELECT).
 404  *
 405  * Essentially, this tests whether have_join_order_restriction() could
 406  * succeed with this rel and some other one.  It's OK if we sometimes
 407  * say "true" incorrectly.      (Therefore, we don't bother with the relatively
 408  * expensive has_legal_joinclause test.)
 409  */
 410 static bool
 411 has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
 412 {
 413         ListCell   *l;
 414
 415         foreach(l, root->join_info_list)
 416         {
 417                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
 418
 419                 /* ignore full joins --- other mechanisms preserve their ordering */
 420                 if (sjinfo->jointype == JOIN_FULL)
 421                         continue;
 422
 423                 /* ignore if SJ is already contained in rel */
 424                 if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
 425                         bms_is_subset(sjinfo->min_righthand, rel->relids))
 426                         continue;
 427
 428                 /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
 429                 if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
 430                         bms_overlap(sjinfo->min_righthand, rel->relids))
 431                         return true;
 432         }
 433
 434         return false;
 435 }