core.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * core.c
   4  *        Routines copied from PostgreSQL core distribution.
   5  *
   6  * The main purpose of this files is having access to static functions in core.
   7  * Another purpose is tweaking functions behavior by replacing part of them by
   8  * macro definitions. See at the end of pg_hint_plan.c for details. Anyway,
   9  * this file *must* contain required functions without making any change.
  10  *
  11  * This file contains the following functions from corresponding files.
  12  *
  13  * src/backend/optimizer/path/allpaths.c
  14  *
  15  *  public functions:
  16  *     standard_join_search(): This funcion is not static. The reason for
  17  *        including this function is make_rels_by_clause_joins. In order to
  18  *        avoid generating apparently unwanted join combination, we decided to
  19  *        change the behavior of make_join_rel, which is called under this
  20  *        function.
  21  *
  22  *      static functions:
  23  *         set_rel_pathlist()
  24  *         set_plain_rel_pathlist()
  25  *         set_tablesample_rel_pathlist
  26  *         set_foreign_pathlist()
  27  *         set_append_rel_pathlist()
  28  *         set_function_pathlist()
  29  *         set_values_pathlist()
  30  *         set_tablefunc_pathlist()
  31  *         create_plain_partial_paths()
  32  *
  33  * src/backend/optimizer/path/joinrels.c
  34  *
  35  *      public functions:
  36  *     join_search_one_level(): We have to modify this to call my definition of
  37  *                  make_rels_by_clause_joins.
  38  *
  39  *      static functions:
  40  *     make_rels_by_clause_joins()
  41  *     make_rels_by_clauseless_joins()
  42  *     join_is_legal()
  43  *     has_join_restriction()
  44  *     restriction_is_constant_false()
  45  *     build_child_join_sjinfo()
  46  *     get_matching_part_pairs()
  47  *     compute_partition_bounds()
  48  *     try_partitionwise_join()
  49  *
  50  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
  51  * Portions Copyright (c) 1994, Regents of the University of California
  52  *
  53  *-------------------------------------------------------------------------
  54  */
  55
  56 #include "access/tsmapi.h"
  57 #include "catalog/pg_operator.h"
  58 #include "foreign/fdwapi.h"
  59
  60 /*
  61  * set_plain_rel_pathlist
  62  *        Build access paths for a plain relation (no subquery, no inheritance)
  63  */
  64 static void
  65 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
  66 {
  67         Relids          required_outer;
  68
  69         /*
  70          * We don't support pushing join clauses into the quals of a seqscan, but
  71          * it could still have required parameterization due to LATERAL refs in
  72          * its tlist.
  73          */
  74         required_outer = rel->lateral_relids;
  75
  76         /* Consider sequential scan */
  77         add_path(rel, create_seqscan_path(root, rel, required_outer, 0));
  78
  79         /* If appropriate, consider parallel sequential scan */
  80         if (rel->consider_parallel && required_outer == NULL)
  81                 create_plain_partial_paths(root, rel);
  82
  83         /* Consider index scans */
  84         create_index_paths(root, rel);
  85
  86         /* Consider TID scans */
  87         create_tidscan_paths(root, rel);
  88 }
  89
  90
  91 /*
  92  * set_tablesample_rel_pathlist
  93  *        Build access paths for a sampled relation
  94  */
  95 static void
  96 set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
  97 {
  98         Relids          required_outer;
  99         Path       *path;
 100
 101         /*
 102          * We don't support pushing join clauses into the quals of a samplescan,
 103          * but it could still have required parameterization due to LATERAL refs
 104          * in its tlist or TABLESAMPLE arguments.
 105          */
 106         required_outer = rel->lateral_relids;
 107
 108         /* Consider sampled scan */
 109         path = create_samplescan_path(root, rel, required_outer);
 110
 111         /*
 112          * If the sampling method does not support repeatable scans, we must avoid
 113          * plans that would scan the rel multiple times.  Ideally, we'd simply
 114          * avoid putting the rel on the inside of a nestloop join; but adding such
 115          * a consideration to the planner seems like a great deal of complication
 116          * to support an uncommon usage of second-rate sampling methods.  Instead,
 117          * if there is a risk that the query might perform an unsafe join, just
 118          * wrap the SampleScan in a Materialize node.  We can check for joins by
 119          * counting the membership of all_baserels (note that this correctly
 120          * counts inheritance trees as single rels).  If we're inside a subquery,
 121          * we can't easily check whether a join might occur in the outer query, so
 122          * just assume one is possible.
 123          *
 124          * GetTsmRoutine is relatively expensive compared to the other tests here,
 125          * so check repeatable_across_scans last, even though that's a bit odd.
 126          */
 127         if ((root->query_level > 1 ||
 128                  bms_membership(root->all_baserels) != BMS_SINGLETON) &&
 129                 !(GetTsmRoutine(rte->tablesample->tsmhandler)->repeatable_across_scans))
 130         {
 131                 path = (Path *) create_material_path(rel, path);
 132         }
 133
 134         add_path(rel, path);
 135
 136         /* For the moment, at least, there are no other paths to consider */
 137 }
 138
 139
 140 /*
 141  * set_foreign_pathlist
 142  *              Build access paths for a foreign table RTE
 143  */
 144 static void
 145 set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 146 {
 147         /* Call the FDW's GetForeignPaths function to generate path(s) */
 148         rel->fdwroutine->GetForeignPaths(root, rel, rte->relid);
 149 }
 150
 151
 152 /*
 153  * set_function_pathlist
 154  *              Build the (single) access path for a function RTE
 155  */
 156 static void
 157 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 158 {
 159         Relids          required_outer;
 160         List       *pathkeys = NIL;
 161
 162         /*
 163          * We don't support pushing join clauses into the quals of a function
 164          * scan, but it could still have required parameterization due to LATERAL
 165          * refs in the function expression.
 166          */
 167         required_outer = rel->lateral_relids;
 168
 169         /*
 170          * The result is considered unordered unless ORDINALITY was used, in which
 171          * case it is ordered by the ordinal column (the last one).  See if we
 172          * care, by checking for uses of that Var in equivalence classes.
 173          */
 174         if (rte->funcordinality)
 175         {
 176                 AttrNumber      ordattno = rel->max_attr;
 177                 Var                *var = NULL;
 178                 ListCell   *lc;
 179
 180                 /*
 181                  * Is there a Var for it in rel's targetlist?  If not, the query did
 182                  * not reference the ordinality column, or at least not in any way
 183                  * that would be interesting for sorting.
 184                  */
 185                 foreach(lc, rel->reltarget->exprs)
 186                 {
 187                         Var                *node = (Var *) lfirst(lc);
 188
 189                         /* checking varno/varlevelsup is just paranoia */
 190                         if (IsA(node, Var) &&
 191                                 node->varattno == ordattno &&
 192                                 node->varno == rel->relid &&
 193                                 node->varlevelsup == 0)
 194                         {
 195                                 var = node;
 196                                 break;
 197                         }
 198                 }
 199
 200                 /*
 201                  * Try to build pathkeys for this Var with int8 sorting.  We tell
 202                  * build_expression_pathkey not to build any new equivalence class; if
 203                  * the Var isn't already mentioned in some EC, it means that nothing
 204                  * cares about the ordering.
 205                  */
 206                 if (var)
 207                         pathkeys = build_expression_pathkey(root,
 208                                                                                                 (Expr *) var,
 209                                                                                                 NULL,   /* below outer joins */
 210                                                                                                 Int8LessOperator,
 211                                                                                                 rel->relids,
 212                                                                                                 false);
 213         }
 214
 215         /* Generate appropriate path */
 216         add_path(rel, create_functionscan_path(root, rel,
 217                                                                                    pathkeys, required_outer));
 218 }
 219
 220
 221 /*
 222  * set_values_pathlist
 223  *              Build the (single) access path for a VALUES RTE
 224  */
 225 static void
 226 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 227 {
 228         Relids          required_outer;
 229
 230         /*
 231          * We don't support pushing join clauses into the quals of a values scan,
 232          * but it could still have required parameterization due to LATERAL refs
 233          * in the values expressions.
 234          */
 235         required_outer = rel->lateral_relids;
 236
 237         /* Generate appropriate path */
 238         add_path(rel, create_valuesscan_path(root, rel, required_outer));
 239 }
 240
 241 /*
 242  * set_tablefunc_pathlist
 243  *              Build the (single) access path for a table func RTE
 244  */
 245 static void
 246 set_tablefunc_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 247 {
 248         Relids          required_outer;
 249
 250         /*
 251          * We don't support pushing join clauses into the quals of a tablefunc
 252          * scan, but it could still have required parameterization due to LATERAL
 253          * refs in the function expression.
 254          */
 255         required_outer = rel->lateral_relids;
 256
 257         /* Generate appropriate path */
 258         add_path(rel, create_tablefuncscan_path(root, rel,
 259                                                                                         required_outer));
 260 }
 261
 262
 263 /*
 264  * set_rel_pathlist
 265  *        Build access paths for a base relation
 266  */
 267 static void
 268 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 269                                  Index rti, RangeTblEntry *rte)
 270 {
 271         if (IS_DUMMY_REL(rel))
 272         {
 273                 /* We already proved the relation empty, so nothing more to do */
 274         }
 275         else if (rte->inh)
 276         {
 277                 /* It's an "append relation", process accordingly */
 278                 set_append_rel_pathlist(root, rel, rti, rte);
 279         }
 280         else
 281         {
 282                 switch (rel->rtekind)
 283                 {
 284                         case RTE_RELATION:
 285                                 if (rte->relkind == RELKIND_FOREIGN_TABLE)
 286                                 {
 287                                         /* Foreign table */
 288                                         set_foreign_pathlist(root, rel, rte);
 289                                 }
 290                                 else if (rte->tablesample != NULL)
 291                                 {
 292                                         /* Sampled relation */
 293                                         set_tablesample_rel_pathlist(root, rel, rte);
 294                                 }
 295                                 else
 296                                 {
 297                                         /* Plain relation */
 298                                         set_plain_rel_pathlist(root, rel, rte);
 299                                 }
 300                                 break;
 301                         case RTE_SUBQUERY:
 302                                 /* Subquery --- fully handled during set_rel_size */
 303                                 break;
 304                         case RTE_FUNCTION:
 305                                 /* RangeFunction */
 306                                 set_function_pathlist(root, rel, rte);
 307                                 break;
 308                         case RTE_TABLEFUNC:
 309                                 /* Table Function */
 310                                 set_tablefunc_pathlist(root, rel, rte);
 311                                 break;
 312                         case RTE_VALUES:
 313                                 /* Values list */
 314                                 set_values_pathlist(root, rel, rte);
 315                                 break;
 316                         case RTE_CTE:
 317                                 /* CTE reference --- fully handled during set_rel_size */
 318                                 break;
 319                         case RTE_NAMEDTUPLESTORE:
 320                                 /* tuplestore reference --- fully handled during set_rel_size */
 321                                 break;
 322                         case RTE_RESULT:
 323                                 /* simple Result --- fully handled during set_rel_size */
 324                                 break;
 325                         default:
 326                                 elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind);
 327                                 break;
 328                 }
 329         }
 330
 331         /*
 332          * Allow a plugin to editorialize on the set of Paths for this base
 333          * relation.  It could add new paths (such as CustomPaths) by calling
 334          * add_path(), or add_partial_path() if parallel aware.  It could also
 335          * delete or modify paths added by the core code.
 336          */
 337         if (set_rel_pathlist_hook)
 338                 (*set_rel_pathlist_hook) (root, rel, rti, rte);
 339
 340         /*
 341          * If this is a baserel, we should normally consider gathering any partial
 342          * paths we may have created for it.  We have to do this after calling the
 343          * set_rel_pathlist_hook, else it cannot add partial paths to be included
 344          * here.
 345          *
 346          * However, if this is an inheritance child, skip it.  Otherwise, we could
 347          * end up with a very large number of gather nodes, each trying to grab
 348          * its own pool of workers.  Instead, we'll consider gathering partial
 349          * paths for the parent appendrel.
 350          *
 351          * Also, if this is the topmost scan/join rel (that is, the only baserel),
 352          * we postpone gathering until the final scan/join targetlist is available
 353          * (see grouping_planner).
 354          */
 355         if (rel->reloptkind == RELOPT_BASEREL &&
 356                 bms_membership(root->all_baserels) != BMS_SINGLETON)
 357                 generate_useful_gather_paths(root, rel, false);
 358
 359         /* Now find the cheapest of the paths for this rel */
 360         set_cheapest(rel);
 361
 362 #ifdef OPTIMIZER_DEBUG
 363         debug_print_rel(root, rel);
 364 #endif
 365 }
 366
 367
 368 /*
 369  * set_append_rel_pathlist
 370  *        Build access paths for an "append relation"
 371  */
 372 static void
 373 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 374                                                 Index rti, RangeTblEntry *rte)
 375 {
 376         int                     parentRTindex = rti;
 377         List       *live_childrels = NIL;
 378         ListCell   *l;
 379
 380         /*
 381          * Generate access paths for each member relation, and remember the
 382          * non-dummy children.
 383          */
 384         foreach(l, root->append_rel_list)
 385         {
 386                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
 387                 int                     childRTindex;
 388                 RangeTblEntry *childRTE;
 389                 RelOptInfo *childrel;
 390
 391                 /* append_rel_list contains all append rels; ignore others */
 392                 if (appinfo->parent_relid != parentRTindex)
 393                         continue;
 394
 395                 /* Re-locate the child RTE and RelOptInfo */
 396                 childRTindex = appinfo->child_relid;
 397                 childRTE = root->simple_rte_array[childRTindex];
 398                 childrel = root->simple_rel_array[childRTindex];
 399
 400                 /*
 401                  * If set_append_rel_size() decided the parent appendrel was
 402                  * parallel-unsafe at some point after visiting this child rel, we
 403                  * need to propagate the unsafety marking down to the child, so that
 404                  * we don't generate useless partial paths for it.
 405                  */
 406                 if (!rel->consider_parallel)
 407                         childrel->consider_parallel = false;
 408
 409                 /*
 410                  * Compute the child's access paths.
 411                  */
 412                 set_rel_pathlist(root, childrel, childRTindex, childRTE);
 413
 414                 /*
 415                  * If child is dummy, ignore it.
 416                  */
 417                 if (IS_DUMMY_REL(childrel))
 418                         continue;
 419
 420                 /*
 421                  * Child is live, so add it to the live_childrels list for use below.
 422                  */
 423                 live_childrels = lappend(live_childrels, childrel);
 424         }
 425
 426         /* Add paths to the append relation. */
 427         add_paths_to_append_rel(root, rel, live_childrels);
 428 }
 429
 430
 431 /*
 432  * standard_join_search
 433  *        Find possible joinpaths for a query by successively finding ways
 434  *        to join component relations into join relations.
 435  *
 436  * 'levels_needed' is the number of iterations needed, ie, the number of
 437  *              independent jointree items in the query.  This is > 1.
 438  *
 439  * 'initial_rels' is a list of RelOptInfo nodes for each independent
 440  *              jointree item.  These are the components to be joined together.
 441  *              Note that levels_needed == list_length(initial_rels).
 442  *
 443  * Returns the final level of join relations, i.e., the relation that is
 444  * the result of joining all the original relations together.
 445  * At least one implementation path must be provided for this relation and
 446  * all required sub-relations.
 447  *
 448  * To support loadable plugins that modify planner behavior by changing the
 449  * join searching algorithm, we provide a hook variable that lets a plugin
 450  * replace or supplement this function.  Any such hook must return the same
 451  * final join relation as the standard code would, but it might have a
 452  * different set of implementation paths attached, and only the sub-joinrels
 453  * needed for these paths need have been instantiated.
 454  *
 455  * Note to plugin authors: the functions invoked during standard_join_search()
 456  * modify root->join_rel_list and root->join_rel_hash.  If you want to do more
 457  * than one join-order search, you'll probably need to save and restore the
 458  * original states of those data structures.  See geqo_eval() for an example.
 459  */
 460 RelOptInfo *
 461 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
 462 {
 463         int                     lev;
 464         RelOptInfo *rel;
 465
 466         /*
 467          * This function cannot be invoked recursively within any one planning
 468          * problem, so join_rel_level[] can't be in use already.
 469          */
 470         Assert(root->join_rel_level == NULL);
 471
 472         /*
 473          * We employ a simple "dynamic programming" algorithm: we first find all
 474          * ways to build joins of two jointree items, then all ways to build joins
 475          * of three items (from two-item joins and single items), then four-item
 476          * joins, and so on until we have considered all ways to join all the
 477          * items into one rel.
 478          *
 479          * root->join_rel_level[j] is a list of all the j-item rels.  Initially we
 480          * set root->join_rel_level[1] to represent all the single-jointree-item
 481          * relations.
 482          */
 483         root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
 484
 485         root->join_rel_level[1] = initial_rels;
 486
 487         for (lev = 2; lev <= levels_needed; lev++)
 488         {
 489                 ListCell   *lc;
 490
 491                 /*
 492                  * Determine all possible pairs of relations to be joined at this
 493                  * level, and build paths for making each one from every available
 494                  * pair of lower-level relations.
 495                  */
 496                 join_search_one_level(root, lev);
 497
 498                 /*
 499                  * Run generate_partitionwise_join_paths() and
 500                  * generate_useful_gather_paths() for each just-processed joinrel.  We
 501                  * could not do this earlier because both regular and partial paths
 502                  * can get added to a particular joinrel at multiple times within
 503                  * join_search_one_level.
 504                  *
 505                  * After that, we're done creating paths for the joinrel, so run
 506                  * set_cheapest().
 507                  */
 508                 foreach(lc, root->join_rel_level[lev])
 509                 {
 510                         rel = (RelOptInfo *) lfirst(lc);
 511
 512                         /* Create paths for partitionwise joins. */
 513                         generate_partitionwise_join_paths(root, rel);
 514
 515                         /*
 516                          * Except for the topmost scan/join rel, consider gathering
 517                          * partial paths.  We'll do the same for the topmost scan/join rel
 518                          * once we know the final targetlist (see grouping_planner).
 519                          */
 520                         if (lev < levels_needed)
 521                                 generate_useful_gather_paths(root, rel, false);
 522
 523                         /* Find and save the cheapest paths for this rel */
 524                         set_cheapest(rel);
 525
 526 #ifdef OPTIMIZER_DEBUG
 527                         debug_print_rel(root, rel);
 528 #endif
 529                 }
 530         }
 531
 532         /*
 533          * We should have a single rel at the final level.
 534          */
 535         if (root->join_rel_level[levels_needed] == NIL)
 536                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
 537         Assert(list_length(root->join_rel_level[levels_needed]) == 1);
 538
 539         rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
 540
 541         root->join_rel_level = NULL;
 542
 543         return rel;
 544 }
 545
 546
 547 /*
 548  * create_plain_partial_paths
 549  *        Build partial access paths for parallel scan of a plain relation
 550  */
 551 static void
 552 create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel)
 553 {
 554         int                     parallel_workers;
 555
 556         parallel_workers = compute_parallel_worker(rel, rel->pages, -1,
 557                                                                                            max_parallel_workers_per_gather);
 558
 559         /* If any limit was set to zero, the user doesn't want a parallel scan. */
 560         if (parallel_workers <= 0)
 561                 return;
 562
 563         /* Add an unordered partial path based on a parallel sequential scan. */
 564         add_partial_path(rel, create_seqscan_path(root, rel, NULL, parallel_workers));
 565 }
 566
 567
 568 /*
 569  * join_search_one_level
 570  *        Consider ways to produce join relations containing exactly 'level'
 571  *        jointree items.  (This is one step of the dynamic-programming method
 572  *        embodied in standard_join_search.)  Join rel nodes for each feasible
 573  *        combination of lower-level rels are created and returned in a list.
 574  *        Implementation paths are created for each such joinrel, too.
 575  *
 576  * level: level of rels we want to make this time
 577  * root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
 578  *
 579  * The result is returned in root->join_rel_level[level].
 580  */
 581 void
 582 join_search_one_level(PlannerInfo *root, int level)
 583 {
 584         List      **joinrels = root->join_rel_level;
 585         ListCell   *r;
 586         int                     k;
 587
 588         Assert(joinrels[level] == NIL);
 589
 590         /* Set join_cur_level so that new joinrels are added to proper list */
 591         root->join_cur_level = level;
 592
 593         /*
 594          * First, consider left-sided and right-sided plans, in which rels of
 595          * exactly level-1 member relations are joined against initial relations.
 596          * We prefer to join using join clauses, but if we find a rel of level-1
 597          * members that has no join clauses, we will generate Cartesian-product
 598          * joins against all initial rels not already contained in it.
 599          */
 600         foreach(r, joinrels[level - 1])
 601         {
 602                 RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 603
 604                 if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
 605                         has_join_restriction(root, old_rel))
 606                 {
 607                         /*
 608                          * There are join clauses or join order restrictions relevant to
 609                          * this rel, so consider joins between this rel and (only) those
 610                          * initial rels it is linked to by a clause or restriction.
 611                          *
 612                          * At level 2 this condition is symmetric, so there is no need to
 613                          * look at initial rels before this one in the list; we already
 614                          * considered such joins when we were at the earlier rel.  (The
 615                          * mirror-image joins are handled automatically by make_join_rel.)
 616                          * In later passes (level > 2), we join rels of the previous level
 617                          * to each initial rel they don't already include but have a join
 618                          * clause or restriction with.
 619                          */
 620                         List       *other_rels_list;
 621                         ListCell   *other_rels;
 622
 623                         if (level == 2)         /* consider remaining initial rels */
 624                         {
 625                                 other_rels_list = joinrels[level - 1];
 626                                 other_rels = lnext(other_rels_list, r);
 627                         }
 628                         else                            /* consider all initial rels */
 629                         {
 630                                 other_rels_list = joinrels[1];
 631                                 other_rels = list_head(other_rels_list);
 632                         }
 633
 634                         make_rels_by_clause_joins(root,
 635                                                                           old_rel,
 636                                                                           other_rels_list,
 637                                                                           other_rels);
 638                 }
 639                 else
 640                 {
 641                         /*
 642                          * Oops, we have a relation that is not joined to any other
 643                          * relation, either directly or by join-order restrictions.
 644                          * Cartesian product time.
 645                          *
 646                          * We consider a cartesian product with each not-already-included
 647                          * initial rel, whether it has other join clauses or not.  At
 648                          * level 2, if there are two or more clauseless initial rels, we
 649                          * will redundantly consider joining them in both directions; but
 650                          * such cases aren't common enough to justify adding complexity to
 651                          * avoid the duplicated effort.
 652                          */
 653                         make_rels_by_clauseless_joins(root,
 654                                                                                   old_rel,
 655                                                                                   joinrels[1]);
 656                 }
 657         }
 658
 659         /*
 660          * Now, consider "bushy plans" in which relations of k initial rels are
 661          * joined to relations of level-k initial rels, for 2 <= k <= level-2.
 662          *
 663          * We only consider bushy-plan joins for pairs of rels where there is a
 664          * suitable join clause (or join order restriction), in order to avoid
 665          * unreasonable growth of planning time.
 666          */
 667         for (k = 2;; k++)
 668         {
 669                 int                     other_level = level - k;
 670
 671                 /*
 672                  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
 673                  * need to go as far as the halfway point.
 674                  */
 675                 if (k > other_level)
 676                         break;
 677
 678                 foreach(r, joinrels[k])
 679                 {
 680                         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 681                         List       *other_rels_list;
 682                         ListCell   *other_rels;
 683                         ListCell   *r2;
 684
 685                         /*
 686                          * We can ignore relations without join clauses here, unless they
 687                          * participate in join-order restrictions --- then we might have
 688                          * to force a bushy join plan.
 689                          */
 690                         if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
 691                                 !has_join_restriction(root, old_rel))
 692                                 continue;
 693
 694                         if (k == other_level)
 695                         {
 696                                 /* only consider remaining rels */
 697                                 other_rels_list = joinrels[k];
 698                                 other_rels = lnext(other_rels_list, r);
 699                         }
 700                         else
 701                         {
 702                                 other_rels_list = joinrels[other_level];
 703                                 other_rels = list_head(other_rels_list);
 704                         }
 705
 706                         for_each_cell(r2, other_rels_list, other_rels)
 707                         {
 708                                 RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
 709
 710                                 if (!bms_overlap(old_rel->relids, new_rel->relids))
 711                                 {
 712                                         /*
 713                                          * OK, we can build a rel of the right level from this
 714                                          * pair of rels.  Do so if there is at least one relevant
 715                                          * join clause or join order restriction.
 716                                          */
 717                                         if (have_relevant_joinclause(root, old_rel, new_rel) ||
 718                                                 have_join_order_restriction(root, old_rel, new_rel))
 719                                         {
 720                                                 (void) make_join_rel(root, old_rel, new_rel);
 721                                         }
 722                                 }
 723                         }
 724                 }
 725         }
 726
 727         /*----------
 728          * Last-ditch effort: if we failed to find any usable joins so far, force
 729          * a set of cartesian-product joins to be generated.  This handles the
 730          * special case where all the available rels have join clauses but we
 731          * cannot use any of those clauses yet.  This can only happen when we are
 732          * considering a join sub-problem (a sub-joinlist) and all the rels in the
 733          * sub-problem have only join clauses with rels outside the sub-problem.
 734          * An example is
 735          *
 736          *              SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
 737          *              WHERE a.w = c.x and b.y = d.z;
 738          *
 739          * If the "a INNER JOIN b" sub-problem does not get flattened into the
 740          * upper level, we must be willing to make a cartesian join of a and b;
 741          * but the code above will not have done so, because it thought that both
 742          * a and b have joinclauses.  We consider only left-sided and right-sided
 743          * cartesian joins in this case (no bushy).
 744          *----------
 745          */
 746         if (joinrels[level] == NIL)
 747         {
 748                 /*
 749                  * This loop is just like the first one, except we always call
 750                  * make_rels_by_clauseless_joins().
 751                  */
 752                 foreach(r, joinrels[level - 1])
 753                 {
 754                         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 755
 756                         make_rels_by_clauseless_joins(root,
 757                                                                                   old_rel,
 758                                                                                   joinrels[1]);
 759                 }
 760
 761                 /*----------
 762                  * When special joins are involved, there may be no legal way
 763                  * to make an N-way join for some values of N.  For example consider
 764                  *
 765                  * SELECT ... FROM t1 WHERE
 766                  *       x IN (SELECT ... FROM t2,t3 WHERE ...) AND
 767                  *       y IN (SELECT ... FROM t4,t5 WHERE ...)
 768                  *
 769                  * We will flatten this query to a 5-way join problem, but there are
 770                  * no 4-way joins that join_is_legal() will consider legal.  We have
 771                  * to accept failure at level 4 and go on to discover a workable
 772                  * bushy plan at level 5.
 773                  *
 774                  * However, if there are no special joins and no lateral references
 775                  * then join_is_legal() should never fail, and so the following sanity
 776                  * check is useful.
 777                  *----------
 778                  */
 779                 if (joinrels[level] == NIL &&
 780                         root->join_info_list == NIL &&
 781                         !root->hasLateralRTEs)
 782                         elog(ERROR, "failed to build any %d-way joins", level);
 783         }
 784 }
 785
 786
 787 /*
 788  * make_rels_by_clause_joins
 789  *        Build joins between the given relation 'old_rel' and other relations
 790  *        that participate in join clauses that 'old_rel' also participates in
 791  *        (or participate in join-order restrictions with it).
 792  *        The join rels are returned in root->join_rel_level[join_cur_level].
 793  *
 794  * Note: at levels above 2 we will generate the same joined relation in
 795  * multiple ways --- for example (a join b) join c is the same RelOptInfo as
 796  * (b join c) join a, though the second case will add a different set of Paths
 797  * to it.  This is the reason for using the join_rel_level mechanism, which
 798  * automatically ensures that each new joinrel is only added to the list once.
 799  *
 800  * 'old_rel' is the relation entry for the relation to be joined
 801  * 'other_rels_list': a list containing the other
 802  * rels to be considered for joining
 803  * 'other_rels': the first cell to be considered
 804  *
 805  * Currently, this is only used with initial rels in other_rels, but it
 806  * will work for joining to joinrels too.
 807  */
 808 static void
 809 make_rels_by_clause_joins(PlannerInfo *root,
 810                                                   RelOptInfo *old_rel,
 811                                                   List *other_rels_list,
 812                                                   ListCell *other_rels)
 813 {
 814         ListCell   *l;
 815
 816         for_each_cell(l, other_rels_list, other_rels)
 817         {
 818                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 819
 820                 if (!bms_overlap(old_rel->relids, other_rel->relids) &&
 821                         (have_relevant_joinclause(root, old_rel, other_rel) ||
 822                          have_join_order_restriction(root, old_rel, other_rel)))
 823                 {
 824                         (void) make_join_rel(root, old_rel, other_rel);
 825                 }
 826         }
 827 }
 828
 829
 830 /*
 831  * make_rels_by_clauseless_joins
 832  *        Given a relation 'old_rel' and a list of other relations
 833  *        'other_rels', create a join relation between 'old_rel' and each
 834  *        member of 'other_rels' that isn't already included in 'old_rel'.
 835  *        The join rels are returned in root->join_rel_level[join_cur_level].
 836  *
 837  * 'old_rel' is the relation entry for the relation to be joined
 838  * 'other_rels': a list containing the other rels to be considered for joining
 839  *
 840  * Currently, this is only used with initial rels in other_rels, but it would
 841  * work for joining to joinrels too.
 842  */
 843 static void
 844 make_rels_by_clauseless_joins(PlannerInfo *root,
 845                                                           RelOptInfo *old_rel,
 846                                                           List *other_rels)
 847 {
 848         ListCell   *l;
 849
 850         foreach(l, other_rels)
 851         {
 852                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 853
 854                 if (!bms_overlap(other_rel->relids, old_rel->relids))
 855                 {
 856                         (void) make_join_rel(root, old_rel, other_rel);
 857                 }
 858         }
 859 }
 860
 861
 862 /*
 863  * join_is_legal
 864  *         Determine whether a proposed join is legal given the query's
 865  *         join order constraints; and if it is, determine the join type.
 866  *
 867  * Caller must supply not only the two rels, but the union of their relids.
 868  * (We could simplify the API by computing joinrelids locally, but this
 869  * would be redundant work in the normal path through make_join_rel.)
 870  *
 871  * On success, *sjinfo_p is set to NULL if this is to be a plain inner join,
 872  * else it's set to point to the associated SpecialJoinInfo node.  Also,
 873  * *reversed_p is set true if the given relations need to be swapped to
 874  * match the SpecialJoinInfo node.
 875  */
 876 static bool
 877 join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 878                           Relids joinrelids,
 879                           SpecialJoinInfo **sjinfo_p, bool *reversed_p)
 880 {
 881         SpecialJoinInfo *match_sjinfo;
 882         bool            reversed;
 883         bool            unique_ified;
 884         bool            must_be_leftjoin;
 885         ListCell   *l;
 886
 887         /*
 888          * Ensure output params are set on failure return.  This is just to
 889          * suppress uninitialized-variable warnings from overly anal compilers.
 890          */
 891         *sjinfo_p = NULL;
 892         *reversed_p = false;
 893
 894         /*
 895          * If we have any special joins, the proposed join might be illegal; and
 896          * in any case we have to determine its join type.  Scan the join info
 897          * list for matches and conflicts.
 898          */
 899         match_sjinfo = NULL;
 900         reversed = false;
 901         unique_ified = false;
 902         must_be_leftjoin = false;
 903
 904         foreach(l, root->join_info_list)
 905         {
 906                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
 907
 908                 /*
 909                  * This special join is not relevant unless its RHS overlaps the
 910                  * proposed join.  (Check this first as a fast path for dismissing
 911                  * most irrelevant SJs quickly.)
 912                  */
 913                 if (!bms_overlap(sjinfo->min_righthand, joinrelids))
 914                         continue;
 915
 916                 /*
 917                  * Also, not relevant if proposed join is fully contained within RHS
 918                  * (ie, we're still building up the RHS).
 919                  */
 920                 if (bms_is_subset(joinrelids, sjinfo->min_righthand))
 921                         continue;
 922
 923                 /*
 924                  * Also, not relevant if SJ is already done within either input.
 925                  */
 926                 if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 927                         bms_is_subset(sjinfo->min_righthand, rel1->relids))
 928                         continue;
 929                 if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
 930                         bms_is_subset(sjinfo->min_righthand, rel2->relids))
 931                         continue;
 932
 933                 /*
 934                  * If it's a semijoin and we already joined the RHS to any other rels
 935                  * within either input, then we must have unique-ified the RHS at that
 936                  * point (see below).  Therefore the semijoin is no longer relevant in
 937                  * this join path.
 938                  */
 939                 if (sjinfo->jointype == JOIN_SEMI)
 940                 {
 941                         if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
 942                                 !bms_equal(sjinfo->syn_righthand, rel1->relids))
 943                                 continue;
 944                         if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
 945                                 !bms_equal(sjinfo->syn_righthand, rel2->relids))
 946                                 continue;
 947                 }
 948
 949                 /*
 950                  * If one input contains min_lefthand and the other contains
 951                  * min_righthand, then we can perform the SJ at this join.
 952                  *
 953                  * Reject if we get matches to more than one SJ; that implies we're
 954                  * considering something that's not really valid.
 955                  */
 956                 if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
 957                         bms_is_subset(sjinfo->min_righthand, rel2->relids))
 958                 {
 959                         if (match_sjinfo)
 960                                 return false;   /* invalid join path */
 961                         match_sjinfo = sjinfo;
 962                         reversed = false;
 963                 }
 964                 else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
 965                                  bms_is_subset(sjinfo->min_righthand, rel1->relids))
 966                 {
 967                         if (match_sjinfo)
 968                                 return false;   /* invalid join path */
 969                         match_sjinfo = sjinfo;
 970                         reversed = true;
 971                 }
 972                 else if (sjinfo->jointype == JOIN_SEMI &&
 973                                  bms_equal(sjinfo->syn_righthand, rel2->relids) &&
 974                                  create_unique_path(root, rel2, rel2->cheapest_total_path,
 975                                                                         sjinfo) != NULL)
 976                 {
 977                         /*----------
 978                          * For a semijoin, we can join the RHS to anything else by
 979                          * unique-ifying the RHS (if the RHS can be unique-ified).
 980                          * We will only get here if we have the full RHS but less
 981                          * than min_lefthand on the LHS.
 982                          *
 983                          * The reason to consider such a join path is exemplified by
 984                          *      SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
 985                          * If we insist on doing this as a semijoin we will first have
 986                          * to form the cartesian product of A*B.  But if we unique-ify
 987                          * C then the semijoin becomes a plain innerjoin and we can join
 988                          * in any order, eg C to A and then to B.  When C is much smaller
 989                          * than A and B this can be a huge win.  So we allow C to be
 990                          * joined to just A or just B here, and then make_join_rel has
 991                          * to handle the case properly.
 992                          *
 993                          * Note that actually we'll allow unique-ified C to be joined to
 994                          * some other relation D here, too.  That is legal, if usually not
 995                          * very sane, and this routine is only concerned with legality not
 996                          * with whether the join is good strategy.
 997                          *----------
 998                          */
 999                         if (match_sjinfo)
1000                                 return false;   /* invalid join path */
1001                         match_sjinfo = sjinfo;
1002                         reversed = false;
1003                         unique_ified = true;
1004                 }
1005                 else if (sjinfo->jointype == JOIN_SEMI &&
1006                                  bms_equal(sjinfo->syn_righthand, rel1->relids) &&
1007                                  create_unique_path(root, rel1, rel1->cheapest_total_path,
1008                                                                         sjinfo) != NULL)
1009                 {
1010                         /* Reversed semijoin case */
1011                         if (match_sjinfo)
1012                                 return false;   /* invalid join path */
1013                         match_sjinfo = sjinfo;
1014                         reversed = true;
1015                         unique_ified = true;
1016                 }
1017                 else
1018                 {
1019                         /*
1020                          * Otherwise, the proposed join overlaps the RHS but isn't a valid
1021                          * implementation of this SJ.  But don't panic quite yet: the RHS
1022                          * violation might have occurred previously, in one or both input
1023                          * relations, in which case we must have previously decided that
1024                          * it was OK to commute some other SJ with this one.  If we need
1025                          * to perform this join to finish building up the RHS, rejecting
1026                          * it could lead to not finding any plan at all.  (This can occur
1027                          * because of the heuristics elsewhere in this file that postpone
1028                          * clauseless joins: we might not consider doing a clauseless join
1029                          * within the RHS until after we've performed other, validly
1030                          * commutable SJs with one or both sides of the clauseless join.)
1031                          * This consideration boils down to the rule that if both inputs
1032                          * overlap the RHS, we can allow the join --- they are either
1033                          * fully within the RHS, or represent previously-allowed joins to
1034                          * rels outside it.
1035                          */
1036                         if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
1037                                 bms_overlap(rel2->relids, sjinfo->min_righthand))
1038                                 continue;               /* assume valid previous violation of RHS */
1039
1040                         /*
1041                          * The proposed join could still be legal, but only if we're
1042                          * allowed to associate it into the RHS of this SJ.  That means
1043                          * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
1044                          * not FULL) and the proposed join must not overlap the LHS.
1045                          */
1046                         if (sjinfo->jointype != JOIN_LEFT ||
1047                                 bms_overlap(joinrelids, sjinfo->min_lefthand))
1048                                 return false;   /* invalid join path */
1049
1050                         /*
1051                          * To be valid, the proposed join must be a LEFT join; otherwise
1052                          * it can't associate into this SJ's RHS.  But we may not yet have
1053                          * found the SpecialJoinInfo matching the proposed join, so we
1054                          * can't test that yet.  Remember the requirement for later.
1055                          */
1056                         must_be_leftjoin = true;
1057                 }
1058         }
1059
1060         /*
1061          * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
1062          * proposed join can't associate into an SJ's RHS.
1063          *
1064          * Also, fail if the proposed join's predicate isn't strict; we're
1065          * essentially checking to see if we can apply outer-join identity 3, and
1066          * that's a requirement.  (This check may be redundant with checks in
1067          * make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
1068          */
1069         if (must_be_leftjoin &&
1070                 (match_sjinfo == NULL ||
1071                  match_sjinfo->jointype != JOIN_LEFT ||
1072                  !match_sjinfo->lhs_strict))
1073                 return false;                   /* invalid join path */
1074
1075         /*
1076          * We also have to check for constraints imposed by LATERAL references.
1077          */
1078         if (root->hasLateralRTEs)
1079         {
1080                 bool            lateral_fwd;
1081                 bool            lateral_rev;
1082                 Relids          join_lateral_rels;
1083
1084                 /*
1085                  * The proposed rels could each contain lateral references to the
1086                  * other, in which case the join is impossible.  If there are lateral
1087                  * references in just one direction, then the join has to be done with
1088                  * a nestloop with the lateral referencer on the inside.  If the join
1089                  * matches an SJ that cannot be implemented by such a nestloop, the
1090                  * join is impossible.
1091                  *
1092                  * Also, if the lateral reference is only indirect, we should reject
1093                  * the join; whatever rel(s) the reference chain goes through must be
1094                  * joined to first.
1095                  *
1096                  * Another case that might keep us from building a valid plan is the
1097                  * implementation restriction described by have_dangerous_phv().
1098                  */
1099                 lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids);
1100                 lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids);
1101                 if (lateral_fwd && lateral_rev)
1102                         return false;           /* have lateral refs in both directions */
1103                 if (lateral_fwd)
1104                 {
1105                         /* has to be implemented as nestloop with rel1 on left */
1106                         if (match_sjinfo &&
1107                                 (reversed ||
1108                                  unique_ified ||
1109                                  match_sjinfo->jointype == JOIN_FULL))
1110                                 return false;   /* not implementable as nestloop */
1111                         /* check there is a direct reference from rel2 to rel1 */
1112                         if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids))
1113                                 return false;   /* only indirect refs, so reject */
1114                         /* check we won't have a dangerous PHV */
1115                         if (have_dangerous_phv(root, rel1->relids, rel2->lateral_relids))
1116                                 return false;   /* might be unable to handle required PHV */
1117                 }
1118                 else if (lateral_rev)
1119                 {
1120                         /* has to be implemented as nestloop with rel2 on left */
1121                         if (match_sjinfo &&
1122                                 (!reversed ||
1123                                  unique_ified ||
1124                                  match_sjinfo->jointype == JOIN_FULL))
1125                                 return false;   /* not implementable as nestloop */
1126                         /* check there is a direct reference from rel1 to rel2 */
1127                         if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids))
1128                                 return false;   /* only indirect refs, so reject */
1129                         /* check we won't have a dangerous PHV */
1130                         if (have_dangerous_phv(root, rel2->relids, rel1->lateral_relids))
1131                                 return false;   /* might be unable to handle required PHV */
1132                 }
1133
1134                 /*
1135                  * LATERAL references could also cause problems later on if we accept
1136                  * this join: if the join's minimum parameterization includes any rels
1137                  * that would have to be on the inside of an outer join with this join
1138                  * rel, then it's never going to be possible to build the complete
1139                  * query using this join.  We should reject this join not only because
1140                  * it'll save work, but because if we don't, the clauseless-join
1141                  * heuristics might think that legality of this join means that some
1142                  * other join rel need not be formed, and that could lead to failure
1143                  * to find any plan at all.  We have to consider not only rels that
1144                  * are directly on the inner side of an OJ with the joinrel, but also
1145                  * ones that are indirectly so, so search to find all such rels.
1146                  */
1147                 join_lateral_rels = min_join_parameterization(root, joinrelids,
1148                                                                                                           rel1, rel2);
1149                 if (join_lateral_rels)
1150                 {
1151                         Relids          join_plus_rhs = bms_copy(joinrelids);
1152                         bool            more;
1153
1154                         do
1155                         {
1156                                 more = false;
1157                                 foreach(l, root->join_info_list)
1158                                 {
1159                                         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1160
1161                                         /* ignore full joins --- their ordering is predetermined */
1162                                         if (sjinfo->jointype == JOIN_FULL)
1163                                                 continue;
1164
1165                                         if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) &&
1166                                                 !bms_is_subset(sjinfo->min_righthand, join_plus_rhs))
1167                                         {
1168                                                 join_plus_rhs = bms_add_members(join_plus_rhs,
1169                                                                                                                 sjinfo->min_righthand);
1170                                                 more = true;
1171                                         }
1172                                 }
1173                         } while (more);
1174                         if (bms_overlap(join_plus_rhs, join_lateral_rels))
1175                                 return false;   /* will not be able to join to some RHS rel */
1176                 }
1177         }
1178
1179         /* Otherwise, it's a valid join */
1180         *sjinfo_p = match_sjinfo;
1181         *reversed_p = reversed;
1182         return true;
1183 }
1184
1185
1186 /*
1187  * has_join_restriction
1188  *              Detect whether the specified relation has join-order restrictions,
1189  *              due to being inside an outer join or an IN (sub-SELECT),
1190  *              or participating in any LATERAL references or multi-rel PHVs.
1191  *
1192  * Essentially, this tests whether have_join_order_restriction() could
1193  * succeed with this rel and some other one.  It's OK if we sometimes
1194  * say "true" incorrectly.  (Therefore, we don't bother with the relatively
1195  * expensive has_legal_joinclause test.)
1196  */
1197 static bool
1198 has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
1199 {
1200         ListCell   *l;
1201
1202         if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL)
1203                 return true;
1204
1205         foreach(l, root->placeholder_list)
1206         {
1207                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1208
1209                 if (bms_is_subset(rel->relids, phinfo->ph_eval_at) &&
1210                         !bms_equal(rel->relids, phinfo->ph_eval_at))
1211                         return true;
1212         }
1213
1214         foreach(l, root->join_info_list)
1215         {
1216                 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1217
1218                 /* ignore full joins --- other mechanisms preserve their ordering */
1219                 if (sjinfo->jointype == JOIN_FULL)
1220                         continue;
1221
1222                 /* ignore if SJ is already contained in rel */
1223                 if (bms_is_subset(sjinfo->min_lefthand, rel->relids) &&
1224                         bms_is_subset(sjinfo->min_righthand, rel->relids))
1225                         continue;
1226
1227                 /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
1228                 if (bms_overlap(sjinfo->min_lefthand, rel->relids) ||
1229                         bms_overlap(sjinfo->min_righthand, rel->relids))
1230                         return true;
1231         }
1232
1233         return false;
1234 }
1235
1236
1237 /*
1238  * restriction_is_constant_false --- is a restrictlist just FALSE?
1239  *
1240  * In cases where a qual is provably constant FALSE, eval_const_expressions
1241  * will generally have thrown away anything that's ANDed with it.  In outer
1242  * join situations this will leave us computing cartesian products only to
1243  * decide there's no match for an outer row, which is pretty stupid.  So,
1244  * we need to detect the case.
1245  *
1246  * If only_pushed_down is true, then consider only quals that are pushed-down
1247  * from the point of view of the joinrel.
1248  */
1249 static bool
1250 restriction_is_constant_false(List *restrictlist,
1251                                                           RelOptInfo *joinrel,
1252                                                           bool only_pushed_down)
1253 {
1254         ListCell   *lc;
1255
1256         /*
1257          * Despite the above comment, the restriction list we see here might
1258          * possibly have other members besides the FALSE constant, since other
1259          * quals could get "pushed down" to the outer join level.  So we check
1260          * each member of the list.
1261          */
1262         foreach(lc, restrictlist)
1263         {
1264                 RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1265
1266                 if (only_pushed_down && !RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
1267                         continue;
1268
1269                 if (rinfo->clause && IsA(rinfo->clause, Const))
1270                 {
1271                         Const      *con = (Const *) rinfo->clause;
1272
1273                         /* constant NULL is as good as constant FALSE for our purposes */
1274                         if (con->constisnull)
1275                                 return true;
1276                         if (!DatumGetBool(con->constvalue))
1277                                 return true;
1278                 }
1279         }
1280         return false;
1281 }
1282
1283
1284 /*
1285  * Construct the SpecialJoinInfo for a child-join by translating
1286  * SpecialJoinInfo for the join between parents. left_relids and right_relids
1287  * are the relids of left and right side of the join respectively.
1288  */
1289 static SpecialJoinInfo *
1290 build_child_join_sjinfo(PlannerInfo *root, SpecialJoinInfo *parent_sjinfo,
1291                                                 Relids left_relids, Relids right_relids)
1292 {
1293         SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
1294         AppendRelInfo **left_appinfos;
1295         int                     left_nappinfos;
1296         AppendRelInfo **right_appinfos;
1297         int                     right_nappinfos;
1298
1299         memcpy(sjinfo, parent_sjinfo, sizeof(SpecialJoinInfo));
1300         left_appinfos = find_appinfos_by_relids(root, left_relids,
1301                                                                                         &left_nappinfos);
1302         right_appinfos = find_appinfos_by_relids(root, right_relids,
1303                                                                                          &right_nappinfos);
1304
1305         sjinfo->min_lefthand = adjust_child_relids(sjinfo->min_lefthand,
1306                                                                                            left_nappinfos, left_appinfos);
1307         sjinfo->min_righthand = adjust_child_relids(sjinfo->min_righthand,
1308                                                                                                 right_nappinfos,
1309                                                                                                 right_appinfos);
1310         sjinfo->syn_lefthand = adjust_child_relids(sjinfo->syn_lefthand,
1311                                                                                            left_nappinfos, left_appinfos);
1312         sjinfo->syn_righthand = adjust_child_relids(sjinfo->syn_righthand,
1313                                                                                                 right_nappinfos,
1314                                                                                                 right_appinfos);
1315         sjinfo->semi_rhs_exprs = (List *) adjust_appendrel_attrs(root,
1316                                                                                                                          (Node *) sjinfo->semi_rhs_exprs,
1317                                                                                                                          right_nappinfos,
1318                                                                                                                          right_appinfos);
1319
1320         pfree(left_appinfos);
1321         pfree(right_appinfos);
1322
1323         return sjinfo;
1324 }
1325
1326
1327 /*
1328  * get_matching_part_pairs
1329  *              Generate pairs of partitions to be joined from inputs
1330  */
1331 static void
1332 get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel,
1333                                                 RelOptInfo *rel1, RelOptInfo *rel2,
1334                                                 List **parts1, List **parts2)
1335 {
1336         bool            rel1_is_simple = IS_SIMPLE_REL(rel1);
1337         bool            rel2_is_simple = IS_SIMPLE_REL(rel2);
1338         int                     cnt_parts;
1339
1340         *parts1 = NIL;
1341         *parts2 = NIL;
1342
1343         for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++)
1344         {
1345                 RelOptInfo *child_joinrel = joinrel->part_rels[cnt_parts];
1346                 RelOptInfo *child_rel1;
1347                 RelOptInfo *child_rel2;
1348                 Relids          child_relids1;
1349                 Relids          child_relids2;
1350
1351                 /*
1352                  * If this segment of the join is empty, it means that this segment
1353                  * was ignored when previously creating child-join paths for it in
1354                  * try_partitionwise_join() as it would not contribute to the join
1355                  * result, due to one or both inputs being empty; add NULL to each of
1356                  * the given lists so that this segment will be ignored again in that
1357                  * function.
1358                  */
1359                 if (!child_joinrel)
1360                 {
1361                         *parts1 = lappend(*parts1, NULL);
1362                         *parts2 = lappend(*parts2, NULL);
1363                         continue;
1364                 }
1365
1366                 /*
1367                  * Get a relids set of partition(s) involved in this join segment that
1368                  * are from the rel1 side.
1369                  */
1370                 child_relids1 = bms_intersect(child_joinrel->relids,
1371                                                                           rel1->all_partrels);
1372                 Assert(bms_num_members(child_relids1) == bms_num_members(rel1->relids));
1373
1374                 /*
1375                  * Get a child rel for rel1 with the relids.  Note that we should have
1376                  * the child rel even if rel1 is a join rel, because in that case the
1377                  * partitions specified in the relids would have matching/overlapping
1378                  * boundaries, so the specified partitions should be considered as
1379                  * ones to be joined when planning partitionwise joins of rel1,
1380                  * meaning that the child rel would have been built by the time we get
1381                  * here.
1382                  */
1383                 if (rel1_is_simple)
1384                 {
1385                         int                     varno = bms_singleton_member(child_relids1);
1386
1387                         child_rel1 = find_base_rel(root, varno);
1388                 }
1389                 else
1390                         child_rel1 = find_join_rel(root, child_relids1);
1391                 Assert(child_rel1);
1392
1393                 /*
1394                  * Get a relids set of partition(s) involved in this join segment that
1395                  * are from the rel2 side.
1396                  */
1397                 child_relids2 = bms_intersect(child_joinrel->relids,
1398                                                                           rel2->all_partrels);
1399                 Assert(bms_num_members(child_relids2) == bms_num_members(rel2->relids));
1400
1401                 /*
1402                  * Get a child rel for rel2 with the relids.  See above comments.
1403                  */
1404                 if (rel2_is_simple)
1405                 {
1406                         int                     varno = bms_singleton_member(child_relids2);
1407
1408                         child_rel2 = find_base_rel(root, varno);
1409                 }
1410                 else
1411                         child_rel2 = find_join_rel(root, child_relids2);
1412                 Assert(child_rel2);
1413
1414                 /*
1415                  * The join of rel1 and rel2 is legal, so is the join of the child
1416                  * rels obtained above; add them to the given lists as a join pair
1417                  * producing this join segment.
1418                  */
1419                 *parts1 = lappend(*parts1, child_rel1);
1420                 *parts2 = lappend(*parts2, child_rel2);
1421         }
1422 }
1423
1424
1425 /*
1426  * compute_partition_bounds
1427  *              Compute the partition bounds for a join rel from those for inputs
1428  */
1429 static void
1430 compute_partition_bounds(PlannerInfo *root, RelOptInfo *rel1,
1431                                                  RelOptInfo *rel2, RelOptInfo *joinrel,
1432                                                  SpecialJoinInfo *parent_sjinfo,
1433                                                  List **parts1, List **parts2)
1434 {
1435         /*
1436          * If we don't have the partition bounds for the join rel yet, try to
1437          * compute those along with pairs of partitions to be joined.
1438          */
1439         if (joinrel->nparts == -1)
1440         {
1441                 PartitionScheme part_scheme = joinrel->part_scheme;
1442                 PartitionBoundInfo boundinfo = NULL;
1443                 int                     nparts = 0;
1444
1445                 Assert(joinrel->boundinfo == NULL);
1446                 Assert(joinrel->part_rels == NULL);
1447
1448                 /*
1449                  * See if the partition bounds for inputs are exactly the same, in
1450                  * which case we don't need to work hard: the join rel have the same
1451                  * partition bounds as inputs, and the partitions with the same
1452                  * cardinal positions form the pairs.
1453                  *
1454                  * Note: even in cases where one or both inputs have merged bounds, it
1455                  * would be possible for both the bounds to be exactly the same, but
1456                  * it seems unlikely to be worth the cycles to check.
1457                  */
1458                 if (!rel1->partbounds_merged &&
1459                         !rel2->partbounds_merged &&
1460                         rel1->nparts == rel2->nparts &&
1461                         partition_bounds_equal(part_scheme->partnatts,
1462                                                                    part_scheme->parttyplen,
1463                                                                    part_scheme->parttypbyval,
1464                                                                    rel1->boundinfo, rel2->boundinfo))
1465                 {
1466                         boundinfo = rel1->boundinfo;
1467                         nparts = rel1->nparts;
1468                 }
1469                 else
1470                 {
1471                         /* Try merging the partition bounds for inputs. */
1472                         boundinfo = partition_bounds_merge(part_scheme->partnatts,
1473                                                                                            part_scheme->partsupfunc,
1474                                                                                            part_scheme->partcollation,
1475                                                                                            rel1, rel2,
1476                                                                                            parent_sjinfo->jointype,
1477                                                                                            parts1, parts2);
1478                         if (boundinfo == NULL)
1479                         {
1480                                 joinrel->nparts = 0;
1481                                 return;
1482                         }
1483                         nparts = list_length(*parts1);
1484                         joinrel->partbounds_merged = true;
1485                 }
1486
1487                 Assert(nparts > 0);
1488                 joinrel->boundinfo = boundinfo;
1489                 joinrel->nparts = nparts;
1490                 joinrel->part_rels =
1491                         (RelOptInfo **) palloc0(sizeof(RelOptInfo *) * nparts);
1492         }
1493         else
1494         {
1495                 Assert(joinrel->nparts > 0);
1496                 Assert(joinrel->boundinfo);
1497                 Assert(joinrel->part_rels);
1498
1499                 /*
1500                  * If the join rel's partbounds_merged flag is true, it means inputs
1501                  * are not guaranteed to have the same partition bounds, therefore we
1502                  * can't assume that the partitions at the same cardinal positions
1503                  * form the pairs; let get_matching_part_pairs() generate the pairs.
1504                  * Otherwise, nothing to do since we can assume that.
1505                  */
1506                 if (joinrel->partbounds_merged)
1507                 {
1508                         get_matching_part_pairs(root, joinrel, rel1, rel2,
1509                                                                         parts1, parts2);
1510                         Assert(list_length(*parts1) == joinrel->nparts);
1511                         Assert(list_length(*parts2) == joinrel->nparts);
1512                 }
1513         }
1514 }
1515
1516
1517 /*
1518  * Assess whether join between given two partitioned relations can be broken
1519  * down into joins between matching partitions; a technique called
1520  * "partitionwise join"
1521  *
1522  * Partitionwise join is possible when a. Joining relations have same
1523  * partitioning scheme b. There exists an equi-join between the partition keys
1524  * of the two relations.
1525  *
1526  * Partitionwise join is planned as follows (details: optimizer/README.)
1527  *
1528  * 1. Create the RelOptInfos for joins between matching partitions i.e
1529  * child-joins and add paths to them.
1530  *
1531  * 2. Construct Append or MergeAppend paths across the set of child joins.
1532  * This second phase is implemented by generate_partitionwise_join_paths().
1533  *
1534  * The RelOptInfo, SpecialJoinInfo and restrictlist for each child join are
1535  * obtained by translating the respective parent join structures.
1536  */
1537 static void
1538 try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
1539                                            RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo,
1540                                            List *parent_restrictlist)
1541 {
1542         bool            rel1_is_simple = IS_SIMPLE_REL(rel1);
1543         bool            rel2_is_simple = IS_SIMPLE_REL(rel2);
1544         List       *parts1 = NIL;
1545         List       *parts2 = NIL;
1546         ListCell   *lcr1 = NULL;
1547         ListCell   *lcr2 = NULL;
1548         int                     cnt_parts;
1549
1550         /* Guard against stack overflow due to overly deep partition hierarchy. */
1551         check_stack_depth();
1552
1553         /* Nothing to do, if the join relation is not partitioned. */
1554         if (joinrel->part_scheme == NULL || joinrel->nparts == 0)
1555                 return;
1556
1557         /* The join relation should have consider_partitionwise_join set. */
1558         Assert(joinrel->consider_partitionwise_join);
1559
1560         /*
1561          * We can not perform partitionwise join if either of the joining
1562          * relations is not partitioned.
1563          */
1564         if (!IS_PARTITIONED_REL(rel1) || !IS_PARTITIONED_REL(rel2))
1565                 return;
1566
1567         Assert(REL_HAS_ALL_PART_PROPS(rel1) && REL_HAS_ALL_PART_PROPS(rel2));
1568
1569         /* The joining relations should have consider_partitionwise_join set. */
1570         Assert(rel1->consider_partitionwise_join &&
1571                    rel2->consider_partitionwise_join);
1572
1573         /*
1574          * The partition scheme of the join relation should match that of the
1575          * joining relations.
1576          */
1577         Assert(joinrel->part_scheme == rel1->part_scheme &&
1578                    joinrel->part_scheme == rel2->part_scheme);
1579
1580         Assert(!(joinrel->partbounds_merged && (joinrel->nparts <= 0)));
1581
1582         compute_partition_bounds(root, rel1, rel2, joinrel, parent_sjinfo,
1583                                                          &parts1, &parts2);
1584
1585         if (joinrel->partbounds_merged)
1586         {
1587                 lcr1 = list_head(parts1);
1588                 lcr2 = list_head(parts2);
1589         }
1590
1591         /*
1592          * Create child-join relations for this partitioned join, if those don't
1593          * exist. Add paths to child-joins for a pair of child relations
1594          * corresponding to the given pair of parent relations.
1595          */
1596         for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++)
1597         {
1598                 RelOptInfo *child_rel1;
1599                 RelOptInfo *child_rel2;
1600                 bool            rel1_empty;
1601                 bool            rel2_empty;
1602                 SpecialJoinInfo *child_sjinfo;
1603                 List       *child_restrictlist;
1604                 RelOptInfo *child_joinrel;
1605                 Relids          child_joinrelids;
1606                 AppendRelInfo **appinfos;
1607                 int                     nappinfos;
1608
1609                 if (joinrel->partbounds_merged)
1610                 {
1611                         child_rel1 = lfirst_node(RelOptInfo, lcr1);
1612                         child_rel2 = lfirst_node(RelOptInfo, lcr2);
1613                         lcr1 = lnext(parts1, lcr1);
1614                         lcr2 = lnext(parts2, lcr2);
1615                 }
1616                 else
1617                 {
1618                         child_rel1 = rel1->part_rels[cnt_parts];
1619                         child_rel2 = rel2->part_rels[cnt_parts];
1620                 }
1621
1622                 rel1_empty = (child_rel1 == NULL || IS_DUMMY_REL(child_rel1));
1623                 rel2_empty = (child_rel2 == NULL || IS_DUMMY_REL(child_rel2));
1624
1625                 /*
1626                  * Check for cases where we can prove that this segment of the join
1627                  * returns no rows, due to one or both inputs being empty (including
1628                  * inputs that have been pruned away entirely).  If so just ignore it.
1629                  * These rules are equivalent to populate_joinrel_with_paths's rules
1630                  * for dummy input relations.
1631                  */
1632                 switch (parent_sjinfo->jointype)
1633                 {
1634                         case JOIN_INNER:
1635                         case JOIN_SEMI:
1636                                 if (rel1_empty || rel2_empty)
1637                                         continue;       /* ignore this join segment */
1638                                 break;
1639                         case JOIN_LEFT:
1640                         case JOIN_ANTI:
1641                                 if (rel1_empty)
1642                                         continue;       /* ignore this join segment */
1643                                 break;
1644                         case JOIN_FULL:
1645                                 if (rel1_empty && rel2_empty)
1646                                         continue;       /* ignore this join segment */
1647                                 break;
1648                         default:
1649                                 /* other values not expected here */
1650                                 elog(ERROR, "unrecognized join type: %d",
1651                                          (int) parent_sjinfo->jointype);
1652                                 break;
1653                 }
1654
1655                 /*
1656                  * If a child has been pruned entirely then we can't generate paths
1657                  * for it, so we have to reject partitionwise joining unless we were
1658                  * able to eliminate this partition above.
1659                  */
1660                 if (child_rel1 == NULL || child_rel2 == NULL)
1661                 {
1662                         /*
1663                          * Mark the joinrel as unpartitioned so that later functions treat
1664                          * it correctly.
1665                          */
1666                         joinrel->nparts = 0;
1667                         return;
1668                 }
1669
1670                 /*
1671                  * If a leaf relation has consider_partitionwise_join=false, it means
1672                  * that it's a dummy relation for which we skipped setting up tlist
1673                  * expressions and adding EC members in set_append_rel_size(), so
1674                  * again we have to fail here.
1675                  */
1676                 if (rel1_is_simple && !child_rel1->consider_partitionwise_join)
1677                 {
1678                         Assert(child_rel1->reloptkind == RELOPT_OTHER_MEMBER_REL);
1679                         Assert(IS_DUMMY_REL(child_rel1));
1680                         joinrel->nparts = 0;
1681                         return;
1682                 }
1683                 if (rel2_is_simple && !child_rel2->consider_partitionwise_join)
1684                 {
1685                         Assert(child_rel2->reloptkind == RELOPT_OTHER_MEMBER_REL);
1686                         Assert(IS_DUMMY_REL(child_rel2));
1687                         joinrel->nparts = 0;
1688                         return;
1689                 }
1690
1691                 /* We should never try to join two overlapping sets of rels. */
1692                 Assert(!bms_overlap(child_rel1->relids, child_rel2->relids));
1693                 child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids);
1694                 appinfos = find_appinfos_by_relids(root, child_joinrelids, &nappinfos);
1695
1696                 /*
1697                  * Construct SpecialJoinInfo from parent join relations's
1698                  * SpecialJoinInfo.
1699                  */
1700                 child_sjinfo = build_child_join_sjinfo(root, parent_sjinfo,
1701                                                                                            child_rel1->relids,
1702                                                                                            child_rel2->relids);
1703
1704                 /*
1705                  * Construct restrictions applicable to the child join from those
1706                  * applicable to the parent join.
1707                  */
1708                 child_restrictlist =
1709                         (List *) adjust_appendrel_attrs(root,
1710                                                                                         (Node *) parent_restrictlist,
1711                                                                                         nappinfos, appinfos);
1712                 pfree(appinfos);
1713
1714                 child_joinrel = joinrel->part_rels[cnt_parts];
1715                 if (!child_joinrel)
1716                 {
1717                         child_joinrel = build_child_join_rel(root, child_rel1, child_rel2,
1718                                                                                                  joinrel, child_restrictlist,
1719                                                                                                  child_sjinfo,
1720                                                                                                  child_sjinfo->jointype);
1721                         joinrel->part_rels[cnt_parts] = child_joinrel;
1722                         joinrel->all_partrels = bms_add_members(joinrel->all_partrels,
1723                                                                                                         child_joinrel->relids);
1724                 }
1725
1726                 Assert(bms_equal(child_joinrel->relids, child_joinrelids));
1727
1728                 populate_joinrel_with_paths(root, child_rel1, child_rel2,
1729                                                                         child_joinrel, child_sjinfo,
1730                                                                         child_restrictlist);
1731         }
1732 }