core.c

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