core.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * core.c
   4  *        Routines copied from PostgreSQL core distribution.
   5  *
   6  * src/backend/optimizer/path/allpaths.c
   7  *     set_plain_rel_pathlist()
   8  *     set_append_rel_pathlist()
   9  *     accumulate_append_subpath()
  10  *     set_dummy_rel_pathlist()
  11  *     standard_join_search()
  12  *
  13  * src/backend/optimizer/path/joinrels.c
  14  *     join_search_one_level()
  15  *     make_rels_by_clause_joins()
  16  *     make_rels_by_clauseless_joins()
  17  *     join_is_legal()
  18  *     has_join_restriction()
  19  *     is_dummy_rel()
  20  *     mark_dummy_rel()
  21  *     restriction_is_constant_false()
  22  *
  23  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
  24  * Portions Copyright (c) 1994, Regents of the University of California
  25  *
  26  *-------------------------------------------------------------------------
  27  */
  28
  29 /*
  30  * set_plain_rel_pathlist
  31  *        Build access paths for a plain relation (no subquery, no inheritance)
  32  */
  33 static void
  34 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
  35 {
  36         /* Consider sequential scan */
  37         add_path(rel, create_seqscan_path(root, rel));
  38
  39         /* Consider index scans */
  40         create_index_paths(root, rel);
  41
  42         /* Consider TID scans */
  43         create_tidscan_paths(root, rel);
  44
  45         /* Now find the cheapest of the paths for this rel */
  46         set_cheapest(rel);
  47 }
  48
  49 /*
  50  * set_append_rel_pathlist
  51  *        Build access paths for an "append relation"
  52  *
  53  * The passed-in rel and RTE represent the entire append relation.      The
  54  * relation's contents are computed by appending together the output of
  55  * the individual member relations.  Note that in the inheritance case,
  56  * the first member relation is actually the same table as is mentioned in
  57  * the parent RTE ... but it has a different RTE and RelOptInfo.  This is
  58  * a good thing because their outputs are not the same size.
  59  */
  60 static void
  61 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  62                                                 Index rti, RangeTblEntry *rte)
  63 {
  64         int                     parentRTindex = rti;
  65         List       *live_childrels = NIL;
  66         List       *subpaths = NIL;
  67         List       *all_child_pathkeys = NIL;
  68         double          parent_rows;
  69         double          parent_size;
  70         double     *parent_attrsizes;
  71         int                     nattrs;
  72         ListCell   *l;
  73
  74         /*
  75          * Initialize to compute size estimates for whole append relation.
  76          *
  77          * We handle width estimates by weighting the widths of different child
  78          * rels proportionally to their number of rows.  This is sensible because
  79          * the use of width estimates is mainly to compute the total relation
  80          * "footprint" if we have to sort or hash it.  To do this, we sum the
  81          * total equivalent size (in "double" arithmetic) and then divide by the
  82          * total rowcount estimate.  This is done separately for the total rel
  83          * width and each attribute.
  84          *
  85          * Note: if you consider changing this logic, beware that child rels could
  86          * have zero rows and/or width, if they were excluded by constraints.
  87          */
  88         parent_rows = 0;
  89         parent_size = 0;
  90         nattrs = rel->max_attr - rel->min_attr + 1;
  91         parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
  92
  93         /*
  94          * Generate access paths for each member relation, and pick the cheapest
  95          * path for each one.
  96          */
  97         foreach(l, root->append_rel_list)
  98         {
  99                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
 100                 int                     childRTindex;
 101                 RangeTblEntry *childRTE;
 102                 RelOptInfo *childrel;
 103                 List       *childquals;
 104                 Node       *childqual;
 105                 ListCell   *lcp;
 106                 ListCell   *parentvars;
 107                 ListCell   *childvars;
 108
 109                 /* append_rel_list contains all append rels; ignore others */
 110                 if (appinfo->parent_relid != parentRTindex)
 111                         continue;
 112
 113                 childRTindex = appinfo->child_relid;
 114                 childRTE = root->simple_rte_array[childRTindex];
 115
 116                 /*
 117                  * The child rel's RelOptInfo was already created during
 118                  * add_base_rels_to_query.
 119                  */
 120                 childrel = find_base_rel(root, childRTindex);
 121                 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
 122
 123                 /*
 124                  * We have to copy the parent's targetlist and quals to the child,
 125                  * with appropriate substitution of variables.  However, only the
 126                  * baserestrictinfo quals are needed before we can check for
 127                  * constraint exclusion; so do that first and then check to see if we
 128                  * can disregard this child.
 129                  *
 130                  * As of 8.4, the child rel's targetlist might contain non-Var
 131                  * expressions, which means that substitution into the quals could
 132                  * produce opportunities for const-simplification, and perhaps even
 133                  * pseudoconstant quals.  To deal with this, we strip the RestrictInfo
 134                  * nodes, do the substitution, do const-simplification, and then
 135                  * reconstitute the RestrictInfo layer.
 136                  */
 137                 childquals = get_all_actual_clauses(rel->baserestrictinfo);
 138                 childquals = (List *) adjust_appendrel_attrs((Node *) childquals,
 139                                                                                                          appinfo);
 140                 childqual = eval_const_expressions(root, (Node *)
 141                                                                                    make_ands_explicit(childquals));
 142                 if (childqual && IsA(childqual, Const) &&
 143                         (((Const *) childqual)->constisnull ||
 144                          !DatumGetBool(((Const *) childqual)->constvalue)))
 145                 {
 146                         /*
 147                          * Restriction reduces to constant FALSE or constant NULL after
 148                          * substitution, so this child need not be scanned.
 149                          */
 150                         set_dummy_rel_pathlist(childrel);
 151                         continue;
 152                 }
 153                 childquals = make_ands_implicit((Expr *) childqual);
 154                 childquals = make_restrictinfos_from_actual_clauses(root,
 155                                                                                                                         childquals);
 156                 childrel->baserestrictinfo = childquals;
 157
 158                 if (relation_excluded_by_constraints(root, childrel, childRTE))
 159                 {
 160                         /*
 161                          * This child need not be scanned, so we can omit it from the
 162                          * appendrel.  Mark it with a dummy cheapest-path though, in case
 163                          * best_appendrel_indexscan() looks at it later.
 164                          */
 165                         set_dummy_rel_pathlist(childrel);
 166                         continue;
 167                 }
 168
 169                 /*
 170                  * CE failed, so finish copying/modifying targetlist and join quals.
 171                  *
 172                  * Note: the resulting childrel->reltargetlist may contain arbitrary
 173                  * expressions, which normally would not occur in a reltargetlist.
 174                  * That is okay because nothing outside of this routine will look at
 175                  * the child rel's reltargetlist.  We do have to cope with the case
 176                  * while constructing attr_widths estimates below, though.
 177                  */
 178                 childrel->joininfo = (List *)
 179                         adjust_appendrel_attrs((Node *) rel->joininfo,
 180                                                                    appinfo);
 181                 childrel->reltargetlist = (List *)
 182                         adjust_appendrel_attrs((Node *) rel->reltargetlist,
 183                                                                    appinfo);
 184
 185                 /*
 186                  * We have to make child entries in the EquivalenceClass data
 187                  * structures as well.  This is needed either if the parent
 188                  * participates in some eclass joins (because we will want to consider
 189                  * inner-indexscan joins on the individual children) or if the parent
 190                  * has useful pathkeys (because we should try to build MergeAppend
 191                  * paths that produce those sort orderings).
 192                  */
 193                 if (rel->has_eclass_joins || has_useful_pathkeys(root, rel))
 194                         add_child_rel_equivalences(root, appinfo, rel, childrel);
 195                 childrel->has_eclass_joins = rel->has_eclass_joins;
 196
 197                 /*
 198                  * Note: we could compute appropriate attr_needed data for the child's
 199                  * variables, by transforming the parent's attr_needed through the
 200                  * translated_vars mapping.  However, currently there's no need
 201                  * because attr_needed is only examined for base relations not
 202                  * otherrels.  So we just leave the child's attr_needed empty.
 203                  */
 204
 205                 /* Remember which childrels are live, for MergeAppend logic below */
 206                 live_childrels = lappend(live_childrels, childrel);
 207
 208                 /*
 209                  * Compute the child's access paths, and add the cheapest one to the
 210                  * Append path we are constructing for the parent.
 211                  */
 212                 set_rel_pathlist(root, childrel, childRTindex, childRTE);
 213
 214                 subpaths = accumulate_append_subpath(subpaths,
 215                                                                                          childrel->cheapest_total_path);
 216
 217                 /*
 218                  * Collect a list of all the available path orderings for all the
 219                  * children.  We use this as a heuristic to indicate which sort
 220                  * orderings we should build MergeAppend paths for.
 221                  */
 222                 foreach(lcp, childrel->pathlist)
 223                 {
 224                         Path       *childpath = (Path *) lfirst(lcp);
 225                         List       *childkeys = childpath->pathkeys;
 226                         ListCell   *lpk;
 227                         bool            found = false;
 228
 229                         /* Ignore unsorted paths */
 230                         if (childkeys == NIL)
 231                                 continue;
 232
 233                         /* Have we already seen this ordering? */
 234                         foreach(lpk, all_child_pathkeys)
 235                         {
 236                                 List       *existing_pathkeys = (List *) lfirst(lpk);
 237
 238                                 if (compare_pathkeys(existing_pathkeys,
 239                                                                          childkeys) == PATHKEYS_EQUAL)
 240                                 {
 241                                         found = true;
 242                                         break;
 243                                 }
 244                         }
 245                         if (!found)
 246                         {
 247                                 /* No, so add it to all_child_pathkeys */
 248                                 all_child_pathkeys = lappend(all_child_pathkeys, childkeys);
 249                         }
 250                 }
 251
 252                 /*
 253                  * Accumulate size information from each child.
 254                  */
 255                 if (childrel->rows > 0)
 256                 {
 257                         parent_rows += childrel->rows;
 258                         parent_size += childrel->width * childrel->rows;
 259
 260                         /*
 261                          * Accumulate per-column estimates too.  We need not do anything
 262                          * for PlaceHolderVars in the parent list.  If child expression
 263                          * isn't a Var, or we didn't record a width estimate for it, we
 264                          * have to fall back on a datatype-based estimate.
 265                          *
 266                          * By construction, child's reltargetlist is 1-to-1 with parent's.
 267                          */
 268                         forboth(parentvars, rel->reltargetlist,
 269                                         childvars, childrel->reltargetlist)
 270                         {
 271                                 Var                *parentvar = (Var *) lfirst(parentvars);
 272                                 Node       *childvar = (Node *) lfirst(childvars);
 273
 274                                 if (IsA(parentvar, Var))
 275                                 {
 276                                         int                     pndx = parentvar->varattno - rel->min_attr;
 277                                         int32           child_width = 0;
 278
 279                                         if (IsA(childvar, Var))
 280                                         {
 281                                                 int             cndx = ((Var *) childvar)->varattno - childrel->min_attr;
 282
 283                                                 child_width = childrel->attr_widths[cndx];
 284                                         }
 285                                         if (child_width <= 0)
 286                                                 child_width = get_typavgwidth(exprType(childvar),
 287                                                                                                           exprTypmod(childvar));
 288                                         Assert(child_width > 0);
 289                                         parent_attrsizes[pndx] += child_width * childrel->rows;
 290                                 }
 291                         }
 292                 }
 293         }
 294
 295         /*
 296          * Save the finished size estimates.
 297          */
 298         rel->rows = parent_rows;
 299         if (parent_rows > 0)
 300         {
 301                 int                     i;
 302
 303                 rel->width = rint(parent_size / parent_rows);
 304                 for (i = 0; i < nattrs; i++)
 305                         rel->attr_widths[i] = rint(parent_attrsizes[i] / parent_rows);
 306         }
 307         else
 308                 rel->width = 0;                 /* attr_widths should be zero already */
 309
 310         /*
 311          * Set "raw tuples" count equal to "rows" for the appendrel; needed
 312          * because some places assume rel->tuples is valid for any baserel.
 313          */
 314         rel->tuples = parent_rows;
 315
 316         pfree(parent_attrsizes);
 317
 318         /*
 319          * Next, build an unordered Append path for the rel.  (Note: this is
 320          * correct even if we have zero or one live subpath due to constraint
 321          * exclusion.)
 322          */
 323         add_path(rel, (Path *) create_append_path(rel, subpaths));
 324
 325         /*
 326          * Next, build MergeAppend paths based on the collected list of child
 327          * pathkeys.  We consider both cheapest-startup and cheapest-total cases,
 328          * ie, for each interesting ordering, collect all the cheapest startup
 329          * subpaths and all the cheapest total paths, and build a MergeAppend path
 330          * for each list.
 331          */
 332         foreach(l, all_child_pathkeys)
 333         {
 334                 List       *pathkeys = (List *) lfirst(l);
 335                 List       *startup_subpaths = NIL;
 336                 List       *total_subpaths = NIL;
 337                 bool            startup_neq_total = false;
 338                 ListCell   *lcr;
 339
 340                 /* Select the child paths for this ordering... */
 341                 foreach(lcr, live_childrels)
 342                 {
 343                         RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
 344                         Path       *cheapest_startup,
 345                                            *cheapest_total;
 346
 347                         /* Locate the right paths, if they are available. */
 348                         cheapest_startup =
 349                                 get_cheapest_path_for_pathkeys(childrel->pathlist,
 350                                                                                            pathkeys,
 351                                                                                            STARTUP_COST);
 352                         cheapest_total =
 353                                 get_cheapest_path_for_pathkeys(childrel->pathlist,
 354                                                                                            pathkeys,
 355                                                                                            TOTAL_COST);
 356
 357                         /*
 358                          * If we can't find any paths with the right order just add the
 359                          * cheapest-total path; we'll have to sort it.
 360                          */
 361                         if (cheapest_startup == NULL)
 362                                 cheapest_startup = childrel->cheapest_total_path;
 363                         if (cheapest_total == NULL)
 364                                 cheapest_total = childrel->cheapest_total_path;
 365
 366                         /*
 367                          * Notice whether we actually have different paths for the
 368                          * "cheapest" and "total" cases; frequently there will be no point
 369                          * in two create_merge_append_path() calls.
 370                          */
 371                         if (cheapest_startup != cheapest_total)
 372                                 startup_neq_total = true;
 373
 374                         startup_subpaths =
 375                                 accumulate_append_subpath(startup_subpaths, cheapest_startup);
 376                         total_subpaths =
 377                                 accumulate_append_subpath(total_subpaths, cheapest_total);
 378                 }
 379
 380                 /* ... and build the MergeAppend paths */
 381                 add_path(rel, (Path *) create_merge_append_path(root,
 382                                                                                                                 rel,
 383                                                                                                                 startup_subpaths,
 384                                                                                                                 pathkeys));
 385                 if (startup_neq_total)
 386                         add_path(rel, (Path *) create_merge_append_path(root,
 387                                                                                                                         rel,
 388                                                                                                                         total_subpaths,
 389                                                                                                                         pathkeys));
 390         }
 391
 392         /* Select cheapest path */
 393         set_cheapest(rel);
 394 }
 395
 396 /*
 397  * accumulate_append_subpath
 398  *              Add a subpath to the list being built for an Append or MergeAppend
 399  *
 400  * It's possible that the child is itself an Append path, in which case
 401  * we can "cut out the middleman" and just add its child paths to our
 402  * own list.  (We don't try to do this earlier because we need to
 403  * apply both levels of transformation to the quals.)
 404  */
 405 static List *
 406 accumulate_append_subpath(List *subpaths, Path *path)
 407 {
 408         if (IsA(path, AppendPath))
 409         {
 410                 AppendPath *apath = (AppendPath *) path;
 411
 412                 /* list_copy is important here to avoid sharing list substructure */
 413                 return list_concat(subpaths, list_copy(apath->subpaths));
 414         }
 415         else
 416                 return lappend(subpaths, path);
 417 }
 418
 419 /*
 420  * set_dummy_rel_pathlist
 421  *        Build a dummy path for a relation that's been excluded by constraints
 422  *
 423  * Rather than inventing a special "dummy" path type, we represent this as an
 424  * AppendPath with no members (see also IS_DUMMY_PATH macro).
 425  */
 426 static void
 427 set_dummy_rel_pathlist(RelOptInfo *rel)
 428 {
 429         /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
 430         rel->rows = 0;
 431         rel->width = 0;
 432
 433         add_path(rel, (Path *) create_append_path(rel, NIL));
 434
 435         /* Select cheapest path (pretty easy in this case...) */
 436         set_cheapest(rel);
 437 }
 438
 439 /*
 440  * standard_join_search
 441  *        Find possible joinpaths for a query by successively finding ways
 442  *        to join component relations into join relations.
 443  *
 444  * 'levels_needed' is the number of iterations needed, ie, the number of
 445  *              independent jointree items in the query.  This is > 1.
 446  *
 447  * 'initial_rels' is a list of RelOptInfo nodes for each independent
 448  *              jointree item.  These are the components to be joined together.
 449  *              Note that levels_needed == list_length(initial_rels).
 450  *
 451  * Returns the final level of join relations, i.e., the relation that is
 452  * the result of joining all the original relations together.
 453  * At least one implementation path must be provided for this relation and
 454  * all required sub-relations.
 455  *
 456  * To support loadable plugins that modify planner behavior by changing the
 457  * join searching algorithm, we provide a hook variable that lets a plugin
 458  * replace or supplement this function.  Any such hook must return the same
 459  * final join relation as the standard code would, but it might have a
 460  * different set of implementation paths attached, and only the sub-joinrels
 461  * needed for these paths need have been instantiated.
 462  *
 463  * Note to plugin authors: the functions invoked during standard_join_search()
 464  * modify root->join_rel_list and root->join_rel_hash.  If you want to do more
 465  * than one join-order search, you'll probably need to save and restore the
 466  * original states of those data structures.  See geqo_eval() for an example.
 467  */
 468 RelOptInfo *
 469 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
 470 {
 471         int                     lev;
 472         RelOptInfo *rel;
 473
 474         /*
 475          * This function cannot be invoked recursively within any one planning
 476          * problem, so join_rel_level[] can't be in use already.
 477          */
 478         Assert(root->join_rel_level == NULL);
 479
 480         /*
 481          * We employ a simple "dynamic programming" algorithm: we first find all
 482          * ways to build joins of two jointree items, then all ways to build joins
 483          * of three items (from two-item joins and single items), then four-item
 484          * joins, and so on until we have considered all ways to join all the
 485          * items into one rel.
 486          *
 487          * root->join_rel_level[j] is a list of all the j-item rels.  Initially we
 488          * set root->join_rel_level[1] to represent all the single-jointree-item
 489          * relations.
 490          */
 491         root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
 492
 493         root->join_rel_level[1] = initial_rels;
 494
 495         for (lev = 2; lev <= levels_needed; lev++)
 496         {
 497                 ListCell   *lc;
 498
 499                 /*
 500                  * Determine all possible pairs of relations to be joined at this
 501                  * level, and build paths for making each one from every available
 502                  * pair of lower-level relations.
 503                  */
 504                 join_search_one_level(root, lev);
 505
 506                 /*
 507                  * Do cleanup work on each just-processed rel.
 508                  */
 509                 foreach(lc, root->join_rel_level[lev])
 510                 {
 511                         rel = (RelOptInfo *) lfirst(lc);
 512
 513                         /* Find and save the cheapest paths for this rel */
 514                         set_cheapest(rel);
 515
 516 #ifdef OPTIMIZER_DEBUG
 517                         debug_print_rel(root, rel);
 518 #endif
 519                 }
 520         }
 521
 522         /*
 523          * We should have a single rel at the final level.
 524          */
 525         if (root->join_rel_level[levels_needed] == NIL)
 526                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
 527         Assert(list_length(root->join_rel_level[levels_needed]) == 1);
 528
 529         rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
 530
 531         root->join_rel_level = NULL;
 532
 533         return rel;
 534 }
 535
 536 /*
 537  * join_search_one_level
 538  *        Consider ways to produce join relations containing exactly 'level'
 539  *        jointree items.  (This is one step of the dynamic-programming method
 540  *        embodied in standard_join_search.)  Join rel nodes for each feasible
 541  *        combination of lower-level rels are created and returned in a list.
 542  *        Implementation paths are created for each such joinrel, too.
 543  *
 544  * level: level of rels we want to make this time
 545  * root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
 546  *
 547  * The result is returned in root->join_rel_level[level].
 548  */
 549 void
 550 join_search_one_level(PlannerInfo *root, int level)
 551 {
 552         List      **joinrels = root->join_rel_level;
 553         ListCell   *r;
 554         int                     k;
 555
 556         Assert(joinrels[level] == NIL);
 557
 558         /* Set join_cur_level so that new joinrels are added to proper list */
 559         root->join_cur_level = level;
 560
 561         /*
 562          * First, consider left-sided and right-sided plans, in which rels of
 563          * exactly level-1 member relations are joined against initial relations.
 564          * We prefer to join using join clauses, but if we find a rel of level-1
 565          * members that has no join clauses, we will generate Cartesian-product
 566          * joins against all initial rels not already contained in it.
 567          *
 568          * In the first pass (level == 2), we try to join each initial rel to each
 569          * initial rel that appears later in joinrels[1].  (The mirror-image joins
 570          * are handled automatically by make_join_rel.)  In later passes, we try
 571          * to join rels of size level-1 from joinrels[level-1] to each initial rel
 572          * in joinrels[1].
 573          */
 574         foreach(r, joinrels[level - 1])
 575         {
 576                 RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 577                 ListCell   *other_rels;
 578
 579                 if (level == 2)
 580                         other_rels = lnext(r);          /* only consider remaining initial
 581                                                                                  * rels */
 582                 else
 583                         other_rels = list_head(joinrels[1]);            /* consider all initial
 584                                                                                                                  * rels */
 585
 586                 if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
 587                         has_join_restriction(root, old_rel))
 588                 {
 589                         /*
 590                          * Note that if all available join clauses for this rel require
 591                          * more than one other rel, we will fail to make any joins against
 592                          * it here.  In most cases that's OK; it'll be considered by
 593                          * "bushy plan" join code in a higher-level pass where we have
 594                          * those other rels collected into a join rel.
 595                          *
 596                          * See also the last-ditch case below.
 597                          */
 598                         make_rels_by_clause_joins(root,
 599                                                                           old_rel,
 600                                                                           other_rels);
 601                 }
 602                 else
 603                 {
 604                         /*
 605                          * Oops, we have a relation that is not joined to any other
 606                          * relation, either directly or by join-order restrictions.
 607                          * Cartesian product time.
 608                          */
 609                         make_rels_by_clauseless_joins(root,
 610                                                                                   old_rel,
 611                                                                                   other_rels);
 612                 }
 613         }
 614
 615         /*
 616          * Now, consider "bushy plans" in which relations of k initial rels are
 617          * joined to relations of level-k initial rels, for 2 <= k <= level-2.
 618          *
 619          * We only consider bushy-plan joins for pairs of rels where there is a
 620          * suitable join clause (or join order restriction), in order to avoid
 621          * unreasonable growth of planning time.
 622          */
 623         for (k = 2;; k++)
 624         {
 625                 int                     other_level = level - k;
 626
 627                 /*
 628                  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
 629                  * need to go as far as the halfway point.
 630                  */
 631                 if (k > other_level)
 632                         break;
 633
 634                 foreach(r, joinrels[k])
 635                 {
 636                         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 637                         ListCell   *other_rels;
 638                         ListCell   *r2;
 639
 640                         /*
 641                          * We can ignore clauseless joins here, *except* when they
 642                          * participate in join-order restrictions --- then we might have
 643                          * to force a bushy join plan.
 644                          */
 645                         if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
 646                                 !has_join_restriction(root, old_rel))
 647                                 continue;
 648
 649                         if (k == other_level)
 650                                 other_rels = lnext(r);  /* only consider remaining rels */
 651                         else
 652                                 other_rels = list_head(joinrels[other_level]);
 653
 654                         for_each_cell(r2, other_rels)
 655                         {
 656                                 RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
 657
 658                                 if (!bms_overlap(old_rel->relids, new_rel->relids))
 659                                 {
 660                                         /*
 661                                          * OK, we can build a rel of the right level from this
 662                                          * pair of rels.  Do so if there is at least one usable
 663                                          * join clause or a relevant join restriction.
 664                                          */
 665                                         if (have_relevant_joinclause(root, old_rel, new_rel) ||
 666                                                 have_join_order_restriction(root, old_rel, new_rel))
 667                                         {
 668                                                 (void) make_join_rel(root, old_rel, new_rel);
 669                                         }
 670                                 }
 671                         }
 672                 }
 673         }
 674
 675         /*
 676          * Last-ditch effort: if we failed to find any usable joins so far, force
 677          * a set of cartesian-product joins to be generated.  This handles the
 678          * special case where all the available rels have join clauses but we
 679          * cannot use any of those clauses yet.  An example is
 680          *
 681          * SELECT * FROM a,b,c WHERE (a.f1 + b.f2 + c.f3) = 0;
 682          *
 683          * The join clause will be usable at level 3, but at level 2 we have no
 684          * choice but to make cartesian joins.  We consider only left-sided and
 685          * right-sided cartesian joins in this case (no bushy).
 686          */
 687         if (joinrels[level] == NIL)
 688         {
 689                 /*
 690                  * This loop is just like the first one, except we always call
 691                  * make_rels_by_clauseless_joins().
 692                  */
 693                 foreach(r, joinrels[level - 1])
 694                 {
 695                         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 696                         ListCell   *other_rels;
 697
 698                         if (level == 2)
 699                                 other_rels = lnext(r);  /* only consider remaining initial
 700                                                                                  * rels */
 701                         else
 702                                 other_rels = list_head(joinrels[1]);    /* consider all initial
 703                                                                                                                  * rels */
 704
 705                         make_rels_by_clauseless_joins(root,
 706                                                                                   old_rel,
 707                                                                                   other_rels);
 708                 }
 709
 710                 /*----------
 711                  * When special joins are involved, there may be no legal way
 712                  * to make an N-way join for some values of N.  For example consider
 713                  *
 714                  * SELECT ... FROM t1 WHERE
 715                  *       x IN (SELECT ... FROM t2,t3 WHERE ...) AND
 716                  *       y IN (SELECT ... FROM t4,t5 WHERE ...)
 717                  *
 718                  * We will flatten this query to a 5-way join problem, but there are
 719                  * no 4-way joins that join_is_legal() will consider legal.  We have
 720                  * to accept failure at level 4 and go on to discover a workable
 721                  * bushy plan at level 5.
 722                  *
 723                  * However, if there are no special joins then join_is_legal() should
 724                  * never fail, and so the following sanity check is useful.
 725                  *----------
 726                  */
 727                 if (joinrels[level] == NIL && root->join_info_list == NIL)
 728                         elog(ERROR, "failed to build any %d-way joins", level);
 729         }
 730 }
 731
 732 /*
 733  * make_rels_by_clause_joins
 734  *        Build joins between the given relation 'old_rel' and other relations
 735  *        that participate in join clauses that 'old_rel' also participates in
 736  *        (or participate in join-order restrictions with it).
 737  *        The join rels are returned in root->join_rel_level[join_cur_level].
 738  *
 739  * Note: at levels above 2 we will generate the same joined relation in
 740  * multiple ways --- for example (a join b) join c is the same RelOptInfo as
 741  * (b join c) join a, though the second case will add a different set of Paths
 742  * to it.  This is the reason for using the join_rel_level mechanism, which
 743  * automatically ensures that each new joinrel is only added to the list once.
 744  *
 745  * 'old_rel' is the relation entry for the relation to be joined
 746  * 'other_rels': the first cell in a linked list containing the other
 747  * rels to be considered for joining
 748  *
 749  * Currently, this is only used with initial rels in other_rels, but it
 750  * will work for joining to joinrels too.
 751  */
 752 static void
 753 make_rels_by_clause_joins(PlannerInfo *root,
 754                                                   RelOptInfo *old_rel,
 755                                                   ListCell *other_rels)
 756 {
 757         ListCell   *l;
 758
 759         for_each_cell(l, other_rels)
 760         {
 761                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 762
 763                 if (!bms_overlap(old_rel->relids, other_rel->relids) &&
 764                         (have_relevant_joinclause(root, old_rel, other_rel) ||
 765                          have_join_order_restriction(root, old_rel, other_rel)))
 766                 {
 767                         (void) make_join_rel(root, old_rel, other_rel);
 768                 }
 769         }
 770 }
 771
 772 /*
 773  * make_rels_by_clauseless_joins
 774  *        Given a relation 'old_rel' and a list of other relations
 775  *        'other_rels', create a join relation between 'old_rel' and each
 776  *        member of 'other_rels' that isn't already included in 'old_rel'.
 777  *        The join rels are returned in root->join_rel_level[join_cur_level].
 778  *
 779  * 'old_rel' is the relation entry for the relation to be joined
 780  * 'other_rels': the first cell of a linked list containing the
 781  * other rels to be considered for joining
 782  *
 783  * Currently, this is only used with initial rels in other_rels, but it would
 784  * work for joining to joinrels too.
 785  */
 786 static void
 787 make_rels_by_clauseless_joins(PlannerInfo *root,
 788                                                           RelOptInfo *old_rel,
 789                                                           ListCell *other_rels)
 790 {
 791         ListCell   *l;
 792
 793         for_each_cell(l, other_rels)
 794         {
 795                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 796
 797                 if (!bms_overlap(other_rel->relids, old_rel->relids))
 798                 {
 799                         (void) make_join_rel(root, old_rel, other_rel);
 800                 }
 801         }
 802 }
 803
 804 /*
 805  * join_is_legal
 806  *         Determine whether a proposed join is legal given the query's
 807  *         join order constraints; and if it is, determine the join type.
 808  *
 809  * Caller must supply not only the two rels, but the union of their relids.
 810  * (We could simplify the API by computing joinrelids locally, but this
 811  * would be redundant work in the normal path through make_join_rel.)
 812  *
 813  * On success, *sjinfo_p is set to NULL if this is to be a plain inner join,
 814  * else it's set to point to the associated SpecialJoinInfo node.  Also,
 815  * *reversed_p is set TRUE if the given relations need to be swapped to
 816  * match the SpecialJoinInfo node.
 817  */
 818 static bool
 819 join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 820                           Relids joinrelids,
 821                           SpecialJoinInfo **sjinfo_p, bool *reversed_p)
 822 {
 823         SpecialJoinInfo *match_sjinfo;
 824         bool            reversed;
 825         bool            unique_ified;
 826         bool            is_valid_inner;
 827         ListCell   *l;
 828
 829         /*
 830          * Ensure output params are set on failure return.      This is just to
 831          * suppress uninitialized-variable warnings from overly anal compilers.
 832          */
 833         *sjinfo_p = NULL;
 834         *reversed_p = false;
 835
 836         /*
 837          * If we have any special joins, the proposed join might be illegal; and
 838          * in any case we have to determine its join type.      Scan the join info
 839          * list for conflicts.
 840          */
 841         match_sjinfo = NULL;
 842         reversed = false;
 843         unique_ified = false;
 844         is_valid_inner = true;
 845
 846         foreach(l, root->join_info_list)
 847         {
 848                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
 849
 850                 /*
 851                  * This special join is not relevant unless its RHS overlaps the
 852                  * proposed join.  (Check this first as a fast path for dismissing
 853                  * most irrelevant SJs quickly.)
 854                  */
 855                 if (!bms_overlap(sjinfo->min_righthand, joinrelids))
 856                         continue;
 857
 858                 /*
 859                  * Also, not relevant if proposed join is fully contained within RHS
 860                  * (ie, we're still building up the RHS).
 861                  */
 862                 if (bms_is_subset(joinrelids, sjinfo->min_righthand))
 863                         continue;
 864
 865                 /*
 866                  * Also, not relevant if SJ is already done within either input.
 867                  */
 868                 if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 869                         bms_is_subset(sjinfo->min_righthand, rel1->relids))
 870                         continue;
 871                 if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
 872                         bms_is_subset(sjinfo->min_righthand, rel2->relids))
 873                         continue;
 874
 875                 /*
 876                  * If it's a semijoin and we already joined the RHS to any other rels
 877                  * within either input, then we must have unique-ified the RHS at that
 878                  * point (see below).  Therefore the semijoin is no longer relevant in
 879                  * this join path.
 880                  */
 881                 if (sjinfo->jointype == JOIN_SEMI)
 882                 {
 883                         if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
 884                                 !bms_equal(sjinfo->syn_righthand, rel1->relids))
 885                                 continue;
 886                         if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
 887                                 !bms_equal(sjinfo->syn_righthand, rel2->relids))
 888                                 continue;
 889                 }
 890
 891                 /*
 892                  * If one input contains min_lefthand and the other contains
 893                  * min_righthand, then we can perform the SJ at this join.
 894                  *
 895                  * Barf if we get matches to more than one SJ (is that possible?)
 896                  */
 897                 if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 898                         bms_is_subset(sjinfo->min_righthand, rel2->relids))
 899                 {
 900                         if (match_sjinfo)
 901                                 return false;   /* invalid join path */
 902                         match_sjinfo = sjinfo;
 903                         reversed = false;
 904                 }
 905                 else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
 906                                  bms_is_subset(sjinfo->min_righthand, rel1->relids))
 907                 {
 908                         if (match_sjinfo)
 909                                 return false;   /* invalid join path */
 910                         match_sjinfo = sjinfo;
 911                         reversed = true;
 912                 }
 913                 else if (sjinfo->jointype == JOIN_SEMI &&
 914                                  bms_equal(sjinfo->syn_righthand, rel2->relids) &&
 915                                  create_unique_path(root, rel2, rel2->cheapest_total_path,
 916                                                                         sjinfo) != NULL)
 917                 {
 918                         /*----------
 919                          * For a semijoin, we can join the RHS to anything else by
 920                          * unique-ifying the RHS (if the RHS can be unique-ified).
 921                          * We will only get here if we have the full RHS but less
 922                          * than min_lefthand on the LHS.
 923                          *
 924                          * The reason to consider such a join path is exemplified by
 925                          *      SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
 926                          * If we insist on doing this as a semijoin we will first have
 927                          * to form the cartesian product of A*B.  But if we unique-ify
 928                          * C then the semijoin becomes a plain innerjoin and we can join
 929                          * in any order, eg C to A and then to B.  When C is much smaller
 930                          * than A and B this can be a huge win.  So we allow C to be
 931                          * joined to just A or just B here, and then make_join_rel has
 932                          * to handle the case properly.
 933                          *
 934                          * Note that actually we'll allow unique-ified C to be joined to
 935                          * some other relation D here, too.  That is legal, if usually not
 936                          * very sane, and this routine is only concerned with legality not
 937                          * with whether the join is good strategy.
 938                          *----------
 939                          */
 940                         if (match_sjinfo)
 941                                 return false;   /* invalid join path */
 942                         match_sjinfo = sjinfo;
 943                         reversed = false;
 944                         unique_ified = true;
 945                 }
 946                 else if (sjinfo->jointype == JOIN_SEMI &&
 947                                  bms_equal(sjinfo->syn_righthand, rel1->relids) &&
 948                                  create_unique_path(root, rel1, rel1->cheapest_total_path,
 949                                                                         sjinfo) != NULL)
 950                 {
 951                         /* Reversed semijoin case */
 952                         if (match_sjinfo)
 953                                 return false;   /* invalid join path */
 954                         match_sjinfo = sjinfo;
 955                         reversed = true;
 956                         unique_ified = true;
 957                 }
 958                 else
 959                 {
 960                         /*----------
 961                          * Otherwise, the proposed join overlaps the RHS but isn't
 962                          * a valid implementation of this SJ.  It might still be
 963                          * a legal join, however.  If both inputs overlap the RHS,
 964                          * assume that it's OK.  Since the inputs presumably got past
 965                          * this function's checks previously, they can't overlap the
 966                          * LHS and their violations of the RHS boundary must represent
 967                          * SJs that have been determined to commute with this one.
 968                          * We have to allow this to work correctly in cases like
 969                          *              (a LEFT JOIN (b JOIN (c LEFT JOIN d)))
 970                          * when the c/d join has been determined to commute with the join
 971                          * to a, and hence d is not part of min_righthand for the upper
 972                          * join.  It should be legal to join b to c/d but this will appear
 973                          * as a violation of the upper join's RHS.
 974                          * Furthermore, if one input overlaps the RHS and the other does
 975                          * not, we should still allow the join if it is a valid
 976                          * implementation of some other SJ.  We have to allow this to
 977                          * support the associative identity
 978                          *              (a LJ b on Pab) LJ c ON Pbc = a LJ (b LJ c ON Pbc) on Pab
 979                          * since joining B directly to C violates the lower SJ's RHS.
 980                          * We assume that make_outerjoininfo() set things up correctly
 981                          * so that we'll only match to some SJ if the join is valid.
 982                          * Set flag here to check at bottom of loop.
 983                          *----------
 984                          */
 985                         if (sjinfo->jointype != JOIN_SEMI &&
 986                                 bms_overlap(rel1->relids, sjinfo->min_righthand) &&
 987                                 bms_overlap(rel2->relids, sjinfo->min_righthand))
 988                         {
 989                                 /* seems OK */
 990                                 Assert(!bms_overlap(joinrelids, sjinfo->min_lefthand));
 991                         }
 992                         else
 993                                 is_valid_inner = false;
 994                 }
 995         }
 996
 997         /*
 998          * Fail if violated some SJ's RHS and didn't match to another SJ. However,
 999          * "matching" to a semijoin we are implementing by unique-ification
1000          * doesn't count (think: it's really an inner join).
1001          */
1002         if (!is_valid_inner &&
1003                 (match_sjinfo == NULL || unique_ified))
1004                 return false;                   /* invalid join path */
1005
1006         /* Otherwise, it's a valid join */
1007         *sjinfo_p = match_sjinfo;
1008         *reversed_p = reversed;
1009         return true;
1010 }
1011
1012 /*
1013  * has_join_restriction
1014  *              Detect whether the specified relation has join-order restrictions
1015  *              due to being inside an outer join or an IN (sub-SELECT).
1016  *
1017  * Essentially, this tests whether have_join_order_restriction() could
1018  * succeed with this rel and some other one.  It's OK if we sometimes
1019  * say "true" incorrectly.      (Therefore, we don't bother with the relatively
1020  * expensive has_legal_joinclause test.)
1021  */
1022 static bool
1023 has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
1024 {
1025         ListCell   *l;
1026
1027         foreach(l, root->join_info_list)
1028         {
1029                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1030
1031                 /* ignore full joins --- other mechanisms preserve their ordering */
1032                 if (sjinfo->jointype == JOIN_FULL)
1033                         continue;
1034
1035                 /* ignore if SJ is already contained in rel */
1036                 if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
1037                         bms_is_subset(sjinfo->min_righthand, rel->relids))
1038                         continue;
1039
1040                 /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
1041                 if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
1042                         bms_overlap(sjinfo->min_righthand, rel->relids))
1043                         return true;
1044         }
1045
1046         return false;
1047 }
1048
1049 /*
1050  * is_dummy_rel --- has relation been proven empty?
1051  *
1052  * If so, it will have a single path that is dummy.
1053  */
1054 static bool
1055 is_dummy_rel(RelOptInfo *rel)
1056 {
1057         return (rel->cheapest_total_path != NULL &&
1058                         IS_DUMMY_PATH(rel->cheapest_total_path));
1059 }
1060
1061 /*
1062  * Mark a relation as proven empty.
1063  *
1064  * During GEQO planning, this can get invoked more than once on the same
1065  * baserel struct, so it's worth checking to see if the rel is already marked
1066  * dummy.
1067  *
1068  * Also, when called during GEQO join planning, we are in a short-lived
1069  * memory context.      We must make sure that the dummy path attached to a
1070  * baserel survives the GEQO cycle, else the baserel is trashed for future
1071  * GEQO cycles.  On the other hand, when we are marking a joinrel during GEQO,
1072  * we don't want the dummy path to clutter the main planning context.  Upshot
1073  * is that the best solution is to explicitly make the dummy path in the same
1074  * context the given RelOptInfo is in.
1075  */
1076 static void
1077 mark_dummy_rel(RelOptInfo *rel)
1078 {
1079         MemoryContext oldcontext;
1080
1081         /* Already marked? */
1082         if (is_dummy_rel(rel))
1083                 return;
1084
1085         /* No, so choose correct context to make the dummy path in */
1086         oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1087
1088         /* Set dummy size estimate */
1089         rel->rows = 0;
1090
1091         /* Evict any previously chosen paths */
1092         rel->pathlist = NIL;
1093
1094         /* Set up the dummy path */
1095         add_path(rel, (Path *) create_append_path(rel, NIL));
1096
1097         /* Set or update cheapest_total_path */
1098         set_cheapest(rel);
1099
1100         MemoryContextSwitchTo(oldcontext);
1101 }
1102
1103 /*
1104  * restriction_is_constant_false --- is a restrictlist just FALSE?
1105  *
1106  * In cases where a qual is provably constant FALSE, eval_const_expressions
1107  * will generally have thrown away anything that's ANDed with it.  In outer
1108  * join situations this will leave us computing cartesian products only to
1109  * decide there's no match for an outer row, which is pretty stupid.  So,
1110  * we need to detect the case.
1111  *
1112  * If only_pushed_down is TRUE, then consider only pushed-down quals.
1113  */
1114 static bool
1115 restriction_is_constant_false(List *restrictlist, bool only_pushed_down)
1116 {
1117         ListCell   *lc;
1118
1119         /*
1120          * Despite the above comment, the restriction list we see here might
1121          * possibly have other members besides the FALSE constant, since other
1122          * quals could get "pushed down" to the outer join level.  So we check
1123          * each member of the list.
1124          */
1125         foreach(lc, restrictlist)
1126         {
1127                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1128
1129                 Assert(IsA(rinfo, RestrictInfo));
1130                 if (only_pushed_down && !rinfo->is_pushed_down)
1131                         continue;
1132
1133                 if (rinfo->clause && IsA(rinfo->clause, Const))
1134                 {
1135                         Const      *con = (Const *) rinfo->clause;
1136
1137                         /* constant NULL is as good as constant FALSE for our purposes */
1138                         if (con->constisnull)
1139                                 return true;
1140                         if (!DatumGetBool(con->constvalue))
1141                                 return true;
1142                 }
1143         }
1144         return false;
1145 }