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-2011, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/optimizer/path/allpaths.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include <math.h>
  19
  20 #include "catalog/pg_class.h"
  21 #include "nodes/nodeFuncs.h"
  22 #ifdef OPTIMIZER_DEBUG
  23 #include "nodes/print.h"
  24 #endif
  25 #include "optimizer/clauses.h"
  26 #include "optimizer/cost.h"
  27 #include "optimizer/geqo.h"
  28 #include "optimizer/pathnode.h"
  29 #include "optimizer/paths.h"
  30 #include "optimizer/plancat.h"
  31 #include "optimizer/planner.h"
  32 #include "optimizer/prep.h"
  33 #include "optimizer/restrictinfo.h"
  34 #include "optimizer/var.h"
  35 #include "parser/parse_clause.h"
  36 #include "parser/parsetree.h"
  37 #include "rewrite/rewriteManip.h"
  38 #include "utils/lsyscache.h"
  39
  40
  41 /* These parameters are set by GUC */
  42 bool            enable_geqo = false;    /* just in case GUC doesn't set it */
  43 int                     geqo_threshold;
  44
  45 /* Hook for plugins to replace standard_join_search() */
  46 join_search_hook_type join_search_hook = NULL;
  47
  48
  49 static void set_base_rel_pathlists(PlannerInfo *root);
  50 static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  51                                  Index rti, RangeTblEntry *rte);
  52 static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  53                                            RangeTblEntry *rte);
  54 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  55                                                 Index rti, RangeTblEntry *rte);
  56 static List *accumulate_append_subpath(List *subpaths, Path *path);
  57 static void set_dummy_rel_pathlist(RelOptInfo *rel);
  58 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
  59                                           Index rti, RangeTblEntry *rte);
  60 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
  61                                           RangeTblEntry *rte);
  62 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
  63                                         RangeTblEntry *rte);
  64 static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel,
  65                                  RangeTblEntry *rte);
  66 static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel,
  67                                            RangeTblEntry *rte);
  68 static void set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel,
  69                                            RangeTblEntry *rte);
  70 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
  71 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
  72                                                   bool *differentTypes);
  73 static bool recurse_pushdown_safe(Node *setOp, Query *topquery,
  74                                           bool *differentTypes);
  75 static void compare_tlist_datatypes(List *tlist, List *colTypes,
  76                                                 bool *differentTypes);
  77 static bool qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
  78                                           bool *differentTypes);
  79 static void subquery_push_qual(Query *subquery,
  80                                    RangeTblEntry *rte, Index rti, Node *qual);
  81 static void recurse_push_qual(Node *setOp, Query *topquery,
  82                                   RangeTblEntry *rte, Index rti, Node *qual);
  83
  84
  85 /*
  86  * make_one_rel
  87  *        Finds all possible access paths for executing a query, returning a
  88  *        single rel that represents the join of all base rels in the query.
  89  */
  90 RelOptInfo *
  91 make_one_rel(PlannerInfo *root, List *joinlist)
  92 {
  93         RelOptInfo *rel;
  94
  95         /*
  96          * Generate access paths for the base rels.
  97          */
  98         set_base_rel_pathlists(root);
  99
 100         /*
 101          * Generate access paths for the entire join tree.
 102          */
 103         rel = make_rel_from_joinlist(root, joinlist);
 104
 105         /*
 106          * The result should join all and only the query's base rels.
 107          */
 108 #ifdef USE_ASSERT_CHECKING
 109         {
 110                 int                     num_base_rels = 0;
 111                 Index           rti;
 112
 113                 for (rti = 1; rti < root->simple_rel_array_size; rti++)
 114                 {
 115                         RelOptInfo *brel = root->simple_rel_array[rti];
 116
 117                         if (brel == NULL)
 118                                 continue;
 119
 120                         Assert(brel->relid == rti); /* sanity check on array */
 121
 122                         /* ignore RTEs that are "other rels" */
 123                         if (brel->reloptkind != RELOPT_BASEREL)
 124                                 continue;
 125
 126                         Assert(bms_is_member(rti, rel->relids));
 127                         num_base_rels++;
 128                 }
 129
 130                 Assert(bms_num_members(rel->relids) == num_base_rels);
 131         }
 132 #endif
 133
 134         return rel;
 135 }
 136
 137 /*
 138  * set_base_rel_pathlists
 139  *        Finds all paths available for scanning each base-relation entry.
 140  *        Sequential scan and any available indices are considered.
 141  *        Each useful path is attached to its relation's 'pathlist' field.
 142  */
 143 static void
 144 set_base_rel_pathlists(PlannerInfo *root)
 145 {
 146         Index           rti;
 147
 148         for (rti = 1; rti < root->simple_rel_array_size; rti++)
 149         {
 150                 RelOptInfo *rel = root->simple_rel_array[rti];
 151
 152                 /* there may be empty slots corresponding to non-baserel RTEs */
 153                 if (rel == NULL)
 154                         continue;
 155
 156                 Assert(rel->relid == rti);              /* sanity check on array */
 157
 158                 /* ignore RTEs that are "other rels" */
 159                 if (rel->reloptkind != RELOPT_BASEREL)
 160                         continue;
 161
 162                 set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
 163         }
 164 }
 165
 166 /*
 167  * set_rel_pathlist
 168  *        Build access paths for a base relation
 169  */
 170 static void
 171 set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 172                                  Index rti, RangeTblEntry *rte)
 173 {
 174         if (rte->inh)
 175         {
 176                 /* It's an "append relation", process accordingly */
 177                 set_append_rel_pathlist(root, rel, rti, rte);
 178         }
 179         else if (rel->rtekind == RTE_SUBQUERY)
 180         {
 181                 /* Subquery --- generate a separate plan for it */
 182                 set_subquery_pathlist(root, rel, rti, rte);
 183         }
 184         else if (rel->rtekind == RTE_FUNCTION)
 185         {
 186                 /* RangeFunction --- generate a suitable path for it */
 187                 set_function_pathlist(root, rel, rte);
 188         }
 189         else if (rel->rtekind == RTE_VALUES)
 190         {
 191                 /* Values list --- generate a suitable path for it */
 192                 set_values_pathlist(root, rel, rte);
 193         }
 194         else if (rel->rtekind == RTE_CTE)
 195         {
 196                 /* CTE reference --- generate a suitable path for it */
 197                 if (rte->self_reference)
 198                         set_worktable_pathlist(root, rel, rte);
 199                 else
 200                         set_cte_pathlist(root, rel, rte);
 201         }
 202         else
 203         {
 204                 Assert(rel->rtekind == RTE_RELATION);
 205                 if (get_rel_relkind(rte->relid) == RELKIND_FOREIGN_TABLE)
 206                 {
 207                         /* Foreign table */
 208                         set_foreign_pathlist(root, rel, rte);
 209                 }
 210                 else
 211                 {
 212                         /* Plain relation */
 213                         set_plain_rel_pathlist(root, rel, rte);
 214                 }
 215         }
 216
 217 #ifdef OPTIMIZER_DEBUG
 218         debug_print_rel(root, rel);
 219 #endif
 220 }
 221
 222 /*
 223  * set_plain_rel_pathlist
 224  *        Build access paths for a plain relation (no subquery, no inheritance)
 225  */
 226 static void
 227 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 228 {
 229         /*
 230          * If we can prove we don't need to scan the rel via constraint exclusion,
 231          * set up a single dummy path for it.  We only need to check for regular
 232          * baserels; if it's an otherrel, CE was already checked in
 233          * set_append_rel_pathlist().
 234          */
 235         if (rel->reloptkind == RELOPT_BASEREL &&
 236                 relation_excluded_by_constraints(root, rel, rte))
 237         {
 238                 set_dummy_rel_pathlist(rel);
 239                 return;
 240         }
 241
 242         /*
 243          * Test any partial indexes of rel for applicability.  We must do this
 244          * first since partial unique indexes can affect size estimates.
 245          */
 246         check_partial_indexes(root, rel);
 247
 248         /* Mark rel with estimated output rows, width, etc */
 249         set_baserel_size_estimates(root, rel);
 250
 251         /*
 252          * Check to see if we can extract any restriction conditions from join
 253          * quals that are OR-of-AND structures.  If so, add them to the rel's
 254          * restriction list, and redo the above steps.
 255          */
 256         if (create_or_index_quals(root, rel))
 257         {
 258                 check_partial_indexes(root, rel);
 259                 set_baserel_size_estimates(root, rel);
 260         }
 261
 262         /*
 263          * Generate paths and add them to the rel's pathlist.
 264          *
 265          * Note: add_path() will discard any paths that are dominated by another
 266          * available path, keeping only those paths that are superior along at
 267          * least one dimension of cost or sortedness.
 268          */
 269
 270         /* Consider sequential scan */
 271         add_path(rel, create_seqscan_path(root, rel));
 272
 273         /* Consider index scans */
 274         create_index_paths(root, rel);
 275
 276         /* Consider TID scans */
 277         create_tidscan_paths(root, rel);
 278
 279         /* Now find the cheapest of the paths for this rel */
 280         set_cheapest(rel);
 281 }
 282
 283 /*
 284  * set_append_rel_pathlist
 285  *        Build access paths for an "append relation"
 286  *
 287  * The passed-in rel and RTE represent the entire append relation.      The
 288  * relation's contents are computed by appending together the output of
 289  * the individual member relations.  Note that in the inheritance case,
 290  * the first member relation is actually the same table as is mentioned in
 291  * the parent RTE ... but it has a different RTE and RelOptInfo.  This is
 292  * a good thing because their outputs are not the same size.
 293  */
 294 static void
 295 set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 296                                                 Index rti, RangeTblEntry *rte)
 297 {
 298         int                     parentRTindex = rti;
 299         List       *live_childrels = NIL;
 300         List       *subpaths = NIL;
 301         List       *all_child_pathkeys = NIL;
 302         double          parent_rows;
 303         double          parent_size;
 304         double     *parent_attrsizes;
 305         int                     nattrs;
 306         ListCell   *l;
 307
 308         /*
 309          * Initialize to compute size estimates for whole append relation.
 310          *
 311          * We handle width estimates by weighting the widths of different child
 312          * rels proportionally to their number of rows.  This is sensible because
 313          * the use of width estimates is mainly to compute the total relation
 314          * "footprint" if we have to sort or hash it.  To do this, we sum the
 315          * total equivalent size (in "double" arithmetic) and then divide by the
 316          * total rowcount estimate.  This is done separately for the total rel
 317          * width and each attribute.
 318          *
 319          * Note: if you consider changing this logic, beware that child rels could
 320          * have zero rows and/or width, if they were excluded by constraints.
 321          */
 322         parent_rows = 0;
 323         parent_size = 0;
 324         nattrs = rel->max_attr - rel->min_attr + 1;
 325         parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
 326
 327         /*
 328          * Generate access paths for each member relation, and pick the cheapest
 329          * path for each one.
 330          */
 331         foreach(l, root->append_rel_list)
 332         {
 333                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
 334                 int                     childRTindex;
 335                 RangeTblEntry *childRTE;
 336                 RelOptInfo *childrel;
 337                 List       *childquals;
 338                 Node       *childqual;
 339                 ListCell   *lcp;
 340                 ListCell   *parentvars;
 341                 ListCell   *childvars;
 342
 343                 /* append_rel_list contains all append rels; ignore others */
 344                 if (appinfo->parent_relid != parentRTindex)
 345                         continue;
 346
 347                 childRTindex = appinfo->child_relid;
 348                 childRTE = root->simple_rte_array[childRTindex];
 349
 350                 /*
 351                  * The child rel's RelOptInfo was already created during
 352                  * add_base_rels_to_query.
 353                  */
 354                 childrel = find_base_rel(root, childRTindex);
 355                 Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
 356
 357                 /*
 358                  * We have to copy the parent's targetlist and quals to the child,
 359                  * with appropriate substitution of variables.  However, only the
 360                  * baserestrictinfo quals are needed before we can check for
 361                  * constraint exclusion; so do that first and then check to see if we
 362                  * can disregard this child.
 363                  *
 364                  * As of 8.4, the child rel's targetlist might contain non-Var
 365                  * expressions, which means that substitution into the quals could
 366                  * produce opportunities for const-simplification, and perhaps even
 367                  * pseudoconstant quals.  To deal with this, we strip the RestrictInfo
 368                  * nodes, do the substitution, do const-simplification, and then
 369                  * reconstitute the RestrictInfo layer.
 370                  */
 371                 childquals = get_all_actual_clauses(rel->baserestrictinfo);
 372                 childquals = (List *) adjust_appendrel_attrs((Node *) childquals,
 373                                                                                                          appinfo);
 374                 childqual = eval_const_expressions(root, (Node *)
 375                                                                                    make_ands_explicit(childquals));
 376                 if (childqual && IsA(childqual, Const) &&
 377                         (((Const *) childqual)->constisnull ||
 378                          !DatumGetBool(((Const *) childqual)->constvalue)))
 379                 {
 380                         /*
 381                          * Restriction reduces to constant FALSE or constant NULL after
 382                          * substitution, so this child need not be scanned.
 383                          */
 384                         set_dummy_rel_pathlist(childrel);
 385                         continue;
 386                 }
 387                 childquals = make_ands_implicit((Expr *) childqual);
 388                 childquals = make_restrictinfos_from_actual_clauses(root,
 389                                                                                                                         childquals);
 390                 childrel->baserestrictinfo = childquals;
 391
 392                 if (relation_excluded_by_constraints(root, childrel, childRTE))
 393                 {
 394                         /*
 395                          * This child need not be scanned, so we can omit it from the
 396                          * appendrel.  Mark it with a dummy cheapest-path though, in case
 397                          * best_appendrel_indexscan() looks at it later.
 398                          */
 399                         set_dummy_rel_pathlist(childrel);
 400                         continue;
 401                 }
 402
 403                 /* CE failed, so finish copying targetlist and join quals */
 404                 childrel->joininfo = (List *)
 405                         adjust_appendrel_attrs((Node *) rel->joininfo,
 406                                                                    appinfo);
 407                 childrel->reltargetlist = (List *)
 408                         adjust_appendrel_attrs((Node *) rel->reltargetlist,
 409                                                                    appinfo);
 410
 411                 /*
 412                  * We have to make child entries in the EquivalenceClass data
 413                  * structures as well.  This is needed either if the parent
 414                  * participates in some eclass joins (because we will want to
 415                  * consider inner-indexscan joins on the individual children)
 416                  * or if the parent has useful pathkeys (because we should try
 417                  * to build MergeAppend paths that produce those sort orderings).
 418                  */
 419                 if (rel->has_eclass_joins || has_useful_pathkeys(root, rel))
 420                         add_child_rel_equivalences(root, appinfo, rel, childrel);
 421                 childrel->has_eclass_joins = rel->has_eclass_joins;
 422
 423                 /*
 424                  * Note: we could compute appropriate attr_needed data for the child's
 425                  * variables, by transforming the parent's attr_needed through the
 426                  * translated_vars mapping.  However, currently there's no need
 427                  * because attr_needed is only examined for base relations not
 428                  * otherrels.  So we just leave the child's attr_needed empty.
 429                  */
 430
 431                 /* Remember which childrels are live, for MergeAppend logic below */
 432                 live_childrels = lappend(live_childrels, childrel);
 433
 434                 /*
 435                  * Compute the child's access paths, and add the cheapest one to the
 436                  * Append path we are constructing for the parent.
 437                  */
 438                 set_rel_pathlist(root, childrel, childRTindex, childRTE);
 439
 440                 subpaths = accumulate_append_subpath(subpaths,
 441                                                                                          childrel->cheapest_total_path);
 442
 443                 /*
 444                  * Collect a list of all the available path orderings for all the
 445                  * children.  We use this as a heuristic to indicate which sort
 446                  * orderings we should build MergeAppend paths for.
 447                  */
 448                 foreach(lcp, childrel->pathlist)
 449                 {
 450                         Path       *childpath = (Path *) lfirst(lcp);
 451                         List       *childkeys = childpath->pathkeys;
 452                         ListCell   *lpk;
 453                         bool            found = false;
 454
 455                         /* Ignore unsorted paths */
 456                         if (childkeys == NIL)
 457                                 continue;
 458
 459                         /* Have we already seen this ordering? */
 460                         foreach(lpk, all_child_pathkeys)
 461                         {
 462                                 List   *existing_pathkeys = (List *) lfirst(lpk);
 463
 464                                 if (compare_pathkeys(existing_pathkeys,
 465                                                                          childkeys) == PATHKEYS_EQUAL)
 466                                 {
 467                                         found = true;
 468                                         break;
 469                                 }
 470                         }
 471                         if (!found)
 472                         {
 473                                 /* No, so add it to all_child_pathkeys */
 474                                 all_child_pathkeys = lappend(all_child_pathkeys, childkeys);
 475                         }
 476                 }
 477
 478                 /*
 479                  * Accumulate size information from each child.
 480                  */
 481                 if (childrel->rows > 0)
 482                 {
 483                         parent_rows += childrel->rows;
 484                         parent_size += childrel->width * childrel->rows;
 485
 486                         forboth(parentvars, rel->reltargetlist,
 487                                         childvars, childrel->reltargetlist)
 488                         {
 489                                 Var                *parentvar = (Var *) lfirst(parentvars);
 490                                 Var                *childvar = (Var *) lfirst(childvars);
 491
 492                                 /*
 493                                  * Accumulate per-column estimates too.  Whole-row Vars and
 494                                  * PlaceHolderVars can be ignored here.
 495                                  */
 496                                 if (IsA(parentvar, Var) &&
 497                                         IsA(childvar, Var))
 498                                 {
 499                                         int                     pndx = parentvar->varattno - rel->min_attr;
 500                                         int                     cndx = childvar->varattno - childrel->min_attr;
 501
 502                                         parent_attrsizes[pndx] += childrel->attr_widths[cndx] * childrel->rows;
 503                                 }
 504                         }
 505                 }
 506         }
 507
 508         /*
 509          * Save the finished size estimates.
 510          */
 511         rel->rows = parent_rows;
 512         if (parent_rows > 0)
 513         {
 514                 int                     i;
 515
 516                 rel->width = rint(parent_size / parent_rows);
 517                 for (i = 0; i < nattrs; i++)
 518                         rel->attr_widths[i] = rint(parent_attrsizes[i] / parent_rows);
 519         }
 520         else
 521                 rel->width = 0;                 /* attr_widths should be zero already */
 522
 523         /*
 524          * Set "raw tuples" count equal to "rows" for the appendrel; needed
 525          * because some places assume rel->tuples is valid for any baserel.
 526          */
 527         rel->tuples = parent_rows;
 528
 529         pfree(parent_attrsizes);
 530
 531         /*
 532          * Next, build an unordered Append path for the rel.  (Note: this is
 533          * correct even if we have zero or one live subpath due to constraint
 534          * exclusion.)
 535          */
 536         add_path(rel, (Path *) create_append_path(rel, subpaths));
 537
 538         /*
 539          * Next, build MergeAppend paths based on the collected list of child
 540          * pathkeys.  We consider both cheapest-startup and cheapest-total
 541          * cases, ie, for each interesting ordering, collect all the cheapest
 542          * startup subpaths and all the cheapest total paths, and build a
 543          * MergeAppend path for each list.
 544          */
 545         foreach(l, all_child_pathkeys)
 546         {
 547                 List   *pathkeys = (List *) lfirst(l);
 548                 List   *startup_subpaths = NIL;
 549                 List   *total_subpaths = NIL;
 550                 bool    startup_neq_total = false;
 551                 ListCell *lcr;
 552
 553                 /* Select the child paths for this ordering... */
 554                 foreach(lcr, live_childrels)
 555                 {
 556                         RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
 557                         Path       *cheapest_startup,
 558                                            *cheapest_total;
 559
 560                         /* Locate the right paths, if they are available. */
 561                         cheapest_startup =
 562                                 get_cheapest_path_for_pathkeys(childrel->pathlist,
 563                                                                                            pathkeys,
 564                                                                                            STARTUP_COST);
 565                         cheapest_total =
 566                                 get_cheapest_path_for_pathkeys(childrel->pathlist,
 567                                                                                            pathkeys,
 568                                                                                            TOTAL_COST);
 569
 570                         /*
 571                          * If we can't find any paths with the right order just add the
 572                          * cheapest-total path; we'll have to sort it.
 573                          */
 574                         if (cheapest_startup == NULL)
 575                                 cheapest_startup = childrel->cheapest_total_path;
 576                         if (cheapest_total == NULL)
 577                                 cheapest_total = childrel->cheapest_total_path;
 578
 579                         /*
 580                          * Notice whether we actually have different paths for the
 581                          * "cheapest" and "total" cases; frequently there will be no
 582                          * point in two create_merge_append_path() calls.
 583                          */
 584                         if (cheapest_startup != cheapest_total)
 585                                 startup_neq_total = true;
 586
 587                         startup_subpaths =
 588                                 accumulate_append_subpath(startup_subpaths, cheapest_startup);
 589                         total_subpaths =
 590                                 accumulate_append_subpath(total_subpaths, cheapest_total);
 591                 }
 592
 593                 /* ... and build the MergeAppend paths */
 594                 add_path(rel, (Path *) create_merge_append_path(root,
 595                                                                                                                 rel,
 596                                                                                                                 startup_subpaths,
 597                                                                                                                 pathkeys));
 598                 if (startup_neq_total)
 599                         add_path(rel, (Path *) create_merge_append_path(root,
 600                                                                                                                         rel,
 601                                                                                                                         total_subpaths,
 602                                                                                                                         pathkeys));
 603         }
 604
 605         /* Select cheapest path */
 606         set_cheapest(rel);
 607 }
 608
 609 /*
 610  * accumulate_append_subpath
 611  *              Add a subpath to the list being built for an Append or MergeAppend
 612  *
 613  * It's possible that the child is itself an Append path, in which case
 614  * we can "cut out the middleman" and just add its child paths to our
 615  * own list.  (We don't try to do this earlier because we need to
 616  * apply both levels of transformation to the quals.)
 617  */
 618 static List *
 619 accumulate_append_subpath(List *subpaths, Path *path)
 620 {
 621         if (IsA(path, AppendPath))
 622         {
 623                 AppendPath      *apath = (AppendPath *) path;
 624
 625                 /* list_copy is important here to avoid sharing list substructure */
 626                 return list_concat(subpaths, list_copy(apath->subpaths));
 627         }
 628         else
 629                 return lappend(subpaths, path);
 630 }
 631
 632 /*
 633  * set_dummy_rel_pathlist
 634  *        Build a dummy path for a relation that's been excluded by constraints
 635  *
 636  * Rather than inventing a special "dummy" path type, we represent this as an
 637  * AppendPath with no members (see also IS_DUMMY_PATH macro).
 638  */
 639 static void
 640 set_dummy_rel_pathlist(RelOptInfo *rel)
 641 {
 642         /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
 643         rel->rows = 0;
 644         rel->width = 0;
 645
 646         add_path(rel, (Path *) create_append_path(rel, NIL));
 647
 648         /* Select cheapest path (pretty easy in this case...) */
 649         set_cheapest(rel);
 650 }
 651
 652 /* quick-and-dirty test to see if any joining is needed */
 653 static bool
 654 has_multiple_baserels(PlannerInfo *root)
 655 {
 656         int                     num_base_rels = 0;
 657         Index           rti;
 658
 659         for (rti = 1; rti < root->simple_rel_array_size; rti++)
 660         {
 661                 RelOptInfo *brel = root->simple_rel_array[rti];
 662
 663                 if (brel == NULL)
 664                         continue;
 665
 666                 /* ignore RTEs that are "other rels" */
 667                 if (brel->reloptkind == RELOPT_BASEREL)
 668                         if (++num_base_rels > 1)
 669                                 return true;
 670         }
 671         return false;
 672 }
 673
 674 /*
 675  * set_subquery_pathlist
 676  *              Build the (single) access path for a subquery RTE
 677  */
 678 static void
 679 set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 680                                           Index rti, RangeTblEntry *rte)
 681 {
 682         Query      *parse = root->parse;
 683         Query      *subquery = rte->subquery;
 684         bool       *differentTypes;
 685         double          tuple_fraction;
 686         PlannerInfo *subroot;
 687         List       *pathkeys;
 688
 689         /*
 690          * Must copy the Query so that planning doesn't mess up the RTE contents
 691          * (really really need to fix the planner to not scribble on its input,
 692          * someday).
 693          */
 694         subquery = copyObject(subquery);
 695
 696         /* We need a workspace for keeping track of set-op type coercions */
 697         differentTypes = (bool *)
 698                 palloc0((list_length(subquery->targetList) + 1) * sizeof(bool));
 699
 700         /*
 701          * If there are any restriction clauses that have been attached to the
 702          * subquery relation, consider pushing them down to become WHERE or HAVING
 703          * quals of the subquery itself.  This transformation is useful because it
 704          * may allow us to generate a better plan for the subquery than evaluating
 705          * all the subquery output rows and then filtering them.
 706          *
 707          * There are several cases where we cannot push down clauses. Restrictions
 708          * involving the subquery are checked by subquery_is_pushdown_safe().
 709          * Restrictions on individual clauses are checked by
 710          * qual_is_pushdown_safe().  Also, we don't want to push down
 711          * pseudoconstant clauses; better to have the gating node above the
 712          * subquery.
 713          *
 714          * Non-pushed-down clauses will get evaluated as qpquals of the
 715          * SubqueryScan node.
 716          *
 717          * XXX Are there any cases where we want to make a policy decision not to
 718          * push down a pushable qual, because it'd result in a worse plan?
 719          */
 720         if (rel->baserestrictinfo != NIL &&
 721                 subquery_is_pushdown_safe(subquery, subquery, differentTypes))
 722         {
 723                 /* OK to consider pushing down individual quals */
 724                 List       *upperrestrictlist = NIL;
 725                 ListCell   *l;
 726
 727                 foreach(l, rel->baserestrictinfo)
 728                 {
 729                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 730                         Node       *clause = (Node *) rinfo->clause;
 731
 732                         if (!rinfo->pseudoconstant &&
 733                                 qual_is_pushdown_safe(subquery, rti, clause, differentTypes))
 734                         {
 735                                 /* Push it down */
 736                                 subquery_push_qual(subquery, rte, rti, clause);
 737                         }
 738                         else
 739                         {
 740                                 /* Keep it in the upper query */
 741                                 upperrestrictlist = lappend(upperrestrictlist, rinfo);
 742                         }
 743                 }
 744                 rel->baserestrictinfo = upperrestrictlist;
 745         }
 746
 747         pfree(differentTypes);
 748
 749         /*
 750          * We can safely pass the outer tuple_fraction down to the subquery if the
 751          * outer level has no joining, aggregation, or sorting to do. Otherwise
 752          * we'd better tell the subquery to plan for full retrieval. (XXX This
 753          * could probably be made more intelligent ...)
 754          */
 755         if (parse->hasAggs ||
 756                 parse->groupClause ||
 757                 parse->havingQual ||
 758                 parse->distinctClause ||
 759                 parse->sortClause ||
 760                 has_multiple_baserels(root))
 761                 tuple_fraction = 0.0;   /* default case */
 762         else
 763                 tuple_fraction = root->tuple_fraction;
 764
 765         /* Generate the plan for the subquery */
 766         rel->subplan = subquery_planner(root->glob, subquery,
 767                                                                         root,
 768                                                                         false, tuple_fraction,
 769                                                                         &subroot);
 770         rel->subrtable = subroot->parse->rtable;
 771         rel->subrowmark = subroot->rowMarks;
 772
 773         /* Mark rel with estimated output rows, width, etc */
 774         set_subquery_size_estimates(root, rel, subroot);
 775
 776         /* Convert subquery pathkeys to outer representation */
 777         pathkeys = convert_subquery_pathkeys(root, rel, subroot->query_pathkeys);
 778
 779         /* Generate appropriate path */
 780         add_path(rel, create_subqueryscan_path(rel, pathkeys));
 781
 782         /* Select cheapest path (pretty easy in this case...) */
 783         set_cheapest(rel);
 784 }
 785
 786 /*
 787  * set_function_pathlist
 788  *              Build the (single) access path for a function RTE
 789  */
 790 static void
 791 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 792 {
 793         /* Mark rel with estimated output rows, width, etc */
 794         set_function_size_estimates(root, rel);
 795
 796         /* Generate appropriate path */
 797         add_path(rel, create_functionscan_path(root, rel));
 798
 799         /* Select cheapest path (pretty easy in this case...) */
 800         set_cheapest(rel);
 801 }
 802
 803 /*
 804  * set_values_pathlist
 805  *              Build the (single) access path for a VALUES RTE
 806  */
 807 static void
 808 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 809 {
 810         /* Mark rel with estimated output rows, width, etc */
 811         set_values_size_estimates(root, rel);
 812
 813         /* Generate appropriate path */
 814         add_path(rel, create_valuesscan_path(root, rel));
 815
 816         /* Select cheapest path (pretty easy in this case...) */
 817         set_cheapest(rel);
 818 }
 819
 820 /*
 821  * set_cte_pathlist
 822  *              Build the (single) access path for a non-self-reference CTE RTE
 823  */
 824 static void
 825 set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 826 {
 827         Plan       *cteplan;
 828         PlannerInfo *cteroot;
 829         Index           levelsup;
 830         int                     ndx;
 831         ListCell   *lc;
 832         int                     plan_id;
 833
 834         /*
 835          * Find the referenced CTE, and locate the plan previously made for it.
 836          */
 837         levelsup = rte->ctelevelsup;
 838         cteroot = root;
 839         while (levelsup-- > 0)
 840         {
 841                 cteroot = cteroot->parent_root;
 842                 if (!cteroot)                   /* shouldn't happen */
 843                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
 844         }
 845
 846         /*
 847          * Note: cte_plan_ids can be shorter than cteList, if we are still working
 848          * on planning the CTEs (ie, this is a side-reference from another CTE).
 849          * So we mustn't use forboth here.
 850          */
 851         ndx = 0;
 852         foreach(lc, cteroot->parse->cteList)
 853         {
 854                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 855
 856                 if (strcmp(cte->ctename, rte->ctename) == 0)
 857                         break;
 858                 ndx++;
 859         }
 860         if (lc == NULL)                         /* shouldn't happen */
 861                 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
 862         if (ndx >= list_length(cteroot->cte_plan_ids))
 863                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
 864         plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
 865         Assert(plan_id > 0);
 866         cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
 867
 868         /* Mark rel with estimated output rows, width, etc */
 869         set_cte_size_estimates(root, rel, cteplan);
 870
 871         /* Generate appropriate path */
 872         add_path(rel, create_ctescan_path(root, rel));
 873
 874         /* Select cheapest path (pretty easy in this case...) */
 875         set_cheapest(rel);
 876 }
 877
 878 /*
 879  * set_worktable_pathlist
 880  *              Build the (single) access path for a self-reference CTE RTE
 881  */
 882 static void
 883 set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 884 {
 885         Plan       *cteplan;
 886         PlannerInfo *cteroot;
 887         Index           levelsup;
 888
 889         /*
 890          * We need to find the non-recursive term's plan, which is in the plan
 891          * level that's processing the recursive UNION, which is one level *below*
 892          * where the CTE comes from.
 893          */
 894         levelsup = rte->ctelevelsup;
 895         if (levelsup == 0)                      /* shouldn't happen */
 896                 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
 897         levelsup--;
 898         cteroot = root;
 899         while (levelsup-- > 0)
 900         {
 901                 cteroot = cteroot->parent_root;
 902                 if (!cteroot)                   /* shouldn't happen */
 903                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
 904         }
 905         cteplan = cteroot->non_recursive_plan;
 906         if (!cteplan)                           /* shouldn't happen */
 907                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
 908
 909         /* Mark rel with estimated output rows, width, etc */
 910         set_cte_size_estimates(root, rel, cteplan);
 911
 912         /* Generate appropriate path */
 913         add_path(rel, create_worktablescan_path(root, rel));
 914
 915         /* Select cheapest path (pretty easy in this case...) */
 916         set_cheapest(rel);
 917 }
 918
 919 /*
 920  * set_foreign_pathlist
 921  *              Build the (single) access path for a foreign table RTE
 922  */
 923 static void
 924 set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 925 {
 926         /* Mark rel with estimated output rows, width, etc */
 927         set_foreign_size_estimates(root, rel);
 928
 929         /* Generate appropriate path */
 930         add_path(rel, (Path *) create_foreignscan_path(root, rel));
 931
 932         /* Select cheapest path (pretty easy in this case...) */
 933         set_cheapest(rel);
 934 }
 935
 936 /*
 937  * make_rel_from_joinlist
 938  *        Build access paths using a "joinlist" to guide the join path search.
 939  *
 940  * See comments for deconstruct_jointree() for definition of the joinlist
 941  * data structure.
 942  */
 943 static RelOptInfo *
 944 make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
 945 {
 946         int                     levels_needed;
 947         List       *initial_rels;
 948         ListCell   *jl;
 949
 950         /*
 951          * Count the number of child joinlist nodes.  This is the depth of the
 952          * dynamic-programming algorithm we must employ to consider all ways of
 953          * joining the child nodes.
 954          */
 955         levels_needed = list_length(joinlist);
 956
 957         if (levels_needed <= 0)
 958                 return NULL;                    /* nothing to do? */
 959
 960         /*
 961          * Construct a list of rels corresponding to the child joinlist nodes.
 962          * This may contain both base rels and rels constructed according to
 963          * sub-joinlists.
 964          */
 965         initial_rels = NIL;
 966         foreach(jl, joinlist)
 967         {
 968                 Node       *jlnode = (Node *) lfirst(jl);
 969                 RelOptInfo *thisrel;
 970
 971                 if (IsA(jlnode, RangeTblRef))
 972                 {
 973                         int                     varno = ((RangeTblRef *) jlnode)->rtindex;
 974
 975                         thisrel = find_base_rel(root, varno);
 976                 }
 977                 else if (IsA(jlnode, List))
 978                 {
 979                         /* Recurse to handle subproblem */
 980                         thisrel = make_rel_from_joinlist(root, (List *) jlnode);
 981                 }
 982                 else
 983                 {
 984                         elog(ERROR, "unrecognized joinlist node type: %d",
 985                                  (int) nodeTag(jlnode));
 986                         thisrel = NULL;         /* keep compiler quiet */
 987                 }
 988
 989                 initial_rels = lappend(initial_rels, thisrel);
 990         }
 991
 992         if (levels_needed == 1)
 993         {
 994                 /*
 995                  * Single joinlist node, so we're done.
 996                  */
 997                 return (RelOptInfo *) linitial(initial_rels);
 998         }
 999         else
1000         {
1001                 /*
1002                  * Consider the different orders in which we could join the rels,
1003                  * using a plugin, GEQO, or the regular join search code.
1004                  *
1005                  * We put the initial_rels list into a PlannerInfo field because
1006                  * has_legal_joinclause() needs to look at it (ugly :-().
1007                  */
1008                 root->initial_rels = initial_rels;
1009
1010                 if (join_search_hook)
1011                         return (*join_search_hook) (root, levels_needed, initial_rels);
1012                 else if (enable_geqo && levels_needed >= geqo_threshold)
1013                         return geqo(root, levels_needed, initial_rels);
1014                 else
1015                         return standard_join_search(root, levels_needed, initial_rels);
1016         }
1017 }
1018
1019 /*
1020  * standard_join_search
1021  *        Find possible joinpaths for a query by successively finding ways
1022  *        to join component relations into join relations.
1023  *
1024  * 'levels_needed' is the number of iterations needed, ie, the number of
1025  *              independent jointree items in the query.  This is > 1.
1026  *
1027  * 'initial_rels' is a list of RelOptInfo nodes for each independent
1028  *              jointree item.  These are the components to be joined together.
1029  *              Note that levels_needed == list_length(initial_rels).
1030  *
1031  * Returns the final level of join relations, i.e., the relation that is
1032  * the result of joining all the original relations together.
1033  * At least one implementation path must be provided for this relation and
1034  * all required sub-relations.
1035  *
1036  * To support loadable plugins that modify planner behavior by changing the
1037  * join searching algorithm, we provide a hook variable that lets a plugin
1038  * replace or supplement this function.  Any such hook must return the same
1039  * final join relation as the standard code would, but it might have a
1040  * different set of implementation paths attached, and only the sub-joinrels
1041  * needed for these paths need have been instantiated.
1042  *
1043  * Note to plugin authors: the functions invoked during standard_join_search()
1044  * modify root->join_rel_list and root->join_rel_hash.  If you want to do more
1045  * than one join-order search, you'll probably need to save and restore the
1046  * original states of those data structures.  See geqo_eval() for an example.
1047  */
1048 RelOptInfo *
1049 standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
1050 {
1051         int                     lev;
1052         RelOptInfo *rel;
1053
1054         /*
1055          * This function cannot be invoked recursively within any one planning
1056          * problem, so join_rel_level[] can't be in use already.
1057          */
1058         Assert(root->join_rel_level == NULL);
1059
1060         /*
1061          * We employ a simple "dynamic programming" algorithm: we first find all
1062          * ways to build joins of two jointree items, then all ways to build joins
1063          * of three items (from two-item joins and single items), then four-item
1064          * joins, and so on until we have considered all ways to join all the
1065          * items into one rel.
1066          *
1067          * root->join_rel_level[j] is a list of all the j-item rels.  Initially we
1068          * set root->join_rel_level[1] to represent all the single-jointree-item
1069          * relations.
1070          */
1071         root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
1072
1073         root->join_rel_level[1] = initial_rels;
1074
1075         for (lev = 2; lev <= levels_needed; lev++)
1076         {
1077                 ListCell   *lc;
1078
1079                 /*
1080                  * Determine all possible pairs of relations to be joined at this
1081                  * level, and build paths for making each one from every available
1082                  * pair of lower-level relations.
1083                  */
1084                 join_search_one_level(root, lev);
1085
1086                 /*
1087                  * Do cleanup work on each just-processed rel.
1088                  */
1089                 foreach(lc, root->join_rel_level[lev])
1090                 {
1091                         rel = (RelOptInfo *) lfirst(lc);
1092
1093                         /* Find and save the cheapest paths for this rel */
1094                         set_cheapest(rel);
1095
1096 #ifdef OPTIMIZER_DEBUG
1097                         debug_print_rel(root, rel);
1098 #endif
1099                 }
1100         }
1101
1102         /*
1103          * We should have a single rel at the final level.
1104          */
1105         if (root->join_rel_level[levels_needed] == NIL)
1106                 elog(ERROR, "failed to build any %d-way joins", levels_needed);
1107         Assert(list_length(root->join_rel_level[levels_needed]) == 1);
1108
1109         rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
1110
1111         root->join_rel_level = NULL;
1112
1113         return rel;
1114 }
1115
1116 /*****************************************************************************
1117  *                      PUSHING QUALS DOWN INTO SUBQUERIES
1118  *****************************************************************************/
1119
1120 /*
1121  * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
1122  *
1123  * subquery is the particular component query being checked.  topquery
1124  * is the top component of a set-operations tree (the same Query if no
1125  * set-op is involved).
1126  *
1127  * Conditions checked here:
1128  *
1129  * 1. If the subquery has a LIMIT clause, we must not push down any quals,
1130  * since that could change the set of rows returned.
1131  *
1132  * 2. If the subquery contains any window functions, we can't push quals
1133  * into it, because that could change the results.
1134  *
1135  * 3. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
1136  * quals into it, because that could change the results.
1137  *
1138  * 4. For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
1139  * push quals into each component query, but the quals can only reference
1140  * subquery columns that suffer no type coercions in the set operation.
1141  * Otherwise there are possible semantic gotchas.  So, we check the
1142  * component queries to see if any of them have different output types;
1143  * differentTypes[k] is set true if column k has different type in any
1144  * component.
1145  */
1146 static bool
1147 subquery_is_pushdown_safe(Query *subquery, Query *topquery,
1148                                                   bool *differentTypes)
1149 {
1150         SetOperationStmt *topop;
1151
1152         /* Check point 1 */
1153         if (subquery->limitOffset != NULL || subquery->limitCount != NULL)
1154                 return false;
1155
1156         /* Check point 2 */
1157         if (subquery->hasWindowFuncs)
1158                 return false;
1159
1160         /* Are we at top level, or looking at a setop component? */
1161         if (subquery == topquery)
1162         {
1163                 /* Top level, so check any component queries */
1164                 if (subquery->setOperations != NULL)
1165                         if (!recurse_pushdown_safe(subquery->setOperations, topquery,
1166                                                                            differentTypes))
1167                                 return false;
1168         }
1169         else
1170         {
1171                 /* Setop component must not have more components (too weird) */
1172                 if (subquery->setOperations != NULL)
1173                         return false;
1174                 /* Check whether setop component output types match top level */
1175                 topop = (SetOperationStmt *) topquery->setOperations;
1176                 Assert(topop && IsA(topop, SetOperationStmt));
1177                 compare_tlist_datatypes(subquery->targetList,
1178                                                                 topop->colTypes,
1179                                                                 differentTypes);
1180         }
1181         return true;
1182 }
1183
1184 /*
1185  * Helper routine to recurse through setOperations tree
1186  */
1187 static bool
1188 recurse_pushdown_safe(Node *setOp, Query *topquery,
1189                                           bool *differentTypes)
1190 {
1191         if (IsA(setOp, RangeTblRef))
1192         {
1193                 RangeTblRef *rtr = (RangeTblRef *) setOp;
1194                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
1195                 Query      *subquery = rte->subquery;
1196
1197                 Assert(subquery != NULL);
1198                 return subquery_is_pushdown_safe(subquery, topquery, differentTypes);
1199         }
1200         else if (IsA(setOp, SetOperationStmt))
1201         {
1202                 SetOperationStmt *op = (SetOperationStmt *) setOp;
1203
1204                 /* EXCEPT is no good */
1205                 if (op->op == SETOP_EXCEPT)
1206                         return false;
1207                 /* Else recurse */
1208                 if (!recurse_pushdown_safe(op->larg, topquery, differentTypes))
1209                         return false;
1210                 if (!recurse_pushdown_safe(op->rarg, topquery, differentTypes))
1211                         return false;
1212         }
1213         else
1214         {
1215                 elog(ERROR, "unrecognized node type: %d",
1216                          (int) nodeTag(setOp));
1217         }
1218         return true;
1219 }
1220
1221 /*
1222  * Compare tlist's datatypes against the list of set-operation result types.
1223  * For any items that are different, mark the appropriate element of
1224  * differentTypes[] to show that this column will have type conversions.
1225  *
1226  * We don't have to care about typmods here: the only allowed difference
1227  * between set-op input and output typmods is input is a specific typmod
1228  * and output is -1, and that does not require a coercion.
1229  */
1230 static void
1231 compare_tlist_datatypes(List *tlist, List *colTypes,
1232                                                 bool *differentTypes)
1233 {
1234         ListCell   *l;
1235         ListCell   *colType = list_head(colTypes);
1236
1237         foreach(l, tlist)
1238         {
1239                 TargetEntry *tle = (TargetEntry *) lfirst(l);
1240
1241                 if (tle->resjunk)
1242                         continue;                       /* ignore resjunk columns */
1243                 if (colType == NULL)
1244                         elog(ERROR, "wrong number of tlist entries");
1245                 if (exprType((Node *) tle->expr) != lfirst_oid(colType))
1246                         differentTypes[tle->resno] = true;
1247                 colType = lnext(colType);
1248         }
1249         if (colType != NULL)
1250                 elog(ERROR, "wrong number of tlist entries");
1251 }
1252
1253 /*
1254  * qual_is_pushdown_safe - is a particular qual safe to push down?
1255  *
1256  * qual is a restriction clause applying to the given subquery (whose RTE
1257  * has index rti in the parent query).
1258  *
1259  * Conditions checked here:
1260  *
1261  * 1. The qual must not contain any subselects (mainly because I'm not sure
1262  * it will work correctly: sublinks will already have been transformed into
1263  * subplans in the qual, but not in the subquery).
1264  *
1265  * 2. The qual must not refer to the whole-row output of the subquery
1266  * (since there is no easy way to name that within the subquery itself).
1267  *
1268  * 3. The qual must not refer to any subquery output columns that were
1269  * found to have inconsistent types across a set operation tree by
1270  * subquery_is_pushdown_safe().
1271  *
1272  * 4. If the subquery uses DISTINCT ON, we must not push down any quals that
1273  * refer to non-DISTINCT output columns, because that could change the set
1274  * of rows returned.  (This condition is vacuous for DISTINCT, because then
1275  * there are no non-DISTINCT output columns, so we needn't check.  But note
1276  * we are assuming that the qual can't distinguish values that the DISTINCT
1277  * operator sees as equal.      This is a bit shaky but we have no way to test
1278  * for the case, and it's unlikely enough that we shouldn't refuse the
1279  * optimization just because it could theoretically happen.)
1280  *
1281  * 5. We must not push down any quals that refer to subselect outputs that
1282  * return sets, else we'd introduce functions-returning-sets into the
1283  * subquery's WHERE/HAVING quals.
1284  *
1285  * 6. We must not push down any quals that refer to subselect outputs that
1286  * contain volatile functions, for fear of introducing strange results due
1287  * to multiple evaluation of a volatile function.
1288  */
1289 static bool
1290 qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual,
1291                                           bool *differentTypes)
1292 {
1293         bool            safe = true;
1294         List       *vars;
1295         ListCell   *vl;
1296         Bitmapset  *tested = NULL;
1297
1298         /* Refuse subselects (point 1) */
1299         if (contain_subplans(qual))
1300                 return false;
1301
1302         /*
1303          * It would be unsafe to push down window function calls, but at least for
1304          * the moment we could never see any in a qual anyhow.
1305          */
1306         Assert(!contain_window_function(qual));
1307
1308         /*
1309          * Examine all Vars used in clause; since it's a restriction clause, all
1310          * such Vars must refer to subselect output columns.
1311          */
1312         vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS);
1313         foreach(vl, vars)
1314         {
1315                 Var                *var = (Var *) lfirst(vl);
1316                 TargetEntry *tle;
1317
1318                 /*
1319                  * XXX Punt if we find any PlaceHolderVars in the restriction clause.
1320                  * It's not clear whether a PHV could safely be pushed down, and even
1321                  * less clear whether such a situation could arise in any cases of
1322                  * practical interest anyway.  So for the moment, just refuse to push
1323                  * down.
1324                  */
1325                 if (!IsA(var, Var))
1326                 {
1327                         safe = false;
1328                         break;
1329                 }
1330
1331                 Assert(var->varno == rti);
1332
1333                 /* Check point 2 */
1334                 if (var->varattno == 0)
1335                 {
1336                         safe = false;
1337                         break;
1338                 }
1339
1340                 /*
1341                  * We use a bitmapset to avoid testing the same attno more than once.
1342                  * (NB: this only works because subquery outputs can't have negative
1343                  * attnos.)
1344                  */
1345                 if (bms_is_member(var->varattno, tested))
1346                         continue;
1347                 tested = bms_add_member(tested, var->varattno);
1348
1349                 /* Check point 3 */
1350                 if (differentTypes[var->varattno])
1351                 {
1352                         safe = false;
1353                         break;
1354                 }
1355
1356                 /* Must find the tlist element referenced by the Var */
1357                 tle = get_tle_by_resno(subquery->targetList, var->varattno);
1358                 Assert(tle != NULL);
1359                 Assert(!tle->resjunk);
1360
1361                 /* If subquery uses DISTINCT ON, check point 4 */
1362                 if (subquery->hasDistinctOn &&
1363                         !targetIsInSortList(tle, InvalidOid, subquery->distinctClause))
1364                 {
1365                         /* non-DISTINCT column, so fail */
1366                         safe = false;
1367                         break;
1368                 }
1369
1370                 /* Refuse functions returning sets (point 5) */
1371                 if (expression_returns_set((Node *) tle->expr))
1372                 {
1373                         safe = false;
1374                         break;
1375                 }
1376
1377                 /* Refuse volatile functions (point 6) */
1378                 if (contain_volatile_functions((Node *) tle->expr))
1379                 {
1380                         safe = false;
1381                         break;
1382                 }
1383         }
1384
1385         list_free(vars);
1386         bms_free(tested);
1387
1388         return safe;
1389 }
1390
1391 /*
1392  * subquery_push_qual - push down a qual that we have determined is safe
1393  */
1394 static void
1395 subquery_push_qual(Query *subquery, RangeTblEntry *rte, Index rti, Node *qual)
1396 {
1397         if (subquery->setOperations != NULL)
1398         {
1399                 /* Recurse to push it separately to each component query */
1400                 recurse_push_qual(subquery->setOperations, subquery,
1401                                                   rte, rti, qual);
1402         }
1403         else
1404         {
1405                 /*
1406                  * We need to replace Vars in the qual (which must refer to outputs of
1407                  * the subquery) with copies of the subquery's targetlist expressions.
1408                  * Note that at this point, any uplevel Vars in the qual should have
1409                  * been replaced with Params, so they need no work.
1410                  *
1411                  * This step also ensures that when we are pushing into a setop tree,
1412                  * each component query gets its own copy of the qual.
1413                  */
1414                 qual = ResolveNew(qual, rti, 0, rte,
1415                                                   subquery->targetList,
1416                                                   CMD_SELECT, 0,
1417                                                   &subquery->hasSubLinks);
1418
1419                 /*
1420                  * Now attach the qual to the proper place: normally WHERE, but if the
1421                  * subquery uses grouping or aggregation, put it in HAVING (since the
1422                  * qual really refers to the group-result rows).
1423                  */
1424                 if (subquery->hasAggs || subquery->groupClause || subquery->havingQual)
1425                         subquery->havingQual = make_and_qual(subquery->havingQual, qual);
1426                 else
1427                         subquery->jointree->quals =
1428                                 make_and_qual(subquery->jointree->quals, qual);
1429
1430                 /*
1431                  * We need not change the subquery's hasAggs or hasSublinks flags,
1432                  * since we can't be pushing down any aggregates that weren't there
1433                  * before, and we don't push down subselects at all.
1434                  */
1435         }
1436 }
1437
1438 /*
1439  * Helper routine to recurse through setOperations tree
1440  */
1441 static void
1442 recurse_push_qual(Node *setOp, Query *topquery,
1443                                   RangeTblEntry *rte, Index rti, Node *qual)
1444 {
1445         if (IsA(setOp, RangeTblRef))
1446         {
1447                 RangeTblRef *rtr = (RangeTblRef *) setOp;
1448                 RangeTblEntry *subrte = rt_fetch(rtr->rtindex, topquery->rtable);
1449                 Query      *subquery = subrte->subquery;
1450
1451                 Assert(subquery != NULL);
1452                 subquery_push_qual(subquery, rte, rti, qual);
1453         }
1454         else if (IsA(setOp, SetOperationStmt))
1455         {
1456                 SetOperationStmt *op = (SetOperationStmt *) setOp;
1457
1458                 recurse_push_qual(op->larg, topquery, rte, rti, qual);
1459                 recurse_push_qual(op->rarg, topquery, rte, rti, qual);
1460         }
1461         else
1462         {
1463                 elog(ERROR, "unrecognized node type: %d",
1464                          (int) nodeTag(setOp));
1465         }
1466 }
1467
1468 /*****************************************************************************
1469  *                      DEBUG SUPPORT
1470  *****************************************************************************/
1471
1472 #ifdef OPTIMIZER_DEBUG
1473
1474 static void
1475 print_relids(Relids relids)
1476 {
1477         Relids          tmprelids;
1478         int                     x;
1479         bool            first = true;
1480
1481         tmprelids = bms_copy(relids);
1482         while ((x = bms_first_member(tmprelids)) >= 0)
1483         {
1484                 if (!first)
1485                         printf(" ");
1486                 printf("%d", x);
1487                 first = false;
1488         }
1489         bms_free(tmprelids);
1490 }
1491
1492 static void
1493 print_restrictclauses(PlannerInfo *root, List *clauses)
1494 {
1495         ListCell   *l;
1496
1497         foreach(l, clauses)
1498         {
1499                 RestrictInfo *c = lfirst(l);
1500
1501                 print_expr((Node *) c->clause, root->parse->rtable);
1502                 if (lnext(l))
1503                         printf(", ");
1504         }
1505 }
1506
1507 static void
1508 print_path(PlannerInfo *root, Path *path, int indent)
1509 {
1510         const char *ptype;
1511         bool            join = false;
1512         Path       *subpath = NULL;
1513         int                     i;
1514
1515         switch (nodeTag(path))
1516         {
1517                 case T_Path:
1518                         ptype = "SeqScan";
1519                         break;
1520                 case T_IndexPath:
1521                         ptype = "IdxScan";
1522                         break;
1523                 case T_BitmapHeapPath:
1524                         ptype = "BitmapHeapScan";
1525                         break;
1526                 case T_BitmapAndPath:
1527                         ptype = "BitmapAndPath";
1528                         break;
1529                 case T_BitmapOrPath:
1530                         ptype = "BitmapOrPath";
1531                         break;
1532                 case T_TidPath:
1533                         ptype = "TidScan";
1534                         break;
1535                 case T_ForeignPath:
1536                         ptype = "ForeignScan";
1537                         break;
1538                 case T_AppendPath:
1539                         ptype = "Append";
1540                         break;
1541                 case T_MergeAppendPath:
1542                         ptype = "MergeAppend";
1543                         break;
1544                 case T_ResultPath:
1545                         ptype = "Result";
1546                         break;
1547                 case T_MaterialPath:
1548                         ptype = "Material";
1549                         subpath = ((MaterialPath *) path)->subpath;
1550                         break;
1551                 case T_UniquePath:
1552                         ptype = "Unique";
1553                         subpath = ((UniquePath *) path)->subpath;
1554                         break;
1555                 case T_NestPath:
1556                         ptype = "NestLoop";
1557                         join = true;
1558                         break;
1559                 case T_MergePath:
1560                         ptype = "MergeJoin";
1561                         join = true;
1562                         break;
1563                 case T_HashPath:
1564                         ptype = "HashJoin";
1565                         join = true;
1566                         break;
1567                 default:
1568                         ptype = "???Path";
1569                         break;
1570         }
1571
1572         for (i = 0; i < indent; i++)
1573                 printf("\t");
1574         printf("%s", ptype);
1575
1576         if (path->parent)
1577         {
1578                 printf("(");
1579                 print_relids(path->parent->relids);
1580                 printf(") rows=%.0f", path->parent->rows);
1581         }
1582         printf(" cost=%.2f..%.2f\n", path->startup_cost, path->total_cost);
1583
1584         if (path->pathkeys)
1585         {
1586                 for (i = 0; i < indent; i++)
1587                         printf("\t");
1588                 printf("  pathkeys: ");
1589                 print_pathkeys(path->pathkeys, root->parse->rtable);
1590         }
1591
1592         if (join)
1593         {
1594                 JoinPath   *jp = (JoinPath *) path;
1595
1596                 for (i = 0; i < indent; i++)
1597                         printf("\t");
1598                 printf("  clauses: ");
1599                 print_restrictclauses(root, jp->joinrestrictinfo);
1600                 printf("\n");
1601
1602                 if (IsA(path, MergePath))
1603                 {
1604                         MergePath  *mp = (MergePath *) path;
1605
1606                         for (i = 0; i < indent; i++)
1607                                 printf("\t");
1608                         printf("  sortouter=%d sortinner=%d materializeinner=%d\n",
1609                                    ((mp->outersortkeys) ? 1 : 0),
1610                                    ((mp->innersortkeys) ? 1 : 0),
1611                                    ((mp->materialize_inner) ? 1 : 0));
1612                 }
1613
1614                 print_path(root, jp->outerjoinpath, indent + 1);
1615                 print_path(root, jp->innerjoinpath, indent + 1);
1616         }
1617
1618         if (subpath)
1619                 print_path(root, subpath, indent + 1);
1620 }
1621
1622 void
1623 debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
1624 {
1625         ListCell   *l;
1626
1627         printf("RELOPTINFO (");
1628         print_relids(rel->relids);
1629         printf("): rows=%.0f width=%d\n", rel->rows, rel->width);
1630
1631         if (rel->baserestrictinfo)
1632         {
1633                 printf("\tbaserestrictinfo: ");
1634                 print_restrictclauses(root, rel->baserestrictinfo);
1635                 printf("\n");
1636         }
1637
1638         if (rel->joininfo)
1639         {
1640                 printf("\tjoininfo: ");
1641                 print_restrictclauses(root, rel->joininfo);
1642                 printf("\n");
1643         }
1644
1645         printf("\tpath list:\n");
1646         foreach(l, rel->pathlist)
1647                 print_path(root, lfirst(l), 1);
1648         printf("\n\tcheapest startup path:\n");
1649         print_path(root, rel->cheapest_startup_path, 1);
1650         printf("\n\tcheapest total path:\n");
1651         print_path(root, rel->cheapest_total_path, 1);
1652         printf("\n");
1653         fflush(stdout);
1654 }
1655
1656 #endif   /* OPTIMIZER_DEBUG */