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-2005, 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.133 2005/06/09 04:18:59 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/parsetree.h"
  31 #include "parser/parse_clause.h"
  32 #include "parser/parse_expr.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_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  43                                            RangeTblEntry *rte);
  44 static void set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  45                                                    Index rti, RangeTblEntry *rte,
  46                                                    List *inheritlist);
  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 RelOptInfo *make_one_rel_by_joins(PlannerInfo *root, int levels_needed,
  52                                           List *initial_rels);
  53 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
  54                                                   bool *differentTypes);
  55 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
  56                                           bool *differentTypes);
  57 static void compare_tlist_datatypes(List *tlist, List *colTypes,
  58                                                 bool *differentTypes);
  59 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
  60                                           bool *differentTypes);
  61 static void subquery_push_qual(Query *subquery,
  62                                                            RangeTblEntry *rte, Index rti, Node *qual);
  63 static void recurse_push_qual(Node *setOp, Query *topquery,
  64                                   RangeTblEntry *rte, Index rti, Node *qual);
  65
  66
  67 /*
  68  * make_one_rel
  69  *        Finds all possible access paths for executing a query, returning a
  70  *        single rel that represents the join of all base rels in the query.
  71  */
  72 RelOptInfo *
  73 make_one_rel(PlannerInfo *root)
  74 {
  75         RelOptInfo *rel;
  76
  77         /*
  78          * Generate access paths for the base rels.
  79          */
  80         set_base_rel_pathlists(root);
  81
  82         /*
  83          * Generate access paths for the entire join tree.
  84          */
  85         Assert(root->parse->jointree != NULL &&
  86                    IsA(root->parse->jointree, FromExpr));
  87
  88         rel = make_fromexpr_rel(root, root->parse->jointree);
  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->base_rel_array_size; rti++)
  99                 {
 100                         RelOptInfo *brel = root->base_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         /*
 134          * Note: because we call expand_inherited_rtentry inside the loop,
 135          * it's quite possible for the base_rel_array to be enlarged while
 136          * the loop runs.  Hence don't try to optimize the loop.
 137          */
 138         for (rti = 1; rti < root->base_rel_array_size; rti++)
 139         {
 140                 RelOptInfo *rel = root->base_rel_array[rti];
 141                 RangeTblEntry *rte;
 142                 List       *inheritlist;
 143
 144                 /* there may be empty slots corresponding to non-baserel RTEs */
 145                 if (rel == NULL)
 146                         continue;
 147
 148                 Assert(rel->relid == rti);              /* sanity check on array */
 149
 150                 /* ignore RTEs that are "other rels" */
 151                 if (rel->reloptkind != RELOPT_BASEREL)
 152                         continue;
 153
 154                 rte = rt_fetch(rti, root->parse->rtable);
 155
 156                 if (rel->rtekind == RTE_SUBQUERY)
 157                 {
 158                         /* Subquery --- generate a separate plan for it */
 159                         set_subquery_pathlist(root, rel, rti, rte);
 160                 }
 161                 else if (rel->rtekind == RTE_FUNCTION)
 162                 {
 163                         /* RangeFunction --- generate a separate plan for it */
 164                         set_function_pathlist(root, rel, rte);
 165                 }
 166                 else if ((inheritlist = expand_inherited_rtentry(root, rti)) != NIL)
 167                 {
 168                         /* Relation is root of an inheritance tree, process specially */
 169                         set_inherited_rel_pathlist(root, rel, rti, rte, inheritlist);
 170                 }
 171                 else
 172                 {
 173                         /* Plain relation */
 174                         set_plain_rel_pathlist(root, rel, rte);
 175                 }
 176
 177 #ifdef OPTIMIZER_DEBUG
 178                 debug_print_rel(root, rel);
 179 #endif
 180         }
 181 }
 182
 183 /*
 184  * set_plain_rel_pathlist
 185  *        Build access paths for a plain relation (no subquery, no inheritance)
 186  */
 187 static void
 188 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 189 {
 190         /* Mark rel with estimated output rows, width, etc */
 191         set_baserel_size_estimates(root, rel);
 192
 193         /* Test any partial indexes of rel for applicability */
 194         check_partial_indexes(root, rel);
 195
 196         /*
 197          * Check to see if we can extract any restriction conditions from join
 198          * quals that are OR-of-AND structures.  If so, add them to the rel's
 199          * restriction list, and recompute the size estimates.
 200          */
 201         if (create_or_index_quals(root, rel))
 202                 set_baserel_size_estimates(root, rel);
 203
 204         /*
 205          * Generate paths and add them to the rel's pathlist.
 206          *
 207          * Note: add_path() will discard any paths that are dominated by another
 208          * available path, keeping only those paths that are superior along at
 209          * least one dimension of cost or sortedness.
 210          */
 211
 212         /* Consider sequential scan */
 213         add_path(rel, create_seqscan_path(root, rel));
 214
 215         /* Consider index scans */
 216         create_index_paths(root, rel);
 217
 218         /* Consider TID scans */
 219         create_tidscan_paths(root, rel);
 220
 221         /* Now find the cheapest of the paths for this rel */
 222         set_cheapest(rel);
 223 }
 224
 225 /*
 226  * set_inherited_rel_pathlist
 227  *        Build access paths for a inheritance tree rooted at rel
 228  *
 229  * inheritlist is a list of RT indexes of all tables in the inheritance tree,
 230  * including a duplicate of the parent itself.  Note we will not come here
 231  * unless there's at least one child in addition to the parent.
 232  *
 233  * NOTE: the passed-in rel and RTE will henceforth represent the appended
 234  * result of the whole inheritance tree.  The members of inheritlist represent
 235  * the individual tables --- in particular, the inheritlist member that is a
 236  * duplicate of the parent RTE represents the parent table alone.
 237  * We will generate plans to scan the individual tables that refer to
 238  * the inheritlist RTEs, whereas Vars elsewhere in the plan tree that
 239  * refer to the original RTE are taken to refer to the append output.
 240  * In particular, this means we have separate RelOptInfos for the parent
 241  * table and for the append output, which is a good thing because they're
 242  * not the same size.
 243  */
 244 static void
 245 set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 246                                                    Index rti, RangeTblEntry *rte,
 247                                                    List *inheritlist)
 248 {
 249         int                     parentRTindex = rti;
 250         Oid                     parentOID = rte->relid;
 251         List       *subpaths = NIL;
 252         ListCell   *il;
 253
 254         /*
 255          * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE;
 256          * can we do better?
 257          */
 258         if (list_member_int(root->parse->rowMarks, parentRTindex))
 259                 ereport(ERROR,
 260                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 261                                  errmsg("SELECT FOR UPDATE/SHARE is not supported for inheritance queries")));
 262
 263         /*
 264          * Initialize to compute size estimates for whole inheritance tree
 265          */
 266         rel->rows = 0;
 267         rel->width = 0;
 268
 269         /*
 270          * Generate access paths for each table in the tree (parent AND
 271          * children), and pick the cheapest path for each table.
 272          */
 273         foreach(il, inheritlist)
 274         {
 275                 int                     childRTindex = lfirst_int(il);
 276                 RangeTblEntry *childrte;
 277                 Oid                     childOID;
 278                 RelOptInfo *childrel;
 279                 ListCell   *parentvars;
 280                 ListCell   *childvars;
 281
 282                 childrte = rt_fetch(childRTindex, root->parse->rtable);
 283                 childOID = childrte->relid;
 284
 285                 /*
 286                  * Make a RelOptInfo for the child so we can do planning.
 287                  * Mark it as an "other rel" since it will not be part of the
 288                  * main join tree.
 289                  */
 290                 childrel = build_other_rel(root, childRTindex);
 291
 292                 /*
 293                  * Copy the parent's targetlist and restriction quals to the
 294                  * child, with attribute-number adjustment as needed.  We don't
 295                  * bother to copy the join quals, since we can't do any joining of
 296                  * the individual tables.  Also, we just zap attr_needed rather
 297                  * than trying to adjust it; it won't be looked at in the child.
 298                  */
 299                 childrel->reltargetlist = (List *)
 300                         adjust_inherited_attrs((Node *) rel->reltargetlist,
 301                                                                    parentRTindex,
 302                                                                    parentOID,
 303                                                                    childRTindex,
 304                                                                    childOID);
 305                 childrel->attr_needed = NULL;
 306                 childrel->baserestrictinfo = (List *)
 307                         adjust_inherited_attrs((Node *) rel->baserestrictinfo,
 308                                                                    parentRTindex,
 309                                                                    parentOID,
 310                                                                    childRTindex,
 311                                                                    childOID);
 312
 313                 /*
 314                  * Now compute child access paths, and save the cheapest.
 315                  */
 316                 set_plain_rel_pathlist(root, childrel, childrte);
 317
 318                 subpaths = lappend(subpaths, childrel->cheapest_total_path);
 319
 320                 /*
 321                  * Propagate size information from the child back to the parent.
 322                  * For simplicity, we use the largest widths from any child as the
 323                  * parent estimates.
 324                  */
 325                 rel->rows += childrel->rows;
 326                 if (childrel->width > rel->width)
 327                         rel->width = childrel->width;
 328
 329                 forboth(parentvars, rel->reltargetlist,
 330                                 childvars, childrel->reltargetlist)
 331                 {
 332                         Var                *parentvar = (Var *) lfirst(parentvars);
 333                         Var                *childvar = (Var *) lfirst(childvars);
 334
 335                         if (IsA(parentvar, Var) &&IsA(childvar, Var))
 336                         {
 337                                 int                     pndx = parentvar->varattno - rel->min_attr;
 338                                 int                     cndx = childvar->varattno - childrel->min_attr;
 339
 340                                 if (childrel->attr_widths[cndx] > rel->attr_widths[pndx])
 341                                         rel->attr_widths[pndx] = childrel->attr_widths[cndx];
 342                         }
 343                 }
 344         }
 345
 346         /*
 347          * Finally, build Append path and install it as the only access path
 348          * for the parent rel.
 349          */
 350         add_path(rel, (Path *) create_append_path(rel, subpaths));
 351
 352         /* Select cheapest path (pretty easy in this case...) */
 353         set_cheapest(rel);
 354 }
 355
 356 /*
 357  * set_subquery_pathlist
 358  *              Build the (single) access path for a subquery RTE
 359  */
 360 static void
 361 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 362                                           Index rti, RangeTblEntry *rte)
 363 {
 364         Query      *subquery = rte->subquery;
 365         bool       *differentTypes;
 366         List       *pathkeys;
 367         List       *subquery_pathkeys;
 368
 369         /* We need a workspace for keeping track of set-op type coercions */
 370         differentTypes = (bool *)
 371                 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
 372
 373         /*
 374          * If there are any restriction clauses that have been attached to the
 375          * subquery relation, consider pushing them down to become WHERE or
 376          * HAVING quals of the subquery itself.  This transformation is useful
 377          * because it may allow us to generate a better plan for the subquery
 378          * than evaluating all the subquery output rows and then filtering them.
 379          *
 380          * There are several cases where we cannot push down clauses.
 381          * Restrictions involving the subquery are checked by
 382          * subquery_is_pushdown_safe().  Restrictions on individual clauses
 383          * are checked by qual_is_pushdown_safe().
 384          *
 385          * Non-pushed-down clauses will get evaluated as qpquals of the
 386          * SubqueryScan node.
 387          *
 388          * XXX Are there any cases where we want to make a policy decision not to
 389          * push down a pushable qual, because it'd result in a worse plan?
 390          */
 391         if (rel->baserestrictinfo != NIL &&
 392                 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
 393         {
 394                 /* OK to consider pushing down individual quals */
 395                 List       *upperrestrictlist = NIL;
 396                 ListCell   *l;
 397
 398                 foreach(l, rel->baserestrictinfo)
 399                 {
 400                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 401                         Node       *clause = (Node *) rinfo->clause;
 402
 403                         if (qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
 404                         {
 405                                 /* Push it down */
 406                                 subquery_push_qual(subquery, rte, rti, clause);
 407                         }
 408                         else
 409                         {
 410                                 /* Keep it in the upper query */
 411                                 upperrestrictlist = lappend(upperrestrictlist, rinfo);
 412                         }
 413                 }
 414                 rel->baserestrictinfo = upperrestrictlist;
 415         }
 416
 417         pfree(differentTypes);
 418
 419         /* Generate the plan for the subquery */
 420         rel->subplan = subquery_planner(subquery, 0.0 /* default case */,
 421                                                                         &subquery_pathkeys);
 422
 423         /* Copy number of output rows from subplan */
 424         rel->tuples = rel->subplan->plan_rows;
 425
 426         /* Mark rel with estimated output rows, width, etc */
 427         set_baserel_size_estimates(root, rel);
 428
 429         /* Convert subquery pathkeys to outer representation */
 430         pathkeys = convert_subquery_pathkeys(root, rel, subquery_pathkeys);
 431
 432         /* Generate appropriate path */
 433         add_path(rel, create_subqueryscan_path(rel, pathkeys));
 434
 435         /* Select cheapest path (pretty easy in this case...) */
 436         set_cheapest(rel);
 437 }
 438
 439 /*
 440  * set_function_pathlist
 441  *              Build the (single) access path for a function RTE
 442  */
 443 static void
 444 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 445 {
 446         /* Mark rel with estimated output rows, width, etc */
 447         set_function_size_estimates(root, rel);
 448
 449         /* Generate appropriate path */
 450         add_path(rel, create_functionscan_path(root, rel));
 451
 452         /* Select cheapest path (pretty easy in this case...) */
 453         set_cheapest(rel);
 454 }
 455
 456 /*
 457  * make_fromexpr_rel
 458  *        Build access paths for a FromExpr jointree node.
 459  */
 460 RelOptInfo *
 461 make_fromexpr_rel(PlannerInfo *root, FromExpr *from)
 462 {
 463         int                     levels_needed;
 464         List       *initial_rels = NIL;
 465         ListCell   *jt;
 466
 467         /*
 468          * Count the number of child jointree nodes.  This is the depth of the
 469          * dynamic-programming algorithm we must employ to consider all ways
 470          * of joining the child nodes.
 471          */
 472         levels_needed = list_length(from->fromlist);
 473
 474         if (levels_needed <= 0)
 475                 return NULL;                    /* nothing to do? */
 476
 477         /*
 478          * Construct a list of rels corresponding to the child jointree nodes.
 479          * This may contain both base rels and rels constructed according to
 480          * explicit JOIN directives.
 481          */
 482         foreach(jt, from->fromlist)
 483         {
 484                 Node       *jtnode = (Node *) lfirst(jt);
 485
 486                 initial_rels = lappend(initial_rels,
 487                                                            make_jointree_rel(root, jtnode));
 488         }
 489
 490         if (levels_needed == 1)
 491         {
 492                 /*
 493                  * Single jointree node, so we're done.
 494                  */
 495                 return (RelOptInfo *) linitial(initial_rels);
 496         }
 497         else
 498         {
 499                 /*
 500                  * Consider the different orders in which we could join the rels,
 501                  * using either GEQO or regular optimizer.
 502                  */
 503                 if (enable_geqo && levels_needed >= geqo_threshold)
 504                         return geqo(root, levels_needed, initial_rels);
 505                 else
 506                         return make_one_rel_by_joins(root, levels_needed, initial_rels);
 507         }
 508 }
 509
 510 /*
 511  * make_one_rel_by_joins
 512  *        Find all possible joinpaths for a query by successively finding ways
 513  *        to join component relations into join relations.
 514  *
 515  * 'levels_needed' is the number of iterations needed, ie, the number of
 516  *              independent jointree items in the query.  This is > 1.
 517  *
 518  * 'initial_rels' is a list of RelOptInfo nodes for each independent
 519  *              jointree item.  These are the components to be joined together.
 520  *
 521  * Returns the final level of join relations, i.e., the relation that is
 522  * the result of joining all the original relations together.
 523  */
 524 static RelOptInfo *
 525 make_one_rel_by_joins(PlannerInfo *root, int levels_needed, List *initial_rels)
 526 {
 527         List      **joinitems;
 528         int                     lev;
 529         RelOptInfo *rel;
 530
 531         /*
 532          * We employ a simple "dynamic programming" algorithm: we first find
 533          * all ways to build joins of two jointree items, then all ways to
 534          * build joins of three items (from two-item joins and single items),
 535          * then four-item joins, and so on until we have considered all ways
 536          * to join all the items into one rel.
 537          *
 538          * joinitems[j] is a list of all the j-item rels.  Initially we set
 539          * joinitems[1] to represent all the single-jointree-item relations.
 540          */
 541         joinitems = (List **) palloc0((levels_needed + 1) * sizeof(List *));
 542
 543         joinitems[1] = initial_rels;
 544
 545         for (lev = 2; lev <= levels_needed; lev++)
 546         {
 547                 ListCell   *x;
 548
 549                 /*
 550                  * Determine all possible pairs of relations to be joined at this
 551                  * level, and build paths for making each one from every available
 552                  * pair of lower-level relations.
 553                  */
 554                 joinitems[lev] = make_rels_by_joins(root, lev, joinitems);
 555
 556                 /*
 557                  * Do cleanup work on each just-processed rel.
 558                  */
 559                 foreach(x, joinitems[lev])
 560                 {
 561                         rel = (RelOptInfo *) lfirst(x);
 562
 563                         /* Find and save the cheapest paths for this rel */
 564                         set_cheapest(rel);
 565
 566 #ifdef OPTIMIZER_DEBUG
 567                         debug_print_rel(root, rel);
 568 #endif
 569                 }
 570         }
 571
 572         /*
 573          * We should have a single rel at the final level.
 574          */
 575         if (joinitems[levels_needed] == NIL)
 576                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
 577         Assert(list_length(joinitems[levels_needed]) == 1);
 578
 579         rel = (RelOptInfo *) linitial(joinitems[levels_needed]);
 580
 581         return rel;
 582 }
 583
 584 /*****************************************************************************
 585  *                      PUSHING QUALS DOWN INTO SUBQUERIES
 586  *****************************************************************************/
 587
 588 /*
 589  * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
 590  *
 591  * subquery is the particular component query being checked.  topquery
 592  * is the top component of a set-operations tree (the same Query if no
 593  * set-op is involved).
 594  *
 595  * Conditions checked here:
 596  *
 597  * 1. If the subquery has a LIMIT clause, we must not push down any quals,
 598  * since that could change the set of rows returned.
 599  *
 600  * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
 601  * quals into it, because that would change the results.
 602  *
 603  * 3. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
 604  * push quals into each component query, but the quals can only reference
 605  * subquery columns that suffer no type coercions in the set operation.
 606  * Otherwise there are possible semantic gotchas.  So, we check the
 607  * component queries to see if any of them have different output types;
 608  * differentTypes[k] is set true if column k has different type in any
 609  * component.
 610  */
 611 static bool
 612 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
 613                                                   bool *differentTypes)
 614 {
 615         SetOperationStmt *topop;
 616
 617         /* Check point 1 */
 618         if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
 619                 return false;
 620
 621         /* Are we at top level, or looking at a setop component? */
 622         if (subquery == topquery)
 623         {
 624                 /* Top level, so check any component queries */
 625                 if (subquery->setOperations != NULL)
 626                         if (!recurse_pushdown_safe(subquery->setOperations, topquery,
 627                                                                            differentTypes))
 628                                 return false;
 629         }
 630         else
 631         {
 632                 /* Setop component must not have more components (too weird) */
 633                 if (subquery->setOperations != NULL)
 634                         return false;
 635                 /* Check whether setop component output types match top level */
 636                 topop = (SetOperationStmt *) topquery->setOperations;
 637                 Assert(topop && IsA(topop, SetOperationStmt));
 638                 compare_tlist_datatypes(subquery->targetList,
 639                                                                 topop->colTypes,
 640                                                                 differentTypes);
 641         }
 642         return true;
 643 }
 644
 645 /*
 646  * Helper routine to recurse through setOperations tree
 647  */
 648 static bool
 649 recurse_pushdown_safe(Node *setOp, Query *topquery,
 650                                           bool *differentTypes)
 651 {
 652         if (IsA(setOp, RangeTblRef))
 653         {
 654                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 655                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
 656                 Query      *subquery = rte->subquery;
 657
 658                 Assert(subquery != NULL);
 659                 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
 660         }
 661         else if (IsA(setOp, SetOperationStmt))
 662         {
 663                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 664
 665                 /* EXCEPT is no good */
 666                 if (op->op == SETOP_EXCEPT)
 667                         return false;
 668                 /* Else recurse */
 669                 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
 670                         return false;
 671                 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
 672                         return false;
 673         }
 674         else
 675         {
 676                 elog(ERROR, "unrecognized node type: %d",
 677                          (int) nodeTag(setOp));
 678         }
 679         return true;
 680 }
 681
 682 /*
 683  * Compare tlist's datatypes against the list of set-operation result types.
 684  * For any items that are different, mark the appropriate element of
 685  * differentTypes[] to show that this column will have type conversions.
 686  */
 687 static void
 688 compare_tlist_datatypes(List *tlist, List *colTypes,
 689                                                 bool *differentTypes)
 690 {
 691         ListCell   *l;
 692         ListCell   *colType = list_head(colTypes);
 693
 694         foreach(l, tlist)
 695         {
 696                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 697
 698                 if (tle->resjunk)
 699                         continue;                       /* ignore resjunk columns */
 700                 if (colType == NULL)
 701                         elog(ERROR, "wrong number of tlist entries");
 702                 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
 703                         differentTypes[tle->resno] = true;
 704                 colType = lnext(colType);
 705         }
 706         if (colType != NULL)
 707                 elog(ERROR, "wrong number of tlist entries");
 708 }
 709
 710 /*
 711  * qual_is_pushdown_safe - is a particular qual safe to push down?
 712  *
 713  * qual is a restriction clause applying to the given subquery (whose RTE
 714  * has index rti in the parent query).
 715  *
 716  * Conditions checked here:
 717  *
 718  * 1. The qual must not contain any subselects (mainly because I'm not sure
 719  * it will work correctly: sublinks will already have been transformed into
 720  * subplans in the qual, but not in the subquery).
 721  *
 722  * 2. The qual must not refer to any subquery output columns that were
 723  * found to have inconsistent types across a set operation tree by
 724  * subquery_is_pushdown_safe().
 725  *
 726  * 3. If the subquery uses DISTINCT ON, we must not push down any quals that
 727  * refer to non-DISTINCT output columns, because that could change the set
 728  * of rows returned.  This condition is vacuous for DISTINCT, because then
 729  * there are no non-DISTINCT output columns, but unfortunately it's fairly
 730  * expensive to tell the difference between DISTINCT and DISTINCT ON in the
 731  * parsetree representation.  It's cheaper to just make sure all the Vars
 732  * in the qual refer to DISTINCT columns.
 733  *
 734  * 4. We must not push down any quals that refer to subselect outputs that
 735  * return sets, else we'd introduce functions-returning-sets into the
 736  * subquery's WHERE/HAVING quals.
 737  */
 738 static bool
 739 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
 740                                           bool *differentTypes)
 741 {
 742         bool            safe = true;
 743         List       *vars;
 744         ListCell   *vl;
 745         Bitmapset  *tested = NULL;
 746
 747         /* Refuse subselects (point 1) */
 748         if (contain_subplans(qual))
 749                 return false;
 750
 751         /*
 752          * Examine all Vars used in clause; since it's a restriction clause,
 753          * all such Vars must refer to subselect output columns.
 754          */
 755         vars = pull_var_clause(qual, false);
 756         foreach(vl, vars)
 757         {
 758                 Var                *var = (Var *) lfirst(vl);
 759                 TargetEntry *tle;
 760
 761                 Assert(var->varno == rti);
 762
 763                 /*
 764                  * We use a bitmapset to avoid testing the same attno more than
 765                  * once.  (NB: this only works because subquery outputs can't have
 766                  * negative attnos.)
 767                  */
 768                 if (bms_is_member(var->varattno, tested))
 769                         continue;
 770                 tested = bms_add_member(tested, var->varattno);
 771
 772                 /* Check point 2 */
 773                 if (differentTypes[var->varattno])
 774                 {
 775                         safe = false;
 776                         break;
 777                 }
 778
 779                 /* Must find the tlist element referenced by the Var */
 780                 tle = get_tle_by_resno(subquery->targetList, var->varattno);
 781                 Assert(tle != NULL);
 782                 Assert(!tle->resjunk);
 783
 784                 /* If subquery uses DISTINCT or DISTINCT ON, check point 3 */
 785                 if (subquery->distinctClause != NIL &&
 786                         !targetIsInSortList(tle, subquery->distinctClause))
 787                 {
 788                         /* non-DISTINCT column, so fail */
 789                         safe = false;
 790                         break;
 791                 }
 792
 793                 /* Refuse functions returning sets (point 4) */
 794                 if (expression_returns_set((Node *) tle->expr))
 795                 {
 796                         safe = false;
 797                         break;
 798                 }
 799         }
 800
 801         list_free(vars);
 802         bms_free(tested);
 803
 804         return safe;
 805 }
 806
 807 /*
 808  * subquery_push_qual - push down a qual that we have determined is safe
 809  */
 810 static void
 811 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
 812 {
 813         if (subquery->setOperations != NULL)
 814         {
 815                 /* Recurse to push it separately to each component query */
 816                 recurse_push_qual(subquery->setOperations, subquery,
 817                                                   rte, rti, qual);
 818         }
 819         else
 820         {
 821                 /*
 822                  * We need to replace Vars in the qual (which must refer to
 823                  * outputs of the subquery) with copies of the subquery's
 824                  * targetlist expressions.      Note that at this point, any uplevel
 825                  * Vars in the qual should have been replaced with Params, so they
 826                  * need no work.
 827                  *
 828                  * This step also ensures that when we are pushing into a setop tree,
 829                  * each component query gets its own copy of the qual.
 830                  */
 831                 qual = ResolveNew(qual, rti, 0, rte,
 832                                                   subquery->targetList,
 833                                                   CMD_SELECT, 0);
 834
 835                 /*
 836                  * Now attach the qual to the proper place: normally WHERE, but
 837                  * if the subquery uses grouping or aggregation, put it in HAVING
 838                  * (since the qual really refers to the group-result rows).
 839                  */
 840                 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
 841                         subquery->havingQual = make_and_qual(subquery->havingQual, qual);
 842                 else
 843                         subquery->jointree->quals =
 844                                 make_and_qual(subquery->jointree->quals, qual);
 845
 846                 /*
 847                  * We need not change the subquery's hasAggs or hasSublinks flags,
 848                  * since we can't be pushing down any aggregates that weren't
 849                  * there before, and we don't push down subselects at all.
 850                  */
 851         }
 852 }
 853
 854 /*
 855  * Helper routine to recurse through setOperations tree
 856  */
 857 static void
 858 recurse_push_qual(Node *setOp, Query *topquery,
 859                                   RangeTblEntry *rte, Index rti, Node *qual)
 860 {
 861         if (IsA(setOp, RangeTblRef))
 862         {
 863                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 864                 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
 865                 Query      *subquery = subrte->subquery;
 866
 867                 Assert(subquery != NULL);
 868                 subquery_push_qual(subquery, rte, rti, qual);
 869         }
 870         else if (IsA(setOp, SetOperationStmt))
 871         {
 872                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 873
 874                 recurse_push_qual(op->larg, topquery, rte, rti, qual);
 875                 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
 876         }
 877         else
 878         {
 879                 elog(ERROR, "unrecognized node type: %d",
 880                          (int) nodeTag(setOp));
 881         }
 882 }
 883
 884 /*****************************************************************************
 885  *                      DEBUG SUPPORT
 886  *****************************************************************************/
 887
 888 #ifdef OPTIMIZER_DEBUG
 889
 890 static void
 891 print_relids(Relids relids)
 892 {
 893         Relids          tmprelids;
 894         int                     x;
 895         bool            first = true;
 896
 897         tmprelids = bms_copy(relids);
 898         while ((x = bms_first_member(tmprelids)) >= 0)
 899         {
 900                 if (!first)
 901                         printf(" ");
 902                 printf("%d", x);
 903                 first = false;
 904         }
 905         bms_free(tmprelids);
 906 }
 907
 908 static void
 909 print_restrictclauses(PlannerInfo *root, List *clauses)
 910 {
 911         ListCell   *l;
 912
 913         foreach(l, clauses)
 914         {
 915                 RestrictInfo *c = lfirst(l);
 916
 917                 print_expr((Node *) c->clause, root->parse->rtable);
 918                 if (lnext(l))
 919                         printf(", ");
 920         }
 921 }
 922
 923 static void
 924 print_path(PlannerInfo *root, Path *path, int indent)
 925 {
 926         const char *ptype;
 927         bool            join = false;
 928         Path       *subpath = NULL;
 929         int                     i;
 930
 931         switch (nodeTag(path))
 932         {
 933                 case T_Path:
 934                         ptype = "SeqScan";
 935                         break;
 936                 case T_IndexPath:
 937                         ptype = "IdxScan";
 938                         break;
 939                 case T_BitmapHeapPath:
 940                         ptype = "BitmapHeapScan";
 941                         break;
 942                 case T_BitmapAndPath:
 943                         ptype = "BitmapAndPath";
 944                         break;
 945                 case T_BitmapOrPath:
 946                         ptype = "BitmapOrPath";
 947                         break;
 948                 case T_TidPath:
 949                         ptype = "TidScan";
 950                         break;
 951                 case T_AppendPath:
 952                         ptype = "Append";
 953                         break;
 954                 case T_ResultPath:
 955                         ptype = "Result";
 956                         subpath = ((ResultPath *) path)->subpath;
 957                         break;
 958                 case T_MaterialPath:
 959                         ptype = "Material";
 960                         subpath = ((MaterialPath *) path)->subpath;
 961                         break;
 962                 case T_UniquePath:
 963                         ptype = "Unique";
 964                         subpath = ((UniquePath *) path)->subpath;
 965                         break;
 966                 case T_NestPath:
 967                         ptype = "NestLoop";
 968                         join = true;
 969                         break;
 970                 case T_MergePath:
 971                         ptype = "MergeJoin";
 972                         join = true;
 973                         break;
 974                 case T_HashPath:
 975                         ptype = "HashJoin";
 976                         join = true;
 977                         break;
 978                 default:
 979                         ptype = "???Path";
 980                         break;
 981         }
 982
 983         for (i = 0; i < indent; i++)
 984                 printf("\t");
 985         printf("%s", ptype);
 986
 987         if (path->parent)
 988         {
 989                 printf("(");
 990                 print_relids(path->parent->relids);
 991                 printf(") rows=%.0f", path->parent->rows);
 992         }
 993         printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
 994
 995         if (path->pathkeys)
 996         {
 997                 for (i = 0; i < indent; i++)
 998                         printf("\t");
 999                 printf("  pathkeys: ");
1000                 print_pathkeys(path->pathkeys, root->parse->rtable);
1001         }
1002
1003         if (join)
1004         {
1005                 JoinPath   *jp = (JoinPath *) path;
1006
1007                 for (i = 0; i < indent; i++)
1008                         printf("\t");
1009                 printf("  clauses: ");
1010                 print_restrictclauses(root, jp->joinrestrictinfo);
1011                 printf("\n");
1012
1013                 if (IsA(path, MergePath))
1014                 {
1015                         MergePath  *mp = (MergePath *) path;
1016
1017                         if (mp->outersortkeys || mp->innersortkeys)
1018                         {
1019                                 for (i = 0; i < indent; i++)
1020                                         printf("\t");
1021                                 printf("  sortouter=%d sortinner=%d\n",
1022                                            ((mp->outersortkeys) ? 1 : 0),
1023                                            ((mp->innersortkeys) ? 1 : 0));
1024                         }
1025                 }
1026
1027                 print_path(root, jp->outerjoinpath, indent + 1);
1028                 print_path(root, jp->innerjoinpath, indent + 1);
1029         }
1030
1031         if (subpath)
1032                 print_path(root, subpath, indent + 1);
1033 }
1034
1035 void
1036 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1037 {
1038         ListCell   *l;
1039
1040         printf("RELOPTINFO (");
1041         print_relids(rel->relids);
1042         printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1043
1044         if (rel->baserestrictinfo)
1045         {
1046                 printf("\tbaserestrictinfo: ");
1047                 print_restrictclauses(root, rel->baserestrictinfo);
1048                 printf("\n");
1049         }
1050
1051         if (rel->joininfo)
1052         {
1053                 printf("\tjoininfo: ");
1054                 print_restrictclauses(root, rel->joininfo);
1055                 printf("\n");
1056         }
1057
1058         printf("\tpath list:\n");
1059         foreach(l, rel->pathlist)
1060                 print_path(root, lfirst(l), 1);
1061         printf("\n\tcheapest startup path:\n");
1062         print_path(root, rel->cheapest_startup_path, 1);
1063         printf("\n\tcheapest total path:\n");
1064         print_path(root, rel->cheapest_total_path, 1);
1065         printf("\n");
1066         fflush(stdout);
1067 }
1068
1069 #endif   /* OPTIMIZER_DEBUG */