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.134 2005/06/10 03:32:21 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 /* quick-and-dirty test to see if any joining is needed */
 357 static bool
 358 has_multiple_baserels(PlannerInfo *root)
 359 {
 360         int                     num_base_rels = 0;
 361         Index           rti;
 362
 363         for (rti = 1; rti < root->base_rel_array_size; rti++)
 364         {
 365                 RelOptInfo *brel = root->base_rel_array[rti];
 366
 367                 if (brel == NULL)
 368                         continue;
 369
 370                 /* ignore RTEs that are "other rels" */
 371                 if (brel->reloptkind == RELOPT_BASEREL)
 372                         if (++num_base_rels > 1)
 373                                 return true;
 374         }
 375         return false;
 376 }
 377
 378 /*
 379  * set_subquery_pathlist
 380  *              Build the (single) access path for a subquery RTE
 381  */
 382 static void
 383 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 384                                           Index rti, RangeTblEntry *rte)
 385 {
 386         Query      *parse = root->parse;
 387         Query      *subquery = rte->subquery;
 388         bool       *differentTypes;
 389         double          tuple_fraction;
 390         List       *pathkeys;
 391         List       *subquery_pathkeys;
 392
 393         /* We need a workspace for keeping track of set-op type coercions */
 394         differentTypes = (bool *)
 395                 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
 396
 397         /*
 398          * If there are any restriction clauses that have been attached to the
 399          * subquery relation, consider pushing them down to become WHERE or
 400          * HAVING quals of the subquery itself.  This transformation is useful
 401          * because it may allow us to generate a better plan for the subquery
 402          * than evaluating all the subquery output rows and then filtering them.
 403          *
 404          * There are several cases where we cannot push down clauses.
 405          * Restrictions involving the subquery are checked by
 406          * subquery_is_pushdown_safe().  Restrictions on individual clauses
 407          * are checked by qual_is_pushdown_safe().
 408          *
 409          * Non-pushed-down clauses will get evaluated as qpquals of the
 410          * SubqueryScan node.
 411          *
 412          * XXX Are there any cases where we want to make a policy decision not to
 413          * push down a pushable qual, because it'd result in a worse plan?
 414          */
 415         if (rel->baserestrictinfo != NIL &&
 416                 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
 417         {
 418                 /* OK to consider pushing down individual quals */
 419                 List       *upperrestrictlist = NIL;
 420                 ListCell   *l;
 421
 422                 foreach(l, rel->baserestrictinfo)
 423                 {
 424                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 425                         Node       *clause = (Node *) rinfo->clause;
 426
 427                         if (qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
 428                         {
 429                                 /* Push it down */
 430                                 subquery_push_qual(subquery, rte, rti, clause);
 431                         }
 432                         else
 433                         {
 434                                 /* Keep it in the upper query */
 435                                 upperrestrictlist = lappend(upperrestrictlist, rinfo);
 436                         }
 437                 }
 438                 rel->baserestrictinfo = upperrestrictlist;
 439         }
 440
 441         pfree(differentTypes);
 442
 443         /*
 444          * We can safely pass the outer tuple_fraction down to the subquery
 445          * if the outer level has no joining, aggregation, or sorting to do.
 446          * Otherwise we'd better tell the subquery to plan for full retrieval.
 447          * (XXX This could probably be made more intelligent ...)
 448          */
 449         if (parse->hasAggs ||
 450                 parse->groupClause ||
 451                 parse->havingQual ||
 452                 parse->distinctClause ||
 453                 parse->sortClause ||
 454                 has_multiple_baserels(root))
 455                 tuple_fraction = 0.0;   /* default case */
 456         else
 457                 tuple_fraction = root->tuple_fraction;
 458
 459         /* Generate the plan for the subquery */
 460         rel->subplan = subquery_planner(subquery, tuple_fraction,
 461                                                                         &subquery_pathkeys);
 462
 463         /* Copy number of output rows from subplan */
 464         rel->tuples = rel->subplan->plan_rows;
 465
 466         /* Mark rel with estimated output rows, width, etc */
 467         set_baserel_size_estimates(root, rel);
 468
 469         /* Convert subquery pathkeys to outer representation */
 470         pathkeys = convert_subquery_pathkeys(root, rel, subquery_pathkeys);
 471
 472         /* Generate appropriate path */
 473         add_path(rel, create_subqueryscan_path(rel, pathkeys));
 474
 475         /* Select cheapest path (pretty easy in this case...) */
 476         set_cheapest(rel);
 477 }
 478
 479 /*
 480  * set_function_pathlist
 481  *              Build the (single) access path for a function RTE
 482  */
 483 static void
 484 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 485 {
 486         /* Mark rel with estimated output rows, width, etc */
 487         set_function_size_estimates(root, rel);
 488
 489         /* Generate appropriate path */
 490         add_path(rel, create_functionscan_path(root, rel));
 491
 492         /* Select cheapest path (pretty easy in this case...) */
 493         set_cheapest(rel);
 494 }
 495
 496 /*
 497  * make_fromexpr_rel
 498  *        Build access paths for a FromExpr jointree node.
 499  */
 500 RelOptInfo *
 501 make_fromexpr_rel(PlannerInfo *root, FromExpr *from)
 502 {
 503         int                     levels_needed;
 504         List       *initial_rels = NIL;
 505         ListCell   *jt;
 506
 507         /*
 508          * Count the number of child jointree nodes.  This is the depth of the
 509          * dynamic-programming algorithm we must employ to consider all ways
 510          * of joining the child nodes.
 511          */
 512         levels_needed = list_length(from->fromlist);
 513
 514         if (levels_needed <= 0)
 515                 return NULL;                    /* nothing to do? */
 516
 517         /*
 518          * Construct a list of rels corresponding to the child jointree nodes.
 519          * This may contain both base rels and rels constructed according to
 520          * explicit JOIN directives.
 521          */
 522         foreach(jt, from->fromlist)
 523         {
 524                 Node       *jtnode = (Node *) lfirst(jt);
 525
 526                 initial_rels = lappend(initial_rels,
 527                                                            make_jointree_rel(root, jtnode));
 528         }
 529
 530         if (levels_needed == 1)
 531         {
 532                 /*
 533                  * Single jointree node, so we're done.
 534                  */
 535                 return (RelOptInfo *) linitial(initial_rels);
 536         }
 537         else
 538         {
 539                 /*
 540                  * Consider the different orders in which we could join the rels,
 541                  * using either GEQO or regular optimizer.
 542                  */
 543                 if (enable_geqo && levels_needed >= geqo_threshold)
 544                         return geqo(root, levels_needed, initial_rels);
 545                 else
 546                         return make_one_rel_by_joins(root, levels_needed, initial_rels);
 547         }
 548 }
 549
 550 /*
 551  * make_one_rel_by_joins
 552  *        Find all possible joinpaths for a query by successively finding ways
 553  *        to join component relations into join relations.
 554  *
 555  * 'levels_needed' is the number of iterations needed, ie, the number of
 556  *              independent jointree items in the query.  This is > 1.
 557  *
 558  * 'initial_rels' is a list of RelOptInfo nodes for each independent
 559  *              jointree item.  These are the components to be joined together.
 560  *
 561  * Returns the final level of join relations, i.e., the relation that is
 562  * the result of joining all the original relations together.
 563  */
 564 static RelOptInfo *
 565 make_one_rel_by_joins(PlannerInfo *root, int levels_needed, List *initial_rels)
 566 {
 567         List      **joinitems;
 568         int                     lev;
 569         RelOptInfo *rel;
 570
 571         /*
 572          * We employ a simple "dynamic programming" algorithm: we first find
 573          * all ways to build joins of two jointree items, then all ways to
 574          * build joins of three items (from two-item joins and single items),
 575          * then four-item joins, and so on until we have considered all ways
 576          * to join all the items into one rel.
 577          *
 578          * joinitems[j] is a list of all the j-item rels.  Initially we set
 579          * joinitems[1] to represent all the single-jointree-item relations.
 580          */
 581         joinitems = (List **) palloc0((levels_needed + 1) * sizeof(List *));
 582
 583         joinitems[1] = initial_rels;
 584
 585         for (lev = 2; lev <= levels_needed; lev++)
 586         {
 587                 ListCell   *x;
 588
 589                 /*
 590                  * Determine all possible pairs of relations to be joined at this
 591                  * level, and build paths for making each one from every available
 592                  * pair of lower-level relations.
 593                  */
 594                 joinitems[lev] = make_rels_by_joins(root, lev, joinitems);
 595
 596                 /*
 597                  * Do cleanup work on each just-processed rel.
 598                  */
 599                 foreach(x, joinitems[lev])
 600                 {
 601                         rel = (RelOptInfo *) lfirst(x);
 602
 603                         /* Find and save the cheapest paths for this rel */
 604                         set_cheapest(rel);
 605
 606 #ifdef OPTIMIZER_DEBUG
 607                         debug_print_rel(root, rel);
 608 #endif
 609                 }
 610         }
 611
 612         /*
 613          * We should have a single rel at the final level.
 614          */
 615         if (joinitems[levels_needed] == NIL)
 616                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
 617         Assert(list_length(joinitems[levels_needed]) == 1);
 618
 619         rel = (RelOptInfo *) linitial(joinitems[levels_needed]);
 620
 621         return rel;
 622 }
 623
 624 /*****************************************************************************
 625  *                      PUSHING QUALS DOWN INTO SUBQUERIES
 626  *****************************************************************************/
 627
 628 /*
 629  * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
 630  *
 631  * subquery is the particular component query being checked.  topquery
 632  * is the top component of a set-operations tree (the same Query if no
 633  * set-op is involved).
 634  *
 635  * Conditions checked here:
 636  *
 637  * 1. If the subquery has a LIMIT clause, we must not push down any quals,
 638  * since that could change the set of rows returned.
 639  *
 640  * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
 641  * quals into it, because that would change the results.
 642  *
 643  * 3. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
 644  * push quals into each component query, but the quals can only reference
 645  * subquery columns that suffer no type coercions in the set operation.
 646  * Otherwise there are possible semantic gotchas.  So, we check the
 647  * component queries to see if any of them have different output types;
 648  * differentTypes[k] is set true if column k has different type in any
 649  * component.
 650  */
 651 static bool
 652 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
 653                                                   bool *differentTypes)
 654 {
 655         SetOperationStmt *topop;
 656
 657         /* Check point 1 */
 658         if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
 659                 return false;
 660
 661         /* Are we at top level, or looking at a setop component? */
 662         if (subquery == topquery)
 663         {
 664                 /* Top level, so check any component queries */
 665                 if (subquery->setOperations != NULL)
 666                         if (!recurse_pushdown_safe(subquery->setOperations, topquery,
 667                                                                            differentTypes))
 668                                 return false;
 669         }
 670         else
 671         {
 672                 /* Setop component must not have more components (too weird) */
 673                 if (subquery->setOperations != NULL)
 674                         return false;
 675                 /* Check whether setop component output types match top level */
 676                 topop = (SetOperationStmt *) topquery->setOperations;
 677                 Assert(topop && IsA(topop, SetOperationStmt));
 678                 compare_tlist_datatypes(subquery->targetList,
 679                                                                 topop->colTypes,
 680                                                                 differentTypes);
 681         }
 682         return true;
 683 }
 684
 685 /*
 686  * Helper routine to recurse through setOperations tree
 687  */
 688 static bool
 689 recurse_pushdown_safe(Node *setOp, Query *topquery,
 690                                           bool *differentTypes)
 691 {
 692         if (IsA(setOp, RangeTblRef))
 693         {
 694                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 695                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
 696                 Query      *subquery = rte->subquery;
 697
 698                 Assert(subquery != NULL);
 699                 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
 700         }
 701         else if (IsA(setOp, SetOperationStmt))
 702         {
 703                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 704
 705                 /* EXCEPT is no good */
 706                 if (op->op == SETOP_EXCEPT)
 707                         return false;
 708                 /* Else recurse */
 709                 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
 710                         return false;
 711                 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
 712                         return false;
 713         }
 714         else
 715         {
 716                 elog(ERROR, "unrecognized node type: %d",
 717                          (int) nodeTag(setOp));
 718         }
 719         return true;
 720 }
 721
 722 /*
 723  * Compare tlist's datatypes against the list of set-operation result types.
 724  * For any items that are different, mark the appropriate element of
 725  * differentTypes[] to show that this column will have type conversions.
 726  */
 727 static void
 728 compare_tlist_datatypes(List *tlist, List *colTypes,
 729                                                 bool *differentTypes)
 730 {
 731         ListCell   *l;
 732         ListCell   *colType = list_head(colTypes);
 733
 734         foreach(l, tlist)
 735         {
 736                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 737
 738                 if (tle->resjunk)
 739                         continue;                       /* ignore resjunk columns */
 740                 if (colType == NULL)
 741                         elog(ERROR, "wrong number of tlist entries");
 742                 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
 743                         differentTypes[tle->resno] = true;
 744                 colType = lnext(colType);
 745         }
 746         if (colType != NULL)
 747                 elog(ERROR, "wrong number of tlist entries");
 748 }
 749
 750 /*
 751  * qual_is_pushdown_safe - is a particular qual safe to push down?
 752  *
 753  * qual is a restriction clause applying to the given subquery (whose RTE
 754  * has index rti in the parent query).
 755  *
 756  * Conditions checked here:
 757  *
 758  * 1. The qual must not contain any subselects (mainly because I'm not sure
 759  * it will work correctly: sublinks will already have been transformed into
 760  * subplans in the qual, but not in the subquery).
 761  *
 762  * 2. The qual must not refer to any subquery output columns that were
 763  * found to have inconsistent types across a set operation tree by
 764  * subquery_is_pushdown_safe().
 765  *
 766  * 3. If the subquery uses DISTINCT ON, we must not push down any quals that
 767  * refer to non-DISTINCT output columns, because that could change the set
 768  * of rows returned.  This condition is vacuous for DISTINCT, because then
 769  * there are no non-DISTINCT output columns, but unfortunately it's fairly
 770  * expensive to tell the difference between DISTINCT and DISTINCT ON in the
 771  * parsetree representation.  It's cheaper to just make sure all the Vars
 772  * in the qual refer to DISTINCT columns.
 773  *
 774  * 4. We must not push down any quals that refer to subselect outputs that
 775  * return sets, else we'd introduce functions-returning-sets into the
 776  * subquery's WHERE/HAVING quals.
 777  */
 778 static bool
 779 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
 780                                           bool *differentTypes)
 781 {
 782         bool            safe = true;
 783         List       *vars;
 784         ListCell   *vl;
 785         Bitmapset  *tested = NULL;
 786
 787         /* Refuse subselects (point 1) */
 788         if (contain_subplans(qual))
 789                 return false;
 790
 791         /*
 792          * Examine all Vars used in clause; since it's a restriction clause,
 793          * all such Vars must refer to subselect output columns.
 794          */
 795         vars = pull_var_clause(qual, false);
 796         foreach(vl, vars)
 797         {
 798                 Var                *var = (Var *) lfirst(vl);
 799                 TargetEntry *tle;
 800
 801                 Assert(var->varno == rti);
 802
 803                 /*
 804                  * We use a bitmapset to avoid testing the same attno more than
 805                  * once.  (NB: this only works because subquery outputs can't have
 806                  * negative attnos.)
 807                  */
 808                 if (bms_is_member(var->varattno, tested))
 809                         continue;
 810                 tested = bms_add_member(tested, var->varattno);
 811
 812                 /* Check point 2 */
 813                 if (differentTypes[var->varattno])
 814                 {
 815                         safe = false;
 816                         break;
 817                 }
 818
 819                 /* Must find the tlist element referenced by the Var */
 820                 tle = get_tle_by_resno(subquery->targetList, var->varattno);
 821                 Assert(tle != NULL);
 822                 Assert(!tle->resjunk);
 823
 824                 /* If subquery uses DISTINCT or DISTINCT ON, check point 3 */
 825                 if (subquery->distinctClause != NIL &&
 826                         !targetIsInSortList(tle, subquery->distinctClause))
 827                 {
 828                         /* non-DISTINCT column, so fail */
 829                         safe = false;
 830                         break;
 831                 }
 832
 833                 /* Refuse functions returning sets (point 4) */
 834                 if (expression_returns_set((Node *) tle->expr))
 835                 {
 836                         safe = false;
 837                         break;
 838                 }
 839         }
 840
 841         list_free(vars);
 842         bms_free(tested);
 843
 844         return safe;
 845 }
 846
 847 /*
 848  * subquery_push_qual - push down a qual that we have determined is safe
 849  */
 850 static void
 851 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
 852 {
 853         if (subquery->setOperations != NULL)
 854         {
 855                 /* Recurse to push it separately to each component query */
 856                 recurse_push_qual(subquery->setOperations, subquery,
 857                                                   rte, rti, qual);
 858         }
 859         else
 860         {
 861                 /*
 862                  * We need to replace Vars in the qual (which must refer to
 863                  * outputs of the subquery) with copies of the subquery's
 864                  * targetlist expressions.      Note that at this point, any uplevel
 865                  * Vars in the qual should have been replaced with Params, so they
 866                  * need no work.
 867                  *
 868                  * This step also ensures that when we are pushing into a setop tree,
 869                  * each component query gets its own copy of the qual.
 870                  */
 871                 qual = ResolveNew(qual, rti, 0, rte,
 872                                                   subquery->targetList,
 873                                                   CMD_SELECT, 0);
 874
 875                 /*
 876                  * Now attach the qual to the proper place: normally WHERE, but
 877                  * if the subquery uses grouping or aggregation, put it in HAVING
 878                  * (since the qual really refers to the group-result rows).
 879                  */
 880                 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
 881                         subquery->havingQual = make_and_qual(subquery->havingQual, qual);
 882                 else
 883                         subquery->jointree->quals =
 884                                 make_and_qual(subquery->jointree->quals, qual);
 885
 886                 /*
 887                  * We need not change the subquery's hasAggs or hasSublinks flags,
 888                  * since we can't be pushing down any aggregates that weren't
 889                  * there before, and we don't push down subselects at all.
 890                  */
 891         }
 892 }
 893
 894 /*
 895  * Helper routine to recurse through setOperations tree
 896  */
 897 static void
 898 recurse_push_qual(Node *setOp, Query *topquery,
 899                                   RangeTblEntry *rte, Index rti, Node *qual)
 900 {
 901         if (IsA(setOp, RangeTblRef))
 902         {
 903                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 904                 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
 905                 Query      *subquery = subrte->subquery;
 906
 907                 Assert(subquery != NULL);
 908                 subquery_push_qual(subquery, rte, rti, qual);
 909         }
 910         else if (IsA(setOp, SetOperationStmt))
 911         {
 912                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 913
 914                 recurse_push_qual(op->larg, topquery, rte, rti, qual);
 915                 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
 916         }
 917         else
 918         {
 919                 elog(ERROR, "unrecognized node type: %d",
 920                          (int) nodeTag(setOp));
 921         }
 922 }
 923
 924 /*****************************************************************************
 925  *                      DEBUG SUPPORT
 926  *****************************************************************************/
 927
 928 #ifdef OPTIMIZER_DEBUG
 929
 930 static void
 931 print_relids(Relids relids)
 932 {
 933         Relids          tmprelids;
 934         int                     x;
 935         bool            first = true;
 936
 937         tmprelids = bms_copy(relids);
 938         while ((x = bms_first_member(tmprelids)) >= 0)
 939         {
 940                 if (!first)
 941                         printf(" ");
 942                 printf("%d", x);
 943                 first = false;
 944         }
 945         bms_free(tmprelids);
 946 }
 947
 948 static void
 949 print_restrictclauses(PlannerInfo *root, List *clauses)
 950 {
 951         ListCell   *l;
 952
 953         foreach(l, clauses)
 954         {
 955                 RestrictInfo *c = lfirst(l);
 956
 957                 print_expr((Node *) c->clause, root->parse->rtable);
 958                 if (lnext(l))
 959                         printf(", ");
 960         }
 961 }
 962
 963 static void
 964 print_path(PlannerInfo *root, Path *path, int indent)
 965 {
 966         const char *ptype;
 967         bool            join = false;
 968         Path       *subpath = NULL;
 969         int                     i;
 970
 971         switch (nodeTag(path))
 972         {
 973                 case T_Path:
 974                         ptype = "SeqScan";
 975                         break;
 976                 case T_IndexPath:
 977                         ptype = "IdxScan";
 978                         break;
 979                 case T_BitmapHeapPath:
 980                         ptype = "BitmapHeapScan";
 981                         break;
 982                 case T_BitmapAndPath:
 983                         ptype = "BitmapAndPath";
 984                         break;
 985                 case T_BitmapOrPath:
 986                         ptype = "BitmapOrPath";
 987                         break;
 988                 case T_TidPath:
 989                         ptype = "TidScan";
 990                         break;
 991                 case T_AppendPath:
 992                         ptype = "Append";
 993                         break;
 994                 case T_ResultPath:
 995                         ptype = "Result";
 996                         subpath = ((ResultPath *) path)->subpath;
 997                         break;
 998                 case T_MaterialPath:
 999                         ptype = "Material";
1000                         subpath = ((MaterialPath *) path)->subpath;
1001                         break;
1002                 case T_UniquePath:
1003                         ptype = "Unique";
1004                         subpath = ((UniquePath *) path)->subpath;
1005                         break;
1006                 case T_NestPath:
1007                         ptype = "NestLoop";
1008                         join = true;
1009                         break;
1010                 case T_MergePath:
1011                         ptype = "MergeJoin";
1012                         join = true;
1013                         break;
1014                 case T_HashPath:
1015                         ptype = "HashJoin";
1016                         join = true;
1017                         break;
1018                 default:
1019                         ptype = "???Path";
1020                         break;
1021         }
1022
1023         for (i = 0; i < indent; i++)
1024                 printf("\t");
1025         printf("%s", ptype);
1026
1027         if (path->parent)
1028         {
1029                 printf("(");
1030                 print_relids(path->parent->relids);
1031                 printf(") rows=%.0f", path->parent->rows);
1032         }
1033         printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
1034
1035         if (path->pathkeys)
1036         {
1037                 for (i = 0; i < indent; i++)
1038                         printf("\t");
1039                 printf("  pathkeys: ");
1040                 print_pathkeys(path->pathkeys, root->parse->rtable);
1041         }
1042
1043         if (join)
1044         {
1045                 JoinPath   *jp = (JoinPath *) path;
1046
1047                 for (i = 0; i < indent; i++)
1048                         printf("\t");
1049                 printf("  clauses: ");
1050                 print_restrictclauses(root, jp->joinrestrictinfo);
1051                 printf("\n");
1052
1053                 if (IsA(path, MergePath))
1054                 {
1055                         MergePath  *mp = (MergePath *) path;
1056
1057                         if (mp->outersortkeys || mp->innersortkeys)
1058                         {
1059                                 for (i = 0; i < indent; i++)
1060                                         printf("\t");
1061                                 printf("  sortouter=%d sortinner=%d\n",
1062                                            ((mp->outersortkeys) ? 1 : 0),
1063                                            ((mp->innersortkeys) ? 1 : 0));
1064                         }
1065                 }
1066
1067                 print_path(root, jp->outerjoinpath, indent + 1);
1068                 print_path(root, jp->innerjoinpath, indent + 1);
1069         }
1070
1071         if (subpath)
1072                 print_path(root, subpath, indent + 1);
1073 }
1074
1075 void
1076 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1077 {
1078         ListCell   *l;
1079
1080         printf("RELOPTINFO (");
1081         print_relids(rel->relids);
1082         printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1083
1084         if (rel->baserestrictinfo)
1085         {
1086                 printf("\tbaserestrictinfo: ");
1087                 print_restrictclauses(root, rel->baserestrictinfo);
1088                 printf("\n");
1089         }
1090
1091         if (rel->joininfo)
1092         {
1093                 printf("\tjoininfo: ");
1094                 print_restrictclauses(root, rel->joininfo);
1095                 printf("\n");
1096         }
1097
1098         printf("\tpath list:\n");
1099         foreach(l, rel->pathlist)
1100                 print_path(root, lfirst(l), 1);
1101         printf("\n\tcheapest startup path:\n");
1102         print_path(root, rel->cheapest_startup_path, 1);
1103         printf("\n\tcheapest total path:\n");
1104         print_path(root, rel->cheapest_total_path, 1);
1105         printf("\n");
1106         fflush(stdout);
1107 }
1108
1109 #endif   /* OPTIMIZER_DEBUG */