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