granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/allpaths.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * allpaths.c
   4  *        Routines to find possible search paths for processing a query
   5  *
   6  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.157 2007/01/20 20:45:38 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #ifdef OPTIMIZER_DEBUG
  19 #include "nodes/print.h"
  20 #endif
  21 #include "optimizer/clauses.h"
  22 #include "optimizer/cost.h"
  23 #include "optimizer/geqo.h"
  24 #include "optimizer/pathnode.h"
  25 #include "optimizer/paths.h"
  26 #include "optimizer/plancat.h"
  27 #include "optimizer/planner.h"
  28 #include "optimizer/prep.h"
  29 #include "optimizer/var.h"
  30 #include "parser/parse_clause.h"
  31 #include "parser/parse_expr.h"
  32 #include "parser/parsetree.h"
  33 #include "rewrite/rewriteManip.h"
  34
  35
  36 /* These parameters are set by GUC */
  37 bool            enable_geqo = false;    /* just in case GUC doesn't set it */
  38 int                     geqo_threshold;
  39
  40
  41 static void set_base_rel_pathlists(PlannerInfo *root);
  42 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti);
  43 static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  44                                            RangeTblEntry *rte);
  45 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  46                                                 Index rti, RangeTblEntry *rte);
  47 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
  48                                           Index rti, RangeTblEntry *rte);
  49 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
  50                                           RangeTblEntry *rte);
  51 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
  52                                         RangeTblEntry *rte);
  53 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
  54 static RelOptInfo *make_one_rel_by_joins(PlannerInfo *root, int levels_needed,
  55                                           List *initial_rels);
  56 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
  57                                                   bool *differentTypes);
  58 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
  59                                           bool *differentTypes);
  60 static void compare_tlist_datatypes(List *tlist, List *colTypes,
  61                                                 bool *differentTypes);
  62 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
  63                                           bool *differentTypes);
  64 static void subquery_push_qual(Query *subquery,
  65                                    RangeTblEntry *rte, Index rti, Node *qual);
  66 static void recurse_push_qual(Node *setOp, Query *topquery,
  67                                   RangeTblEntry *rte, Index rti, Node *qual);
  68
  69
  70 /*
  71  * make_one_rel
  72  *        Finds all possible access paths for executing a query, returning a
  73  *        single rel that represents the join of all base rels in the query.
  74  */
  75 RelOptInfo *
  76 make_one_rel(PlannerInfo *root, List *joinlist)
  77 {
  78         RelOptInfo *rel;
  79
  80         /*
  81          * Generate access paths for the base rels.
  82          */
  83         set_base_rel_pathlists(root);
  84
  85         /*
  86          * Generate access paths for the entire join tree.
  87          */
  88         rel = make_rel_from_joinlist(root, joinlist);
  89
  90         /*
  91          * The result should join all and only the query's base rels.
  92          */
  93 #ifdef USE_ASSERT_CHECKING
  94         {
  95                 int                     num_base_rels = 0;
  96                 Index           rti;
  97
  98                 for (rti = 1; rti < root->simple_rel_array_size; rti++)
  99                 {
 100                         RelOptInfo *brel = root->simple_rel_array[rti];
 101
 102                         if (brel == NULL)
 103                                 continue;
 104
 105                         Assert(brel->relid == rti); /* sanity check on array */
 106
 107                         /* ignore RTEs that are "other rels" */
 108                         if (brel->reloptkind != RELOPT_BASEREL)
 109                                 continue;
 110
 111                         Assert(bms_is_member(rti, rel->relids));
 112                         num_base_rels++;
 113                 }
 114
 115                 Assert(bms_num_members(rel->relids) == num_base_rels);
 116         }
 117 #endif
 118
 119         return rel;
 120 }
 121
 122 /*
 123  * set_base_rel_pathlists
 124  *        Finds all paths available for scanning each base-relation entry.
 125  *        Sequential scan and any available indices are considered.
 126  *        Each useful path is attached to its relation's 'pathlist' field.
 127  */
 128 static void
 129 set_base_rel_pathlists(PlannerInfo *root)
 130 {
 131         Index           rti;
 132
 133         for (rti = 1; rti < root->simple_rel_array_size; rti++)
 134         {
 135                 RelOptInfo *rel = root->simple_rel_array[rti];
 136
 137                 /* there may be empty slots corresponding to non-baserel RTEs */
 138                 if (rel == NULL)
 139                         continue;
 140
 141                 Assert(rel->relid == rti);              /* sanity check on array */
 142
 143                 /* ignore RTEs that are "other rels" */
 144                 if (rel->reloptkind != RELOPT_BASEREL)
 145                         continue;
 146
 147                 set_rel_pathlist(root, rel, rti);
 148         }
 149 }
 150
 151 /*
 152  * set_rel_pathlist
 153  *        Build access paths for a base relation
 154  */
 155 static void
 156 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti)
 157 {
 158         RangeTblEntry *rte = rt_fetch(rti, root->parse->rtable);
 159
 160         if (rte->inh)
 161         {
 162                 /* It's an "append relation", process accordingly */
 163                 set_append_rel_pathlist(root, rel, rti, rte);
 164         }
 165         else if (rel->rtekind == RTE_SUBQUERY)
 166         {
 167                 /* Subquery --- generate a separate plan for it */
 168                 set_subquery_pathlist(root, rel, rti, rte);
 169         }
 170         else if (rel->rtekind == RTE_FUNCTION)
 171         {
 172                 /* RangeFunction --- generate a separate plan for it */
 173                 set_function_pathlist(root, rel, rte);
 174         }
 175         else if (rel->rtekind == RTE_VALUES)
 176         {
 177                 /* Values list --- generate a separate plan for it */
 178                 set_values_pathlist(root, rel, rte);
 179         }
 180         else
 181         {
 182                 /* Plain relation */
 183                 Assert(rel->rtekind == RTE_RELATION);
 184                 set_plain_rel_pathlist(root, rel, rte);
 185         }
 186
 187 #ifdef OPTIMIZER_DEBUG
 188         debug_print_rel(root, rel);
 189 #endif
 190 }
 191
 192 /*
 193  * set_plain_rel_pathlist
 194  *        Build access paths for a plain relation (no subquery, no inheritance)
 195  */
 196 static void
 197 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 198 {
 199         /* Mark rel with estimated output rows, width, etc */
 200         set_baserel_size_estimates(root, rel);
 201
 202         /* Test any partial indexes of rel for applicability */
 203         check_partial_indexes(root, rel);
 204
 205         /*
 206          * Check to see if we can extract any restriction conditions from join
 207          * quals that are OR-of-AND structures.  If so, add them to the rel's
 208          * restriction list, and recompute the size estimates.
 209          */
 210         if (create_or_index_quals(root, rel))
 211                 set_baserel_size_estimates(root, rel);
 212
 213         /*
 214          * If we can prove we don't need to scan the rel via constraint exclusion,
 215          * set up a single dummy path for it.  (Rather than inventing a special
 216          * "dummy" path type, we represent this as an AppendPath with no members.)
 217          */
 218         if (relation_excluded_by_constraints(rel, rte))
 219         {
 220                 /* Reset output-rows estimate to 0 */
 221                 rel->rows = 0;
 222
 223                 add_path(rel, (Path *) create_append_path(rel, NIL));
 224
 225                 /* Select cheapest path (pretty easy in this case...) */
 226                 set_cheapest(rel);
 227
 228                 return;
 229         }
 230
 231         /*
 232          * Generate paths and add them to the rel's pathlist.
 233          *
 234          * Note: add_path() will discard any paths that are dominated by another
 235          * available path, keeping only those paths that are superior along at
 236          * least one dimension of cost or sortedness.
 237          */
 238
 239         /* Consider sequential scan */
 240         add_path(rel, create_seqscan_path(root, rel));
 241
 242         /* Consider index scans */
 243         create_index_paths(root, rel);
 244
 245         /* Consider TID scans */
 246         create_tidscan_paths(root, rel);
 247
 248         /* Now find the cheapest of the paths for this rel */
 249         set_cheapest(rel);
 250 }
 251
 252 /*
 253  * set_append_rel_pathlist
 254  *        Build access paths for an "append relation"
 255  *
 256  * The passed-in rel and RTE represent the entire append relation.      The
 257  * relation's contents are computed by appending together the output of
 258  * the individual member relations.  Note that in the inheritance case,
 259  * the first member relation is actually the same table as is mentioned in
 260  * the parent RTE ... but it has a different RTE and RelOptInfo.  This is
 261  * a good thing because their outputs are not the same size.
 262  */
 263 static void
 264 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 265                                                 Index rti, RangeTblEntry *rte)
 266 {
 267         int                     parentRTindex = rti;
 268         List       *subpaths = NIL;
 269         ListCell   *l;
 270
 271         /*
 272          * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE; can
 273          * we do better?  (This will take some redesign because the executor
 274          * currently supposes that every rowMark relation is involved in every row
 275          * returned by the query.)
 276          */
 277         if (get_rowmark(root->parse, parentRTindex))
 278                 ereport(ERROR,
 279                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 280                                  errmsg("SELECT FOR UPDATE/SHARE is not supported for inheritance queries")));
 281
 282         /*
 283          * Initialize to compute size estimates for whole append relation
 284          */
 285         rel->rows = 0;
 286         rel->width = 0;
 287
 288         /*
 289          * Generate access paths for each member relation, and pick the cheapest
 290          * path for each one.
 291          */
 292         foreach(l, root->append_rel_list)
 293         {
 294                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
 295                 int                     childRTindex;
 296                 RelOptInfo *childrel;
 297                 Path       *childpath;
 298                 ListCell   *parentvars;
 299                 ListCell   *childvars;
 300
 301                 /* append_rel_list contains all append rels; ignore others */
 302                 if (appinfo->parent_relid != parentRTindex)
 303                         continue;
 304
 305                 childRTindex = appinfo->child_relid;
 306
 307                 /*
 308                  * The child rel's RelOptInfo was already created during
 309                  * add_base_rels_to_query.
 310                  */
 311                 childrel = find_base_rel(root, childRTindex);
 312                 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
 313
 314                 /*
 315                  * Copy the parent's targetlist and quals to the child, with
 316                  * appropriate substitution of variables.
 317                  */
 318                 childrel->reltargetlist = (List *)
 319                         adjust_appendrel_attrs((Node *) rel->reltargetlist,
 320                                                                    appinfo);
 321                 childrel->baserestrictinfo = (List *)
 322                         adjust_appendrel_attrs((Node *) rel->baserestrictinfo,
 323                                                                    appinfo);
 324                 childrel->joininfo = (List *)
 325                         adjust_appendrel_attrs((Node *) rel->joininfo,
 326                                                                    appinfo);
 327
 328                 /*
 329                  * We have to make child entries in the EquivalenceClass data
 330                  * structures as well.
 331                  */
 332                 if (rel->has_eclass_joins)
 333                 {
 334                         add_child_rel_equivalences(root, appinfo, rel, childrel);
 335                         childrel->has_eclass_joins = true;
 336                 }
 337
 338                 /*
 339                  * Copy the parent's attr_needed data as well, with appropriate
 340                  * adjustment of relids and attribute numbers.
 341                  */
 342                 pfree(childrel->attr_needed);
 343                 childrel->attr_needed =
 344                         adjust_appendrel_attr_needed(rel, appinfo,
 345                                                                                  childrel->min_attr,
 346                                                                                  childrel->max_attr);
 347
 348                 /*
 349                  * Compute the child's access paths, and add the cheapest one to the
 350                  * Append path we are constructing for the parent.
 351                  *
 352                  * It's possible that the child is itself an appendrel, in which case
 353                  * we can "cut out the middleman" and just add its child paths to our
 354                  * own list.  (We don't try to do this earlier because we need to
 355                  * apply both levels of transformation to the quals.) This test also
 356                  * handles the case where the child rel need not be scanned because of
 357                  * constraint exclusion: it'll have an Append path with no subpaths,
 358                  * and will vanish from our list.
 359                  */
 360                 set_rel_pathlist(root, childrel, childRTindex);
 361
 362                 childpath = childrel->cheapest_total_path;
 363                 if (IsA(childpath, AppendPath))
 364                         subpaths = list_concat(subpaths,
 365                                                                    ((AppendPath *) childpath)->subpaths);
 366                 else
 367                         subpaths = lappend(subpaths, childpath);
 368
 369                 /*
 370                  * Propagate size information from the child back to the parent. For
 371                  * simplicity, we use the largest widths from any child as the parent
 372                  * estimates.
 373                  */
 374                 rel->rows += childrel->rows;
 375                 if (childrel->width > rel->width)
 376                         rel->width = childrel->width;
 377
 378                 forboth(parentvars, rel->reltargetlist,
 379                                 childvars, childrel->reltargetlist)
 380                 {
 381                         Var                *parentvar = (Var *) lfirst(parentvars);
 382                         Var                *childvar = (Var *) lfirst(childvars);
 383
 384                         if (IsA(parentvar, Var) &&
 385                                 IsA(childvar, Var))
 386                         {
 387                                 int                     pndx = parentvar->varattno - rel->min_attr;
 388                                 int                     cndx = childvar->varattno - childrel->min_attr;
 389
 390                                 if (childrel->attr_widths[cndx] > rel->attr_widths[pndx])
 391                                         rel->attr_widths[pndx] = childrel->attr_widths[cndx];
 392                         }
 393                 }
 394         }
 395
 396         /*
 397          * Finally, build Append path and install it as the only access path for
 398          * the parent rel.      (Note: this is correct even if we have zero or one
 399          * live subpath due to constraint exclusion.)
 400          */
 401         add_path(rel, (Path *) create_append_path(rel, subpaths));
 402
 403         /* Select cheapest path (pretty easy in this case...) */
 404         set_cheapest(rel);
 405 }
 406
 407 /* quick-and-dirty test to see if any joining is needed */
 408 static bool
 409 has_multiple_baserels(PlannerInfo *root)
 410 {
 411         int                     num_base_rels = 0;
 412         Index           rti;
 413
 414         for (rti = 1; rti < root->simple_rel_array_size; rti++)
 415         {
 416                 RelOptInfo *brel = root->simple_rel_array[rti];
 417
 418                 if (brel == NULL)
 419                         continue;
 420
 421                 /* ignore RTEs that are "other rels" */
 422                 if (brel->reloptkind == RELOPT_BASEREL)
 423                         if (++num_base_rels > 1)
 424                                 return true;
 425         }
 426         return false;
 427 }
 428
 429 /*
 430  * set_subquery_pathlist
 431  *              Build the (single) access path for a subquery RTE
 432  */
 433 static void
 434 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 435                                           Index rti, RangeTblEntry *rte)
 436 {
 437         Query      *parse = root->parse;
 438         Query      *subquery = rte->subquery;
 439         bool       *differentTypes;
 440         double          tuple_fraction;
 441         List       *pathkeys;
 442         List       *subquery_pathkeys;
 443
 444         /* We need a workspace for keeping track of set-op type coercions */
 445         differentTypes = (bool *)
 446                 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
 447
 448         /*
 449          * If there are any restriction clauses that have been attached to the
 450          * subquery relation, consider pushing them down to become WHERE or HAVING
 451          * quals of the subquery itself.  This transformation is useful because it
 452          * may allow us to generate a better plan for the subquery than evaluating
 453          * all the subquery output rows and then filtering them.
 454          *
 455          * There are several cases where we cannot push down clauses. Restrictions
 456          * involving the subquery are checked by subquery_is_pushdown_safe().
 457          * Restrictions on individual clauses are checked by
 458          * qual_is_pushdown_safe().  Also, we don't want to push down
 459          * pseudoconstant clauses; better to have the gating node above the
 460          * subquery.
 461          *
 462          * Non-pushed-down clauses will get evaluated as qpquals of the
 463          * SubqueryScan node.
 464          *
 465          * XXX Are there any cases where we want to make a policy decision not to
 466          * push down a pushable qual, because it'd result in a worse plan?
 467          */
 468         if (rel->baserestrictinfo != NIL &&
 469                 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
 470         {
 471                 /* OK to consider pushing down individual quals */
 472                 List       *upperrestrictlist = NIL;
 473                 ListCell   *l;
 474
 475                 foreach(l, rel->baserestrictinfo)
 476                 {
 477                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 478                         Node       *clause = (Node *) rinfo->clause;
 479
 480                         if (!rinfo->pseudoconstant &&
 481                                 qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
 482                         {
 483                                 /* Push it down */
 484                                 subquery_push_qual(subquery, rte, rti, clause);
 485                         }
 486                         else
 487                         {
 488                                 /* Keep it in the upper query */
 489                                 upperrestrictlist = lappend(upperrestrictlist, rinfo);
 490                         }
 491                 }
 492                 rel->baserestrictinfo = upperrestrictlist;
 493         }
 494
 495         pfree(differentTypes);
 496
 497         /*
 498          * We can safely pass the outer tuple_fraction down to the subquery if the
 499          * outer level has no joining, aggregation, or sorting to do. Otherwise
 500          * we'd better tell the subquery to plan for full retrieval. (XXX This
 501          * could probably be made more intelligent ...)
 502          */
 503         if (parse->hasAggs ||
 504                 parse->groupClause ||
 505                 parse->havingQual ||
 506                 parse->distinctClause ||
 507                 parse->sortClause ||
 508                 has_multiple_baserels(root))
 509                 tuple_fraction = 0.0;   /* default case */
 510         else
 511                 tuple_fraction = root->tuple_fraction;
 512
 513         /* Generate the plan for the subquery */
 514         rel->subplan = subquery_planner(subquery, tuple_fraction,
 515                                                                         &subquery_pathkeys);
 516
 517         /* Copy number of output rows from subplan */
 518         rel->tuples = rel->subplan->plan_rows;
 519
 520         /* Mark rel with estimated output rows, width, etc */
 521         set_baserel_size_estimates(root, rel);
 522
 523         /* Convert subquery pathkeys to outer representation */
 524         pathkeys = convert_subquery_pathkeys(root, rel, subquery_pathkeys);
 525
 526         /* Generate appropriate path */
 527         add_path(rel, create_subqueryscan_path(rel, pathkeys));
 528
 529         /* Select cheapest path (pretty easy in this case...) */
 530         set_cheapest(rel);
 531 }
 532
 533 /*
 534  * set_function_pathlist
 535  *              Build the (single) access path for a function RTE
 536  */
 537 static void
 538 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 539 {
 540         /* Mark rel with estimated output rows, width, etc */
 541         set_function_size_estimates(root, rel);
 542
 543         /* Generate appropriate path */
 544         add_path(rel, create_functionscan_path(root, rel));
 545
 546         /* Select cheapest path (pretty easy in this case...) */
 547         set_cheapest(rel);
 548 }
 549
 550 /*
 551  * set_values_pathlist
 552  *              Build the (single) access path for a VALUES RTE
 553  */
 554 static void
 555 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 556 {
 557         /* Mark rel with estimated output rows, width, etc */
 558         set_values_size_estimates(root, rel);
 559
 560         /* Generate appropriate path */
 561         add_path(rel, create_valuesscan_path(root, rel));
 562
 563         /* Select cheapest path (pretty easy in this case...) */
 564         set_cheapest(rel);
 565 }
 566
 567 /*
 568  * make_rel_from_joinlist
 569  *        Build access paths using a "joinlist" to guide the join path search.
 570  *
 571  * See comments for deconstruct_jointree() for definition of the joinlist
 572  * data structure.
 573  */
 574 static RelOptInfo *
 575 make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
 576 {
 577         int                     levels_needed;
 578         List       *initial_rels;
 579         ListCell   *jl;
 580
 581         /*
 582          * Count the number of child joinlist nodes.  This is the depth of the
 583          * dynamic-programming algorithm we must employ to consider all ways of
 584          * joining the child nodes.
 585          */
 586         levels_needed = list_length(joinlist);
 587
 588         if (levels_needed <= 0)
 589                 return NULL;                    /* nothing to do? */
 590
 591         /*
 592          * Construct a list of rels corresponding to the child joinlist nodes.
 593          * This may contain both base rels and rels constructed according to
 594          * sub-joinlists.
 595          */
 596         initial_rels = NIL;
 597         foreach(jl, joinlist)
 598         {
 599                 Node       *jlnode = (Node *) lfirst(jl);
 600                 RelOptInfo *thisrel;
 601
 602                 if (IsA(jlnode, RangeTblRef))
 603                 {
 604                         int                     varno = ((RangeTblRef *) jlnode)->rtindex;
 605
 606                         thisrel = find_base_rel(root, varno);
 607                 }
 608                 else if (IsA(jlnode, List))
 609                 {
 610                         /* Recurse to handle subproblem */
 611                         thisrel = make_rel_from_joinlist(root, (List *) jlnode);
 612                 }
 613                 else
 614                 {
 615                         elog(ERROR, "unrecognized joinlist node type: %d",
 616                                  (int) nodeTag(jlnode));
 617                         thisrel = NULL;         /* keep compiler quiet */
 618                 }
 619
 620                 initial_rels = lappend(initial_rels, thisrel);
 621         }
 622
 623         if (levels_needed == 1)
 624         {
 625                 /*
 626                  * Single joinlist node, so we're done.
 627                  */
 628                 return (RelOptInfo *) linitial(initial_rels);
 629         }
 630         else
 631         {
 632                 /*
 633                  * Consider the different orders in which we could join the rels,
 634                  * using either GEQO or regular optimizer.
 635                  */
 636                 if (enable_geqo && levels_needed >= geqo_threshold)
 637                         return geqo(root, levels_needed, initial_rels);
 638                 else
 639                         return make_one_rel_by_joins(root, levels_needed, initial_rels);
 640         }
 641 }
 642
 643 /*
 644  * make_one_rel_by_joins
 645  *        Find all possible joinpaths for a query by successively finding ways
 646  *        to join component relations into join relations.
 647  *
 648  * 'levels_needed' is the number of iterations needed, ie, the number of
 649  *              independent jointree items in the query.  This is > 1.
 650  *
 651  * 'initial_rels' is a list of RelOptInfo nodes for each independent
 652  *              jointree item.  These are the components to be joined together.
 653  *
 654  * Returns the final level of join relations, i.e., the relation that is
 655  * the result of joining all the original relations together.
 656  */
 657 static RelOptInfo *
 658 make_one_rel_by_joins(PlannerInfo *root, int levels_needed, List *initial_rels)
 659 {
 660         List      **joinitems;
 661         int                     lev;
 662         RelOptInfo *rel;
 663
 664         /*
 665          * We employ a simple "dynamic programming" algorithm: we first find all
 666          * ways to build joins of two jointree items, then all ways to build joins
 667          * of three items (from two-item joins and single items), then four-item
 668          * joins, and so on until we have considered all ways to join all the
 669          * items into one rel.
 670          *
 671          * joinitems[j] is a list of all the j-item rels.  Initially we set
 672          * joinitems[1] to represent all the single-jointree-item relations.
 673          */
 674         joinitems = (List **) palloc0((levels_needed + 1) * sizeof(List *));
 675
 676         joinitems[1] = initial_rels;
 677
 678         for (lev = 2; lev <= levels_needed; lev++)
 679         {
 680                 ListCell   *x;
 681
 682                 /*
 683                  * Determine all possible pairs of relations to be joined at this
 684                  * level, and build paths for making each one from every available
 685                  * pair of lower-level relations.
 686                  */
 687                 joinitems[lev] = make_rels_by_joins(root, lev, joinitems);
 688
 689                 /*
 690                  * Do cleanup work on each just-processed rel.
 691                  */
 692                 foreach(x, joinitems[lev])
 693                 {
 694                         rel = (RelOptInfo *) lfirst(x);
 695
 696                         /* Find and save the cheapest paths for this rel */
 697                         set_cheapest(rel);
 698
 699 #ifdef OPTIMIZER_DEBUG
 700                         debug_print_rel(root, rel);
 701 #endif
 702                 }
 703         }
 704
 705         /*
 706          * We should have a single rel at the final level.
 707          */
 708         if (joinitems[levels_needed] == NIL)
 709                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
 710         Assert(list_length(joinitems[levels_needed]) == 1);
 711
 712         rel = (RelOptInfo *) linitial(joinitems[levels_needed]);
 713
 714         return rel;
 715 }
 716
 717 /*****************************************************************************
 718  *                      PUSHING QUALS DOWN INTO SUBQUERIES
 719  *****************************************************************************/
 720
 721 /*
 722  * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
 723  *
 724  * subquery is the particular component query being checked.  topquery
 725  * is the top component of a set-operations tree (the same Query if no
 726  * set-op is involved).
 727  *
 728  * Conditions checked here:
 729  *
 730  * 1. If the subquery has a LIMIT clause, we must not push down any quals,
 731  * since that could change the set of rows returned.
 732  *
 733  * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
 734  * quals into it, because that would change the results.
 735  *
 736  * 3. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
 737  * push quals into each component query, but the quals can only reference
 738  * subquery columns that suffer no type coercions in the set operation.
 739  * Otherwise there are possible semantic gotchas.  So, we check the
 740  * component queries to see if any of them have different output types;
 741  * differentTypes[k] is set true if column k has different type in any
 742  * component.
 743  */
 744 static bool
 745 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
 746                                                   bool *differentTypes)
 747 {
 748         SetOperationStmt *topop;
 749
 750         /* Check point 1 */
 751         if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
 752                 return false;
 753
 754         /* Are we at top level, or looking at a setop component? */
 755         if (subquery == topquery)
 756         {
 757                 /* Top level, so check any component queries */
 758                 if (subquery->setOperations != NULL)
 759                         if (!recurse_pushdown_safe(subquery->setOperations, topquery,
 760                                                                            differentTypes))
 761                                 return false;
 762         }
 763         else
 764         {
 765                 /* Setop component must not have more components (too weird) */
 766                 if (subquery->setOperations != NULL)
 767                         return false;
 768                 /* Check whether setop component output types match top level */
 769                 topop = (SetOperationStmt *) topquery->setOperations;
 770                 Assert(topop && IsA(topop, SetOperationStmt));
 771                 compare_tlist_datatypes(subquery->targetList,
 772                                                                 topop->colTypes,
 773                                                                 differentTypes);
 774         }
 775         return true;
 776 }
 777
 778 /*
 779  * Helper routine to recurse through setOperations tree
 780  */
 781 static bool
 782 recurse_pushdown_safe(Node *setOp, Query *topquery,
 783                                           bool *differentTypes)
 784 {
 785         if (IsA(setOp, RangeTblRef))
 786         {
 787                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 788                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
 789                 Query      *subquery = rte->subquery;
 790
 791                 Assert(subquery != NULL);
 792                 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
 793         }
 794         else if (IsA(setOp, SetOperationStmt))
 795         {
 796                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 797
 798                 /* EXCEPT is no good */
 799                 if (op->op == SETOP_EXCEPT)
 800                         return false;
 801                 /* Else recurse */
 802                 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
 803                         return false;
 804                 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
 805                         return false;
 806         }
 807         else
 808         {
 809                 elog(ERROR, "unrecognized node type: %d",
 810                          (int) nodeTag(setOp));
 811         }
 812         return true;
 813 }
 814
 815 /*
 816  * Compare tlist's datatypes against the list of set-operation result types.
 817  * For any items that are different, mark the appropriate element of
 818  * differentTypes[] to show that this column will have type conversions.
 819  *
 820  * We don't have to care about typmods here: the only allowed difference
 821  * between set-op input and output typmods is input is a specific typmod
 822  * and output is -1, and that does not require a coercion.
 823  */
 824 static void
 825 compare_tlist_datatypes(List *tlist, List *colTypes,
 826                                                 bool *differentTypes)
 827 {
 828         ListCell   *l;
 829         ListCell   *colType = list_head(colTypes);
 830
 831         foreach(l, tlist)
 832         {
 833                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 834
 835                 if (tle->resjunk)
 836                         continue;                       /* ignore resjunk columns */
 837                 if (colType == NULL)
 838                         elog(ERROR, "wrong number of tlist entries");
 839                 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
 840                         differentTypes[tle->resno] = true;
 841                 colType = lnext(colType);
 842         }
 843         if (colType != NULL)
 844                 elog(ERROR, "wrong number of tlist entries");
 845 }
 846
 847 /*
 848  * qual_is_pushdown_safe - is a particular qual safe to push down?
 849  *
 850  * qual is a restriction clause applying to the given subquery (whose RTE
 851  * has index rti in the parent query).
 852  *
 853  * Conditions checked here:
 854  *
 855  * 1. The qual must not contain any subselects (mainly because I'm not sure
 856  * it will work correctly: sublinks will already have been transformed into
 857  * subplans in the qual, but not in the subquery).
 858  *
 859  * 2. The qual must not refer to the whole-row output of the subquery
 860  * (since there is no easy way to name that within the subquery itself).
 861  *
 862  * 3. The qual must not refer to any subquery output columns that were
 863  * found to have inconsistent types across a set operation tree by
 864  * subquery_is_pushdown_safe().
 865  *
 866  * 4. If the subquery uses DISTINCT ON, we must not push down any quals that
 867  * refer to non-DISTINCT output columns, because that could change the set
 868  * of rows returned.  This condition is vacuous for DISTINCT, because then
 869  * there are no non-DISTINCT output columns, but unfortunately it's fairly
 870  * expensive to tell the difference between DISTINCT and DISTINCT ON in the
 871  * parsetree representation.  It's cheaper to just make sure all the Vars
 872  * in the qual refer to DISTINCT columns.
 873  *
 874  * 5. We must not push down any quals that refer to subselect outputs that
 875  * return sets, else we'd introduce functions-returning-sets into the
 876  * subquery's WHERE/HAVING quals.
 877  *
 878  * 6. We must not push down any quals that refer to subselect outputs that
 879  * contain volatile functions, for fear of introducing strange results due
 880  * to multiple evaluation of a volatile function.
 881  */
 882 static bool
 883 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
 884                                           bool *differentTypes)
 885 {
 886         bool            safe = true;
 887         List       *vars;
 888         ListCell   *vl;
 889         Bitmapset  *tested = NULL;
 890
 891         /* Refuse subselects (point 1) */
 892         if (contain_subplans(qual))
 893                 return false;
 894
 895         /*
 896          * Examine all Vars used in clause; since it's a restriction clause, all
 897          * such Vars must refer to subselect output columns.
 898          */
 899         vars = pull_var_clause(qual, false);
 900         foreach(vl, vars)
 901         {
 902                 Var                *var = (Var *) lfirst(vl);
 903                 TargetEntry *tle;
 904
 905                 Assert(var->varno == rti);
 906
 907                 /* Check point 2 */
 908                 if (var->varattno == 0)
 909                 {
 910                         safe = false;
 911                         break;
 912                 }
 913
 914                 /*
 915                  * We use a bitmapset to avoid testing the same attno more than once.
 916                  * (NB: this only works because subquery outputs can't have negative
 917                  * attnos.)
 918                  */
 919                 if (bms_is_member(var->varattno, tested))
 920                         continue;
 921                 tested = bms_add_member(tested, var->varattno);
 922
 923                 /* Check point 3 */
 924                 if (differentTypes[var->varattno])
 925                 {
 926                         safe = false;
 927                         break;
 928                 }
 929
 930                 /* Must find the tlist element referenced by the Var */
 931                 tle = get_tle_by_resno(subquery->targetList, var->varattno);
 932                 Assert(tle != NULL);
 933                 Assert(!tle->resjunk);
 934
 935                 /* If subquery uses DISTINCT or DISTINCT ON, check point 4 */
 936                 if (subquery->distinctClause != NIL &&
 937                         !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
 938                 {
 939                         /* non-DISTINCT column, so fail */
 940                         safe = false;
 941                         break;
 942                 }
 943
 944                 /* Refuse functions returning sets (point 5) */
 945                 if (expression_returns_set((Node *) tle->expr))
 946                 {
 947                         safe = false;
 948                         break;
 949                 }
 950
 951                 /* Refuse volatile functions (point 6) */
 952                 if (contain_volatile_functions((Node *) tle->expr))
 953                 {
 954                         safe = false;
 955                         break;
 956                 }
 957         }
 958
 959         list_free(vars);
 960         bms_free(tested);
 961
 962         return safe;
 963 }
 964
 965 /*
 966  * subquery_push_qual - push down a qual that we have determined is safe
 967  */
 968 static void
 969 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
 970 {
 971         if (subquery->setOperations != NULL)
 972         {
 973                 /* Recurse to push it separately to each component query */
 974                 recurse_push_qual(subquery->setOperations, subquery,
 975                                                   rte, rti, qual);
 976         }
 977         else
 978         {
 979                 /*
 980                  * We need to replace Vars in the qual (which must refer to outputs of
 981                  * the subquery) with copies of the subquery's targetlist expressions.
 982                  * Note that at this point, any uplevel Vars in the qual should have
 983                  * been replaced with Params, so they need no work.
 984                  *
 985                  * This step also ensures that when we are pushing into a setop tree,
 986                  * each component query gets its own copy of the qual.
 987                  */
 988                 qual = ResolveNew(qual, rti, 0, rte,
 989                                                   subquery->targetList,
 990                                                   CMD_SELECT, 0);
 991
 992                 /*
 993                  * Now attach the qual to the proper place: normally WHERE, but if the
 994                  * subquery uses grouping or aggregation, put it in HAVING (since the
 995                  * qual really refers to the group-result rows).
 996                  */
 997                 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
 998                         subquery->havingQual = make_and_qual(subquery->havingQual, qual);
 999                 else
1000                         subquery->jointree->quals =
1001                                 make_and_qual(subquery->jointree->quals, qual);
1002
1003                 /*
1004                  * We need not change the subquery's hasAggs or hasSublinks flags,
1005                  * since we can't be pushing down any aggregates that weren't there
1006                  * before, and we don't push down subselects at all.
1007                  */
1008         }
1009 }
1010
1011 /*
1012  * Helper routine to recurse through setOperations tree
1013  */
1014 static void
1015 recurse_push_qual(Node *setOp, Query *topquery,
1016                                   RangeTblEntry *rte, Index rti, Node *qual)
1017 {
1018         if (IsA(setOp, RangeTblRef))
1019         {
1020                 RangeTblRef *rtr = (RangeTblRef *) setOp;
1021                 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
1022                 Query      *subquery = subrte->subquery;
1023
1024                 Assert(subquery != NULL);
1025                 subquery_push_qual(subquery, rte, rti, qual);
1026         }
1027         else if (IsA(setOp, SetOperationStmt))
1028         {
1029                 SetOperationStmt *op = (SetOperationStmt *) setOp;
1030
1031                 recurse_push_qual(op->larg, topquery, rte, rti, qual);
1032                 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
1033         }
1034         else
1035         {
1036                 elog(ERROR, "unrecognized node type: %d",
1037                          (int) nodeTag(setOp));
1038         }
1039 }
1040
1041 /*****************************************************************************
1042  *                      DEBUG SUPPORT
1043  *****************************************************************************/
1044
1045 #ifdef OPTIMIZER_DEBUG
1046
1047 static void
1048 print_relids(Relids relids)
1049 {
1050         Relids          tmprelids;
1051         int                     x;
1052         bool            first = true;
1053
1054         tmprelids = bms_copy(relids);
1055         while ((x = bms_first_member(tmprelids)) >= 0)
1056         {
1057                 if (!first)
1058                         printf(" ");
1059                 printf("%d", x);
1060                 first = false;
1061         }
1062         bms_free(tmprelids);
1063 }
1064
1065 static void
1066 print_restrictclauses(PlannerInfo *root, List *clauses)
1067 {
1068         ListCell   *l;
1069
1070         foreach(l, clauses)
1071         {
1072                 RestrictInfo *c = lfirst(l);
1073
1074                 print_expr((Node *) c->clause, root->parse->rtable);
1075                 if (lnext(l))
1076                         printf(", ");
1077         }
1078 }
1079
1080 static void
1081 print_path(PlannerInfo *root, Path *path, int indent)
1082 {
1083         const char *ptype;
1084         bool            join = false;
1085         Path       *subpath = NULL;
1086         int                     i;
1087
1088         switch (nodeTag(path))
1089         {
1090                 case T_Path:
1091                         ptype = "SeqScan";
1092                         break;
1093                 case T_IndexPath:
1094                         ptype = "IdxScan";
1095                         break;
1096                 case T_BitmapHeapPath:
1097                         ptype = "BitmapHeapScan";
1098                         break;
1099                 case T_BitmapAndPath:
1100                         ptype = "BitmapAndPath";
1101                         break;
1102                 case T_BitmapOrPath:
1103                         ptype = "BitmapOrPath";
1104                         break;
1105                 case T_TidPath:
1106                         ptype = "TidScan";
1107                         break;
1108                 case T_AppendPath:
1109                         ptype = "Append";
1110                         break;
1111                 case T_ResultPath:
1112                         ptype = "Result";
1113                         break;
1114                 case T_MaterialPath:
1115                         ptype = "Material";
1116                         subpath = ((MaterialPath *) path)->subpath;
1117                         break;
1118                 case T_UniquePath:
1119                         ptype = "Unique";
1120                         subpath = ((UniquePath *) path)->subpath;
1121                         break;
1122                 case T_NestPath:
1123                         ptype = "NestLoop";
1124                         join = true;
1125                         break;
1126                 case T_MergePath:
1127                         ptype = "MergeJoin";
1128                         join = true;
1129                         break;
1130                 case T_HashPath:
1131                         ptype = "HashJoin";
1132                         join = true;
1133                         break;
1134                 default:
1135                         ptype = "???Path";
1136                         break;
1137         }
1138
1139         for (i = 0; i < indent; i++)
1140                 printf("\t");
1141         printf("%s", ptype);
1142
1143         if (path->parent)
1144         {
1145                 printf("(");
1146                 print_relids(path->parent->relids);
1147                 printf(") rows=%.0f", path->parent->rows);
1148         }
1149         printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
1150
1151         if (path->pathkeys)
1152         {
1153                 for (i = 0; i < indent; i++)
1154                         printf("\t");
1155                 printf("  pathkeys: ");
1156                 print_pathkeys(path->pathkeys, root->parse->rtable);
1157         }
1158
1159         if (join)
1160         {
1161                 JoinPath   *jp = (JoinPath *) path;
1162
1163                 for (i = 0; i < indent; i++)
1164                         printf("\t");
1165                 printf("  clauses: ");
1166                 print_restrictclauses(root, jp->joinrestrictinfo);
1167                 printf("\n");
1168
1169                 if (IsA(path, MergePath))
1170                 {
1171                         MergePath  *mp = (MergePath *) path;
1172
1173                         if (mp->outersortkeys || mp->innersortkeys)
1174                         {
1175                                 for (i = 0; i < indent; i++)
1176                                         printf("\t");
1177                                 printf("  sortouter=%d sortinner=%d\n",
1178                                            ((mp->outersortkeys) ? 1 : 0),
1179                                            ((mp->innersortkeys) ? 1 : 0));
1180                         }
1181                 }
1182
1183                 print_path(root, jp->outerjoinpath, indent + 1);
1184                 print_path(root, jp->innerjoinpath, indent + 1);
1185         }
1186
1187         if (subpath)
1188                 print_path(root, subpath, indent + 1);
1189 }
1190
1191 void
1192 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1193 {
1194         ListCell   *l;
1195
1196         printf("RELOPTINFO (");
1197         print_relids(rel->relids);
1198         printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1199
1200         if (rel->baserestrictinfo)
1201         {
1202                 printf("\tbaserestrictinfo: ");
1203                 print_restrictclauses(root, rel->baserestrictinfo);
1204                 printf("\n");
1205         }
1206
1207         if (rel->joininfo)
1208         {
1209                 printf("\tjoininfo: ");
1210                 print_restrictclauses(root, rel->joininfo);
1211                 printf("\n");
1212         }
1213
1214         printf("\tpath list:\n");
1215         foreach(l, rel->pathlist)
1216                 print_path(root, lfirst(l), 1);
1217         printf("\n\tcheapest startup path:\n");
1218         print_path(root, rel->cheapest_startup_path, 1);
1219         printf("\n\tcheapest total path:\n");
1220         print_path(root, rel->cheapest_total_path, 1);
1221         printf("\n");
1222         fflush(stdout);
1223 }
1224
1225 #endif   /* OPTIMIZER_DEBUG */