granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/planmain.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * planmain.c
   4  *        Routines to plan a single query
   5  *
   6  * What's in a name, anyway?  The top-level entry point of the planner/
   7  * optimizer is over in planner.c, not here as you might think from the
   8  * file name.  But this is the main code for planning a basic join operation,
   9  * shorn of features like subselects, inheritance, aggregates, grouping,
  10  * and so on.  (Those are the things planner.c deals with.)
  11  *
  12  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  13  * Portions Copyright (c) 1994, Regents of the University of California
  14  *
  15  *
  16  * IDENTIFICATION
  17  *        $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.87 2005/08/27 22:13:43 tgl Exp $
  18  *
  19  *-------------------------------------------------------------------------
  20  */
  21 #include "postgres.h"
  22
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/cost.h"
  25 #include "optimizer/pathnode.h"
  26 #include "optimizer/paths.h"
  27 #include "optimizer/planmain.h"
  28 #include "optimizer/tlist.h"
  29 #include "utils/selfuncs.h"
  30
  31
  32 /*
  33  * query_planner
  34  *        Generate a path (that is, a simplified plan) for a basic query,
  35  *        which may involve joins but not any fancier features.
  36  *
  37  * Since query_planner does not handle the toplevel processing (grouping,
  38  * sorting, etc) it cannot select the best path by itself.      It selects
  39  * two paths: the cheapest path that produces all the required tuples,
  40  * independent of any ordering considerations, and the cheapest path that
  41  * produces the expected fraction of the required tuples in the required
  42  * ordering, if there is a path that is cheaper for this than just sorting
  43  * the output of the cheapest overall path.  The caller (grouping_planner)
  44  * will make the final decision about which to use.
  45  *
  46  * Input parameters:
  47  * root describes the query to plan
  48  * tlist is the target list the query should produce
  49  *              (this is NOT necessarily root->parse->targetList!)
  50  * tuple_fraction is the fraction of tuples we expect will be retrieved
  51  *
  52  * Output parameters:
  53  * *cheapest_path receives the overall-cheapest path for the query
  54  * *sorted_path receives the cheapest presorted path for the query,
  55  *                              if any (NULL if there is no useful presorted path)
  56  * *num_groups receives the estimated number of groups, or 1 if query
  57  *                              does not use grouping
  58  *
  59  * Note: the PlannerInfo node also includes a query_pathkeys field, which is
  60  * both an input and an output of query_planner().  The input value signals
  61  * query_planner that the indicated sort order is wanted in the final output
  62  * plan.  But this value has not yet been "canonicalized", since the needed
  63  * info does not get computed until we scan the qual clauses.  We canonicalize
  64  * it as soon as that task is done.  (The main reason query_pathkeys is a
  65  * PlannerInfo field and not a passed parameter is that the low-level routines
  66  * in indxpath.c need to see it.)
  67  *
  68  * Note: the PlannerInfo node also includes group_pathkeys and sort_pathkeys,
  69  * which like query_pathkeys need to be canonicalized once the info is
  70  * available.
  71  *
  72  * tuple_fraction is interpreted as follows:
  73  *        0: expect all tuples to be retrieved (normal case)
  74  *        0 < tuple_fraction < 1: expect the given fraction of tuples available
  75  *              from the plan to be retrieved
  76  *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
  77  *              expected to be retrieved (ie, a LIMIT specification)
  78  */
  79 void
  80 query_planner(PlannerInfo *root, List *tlist, double tuple_fraction,
  81                           Path **cheapest_path, Path **sorted_path,
  82                           double *num_groups)
  83 {
  84         Query      *parse = root->parse;
  85         List       *constant_quals;
  86         RelOptInfo *final_rel;
  87         Path       *cheapestpath;
  88         Path       *sortedpath;
  89
  90         /* Make tuple_fraction accessible to lower-level routines */
  91         root->tuple_fraction = tuple_fraction;
  92
  93         *num_groups = 1;                        /* default result */
  94
  95         /*
  96          * If the query has an empty join tree, then it's something easy like
  97          * "SELECT 2+2;" or "INSERT ... VALUES()".      Fall through quickly.
  98          */
  99         if (parse->jointree->fromlist == NIL)
 100         {
 101                 *cheapest_path = (Path *) create_result_path(NULL, NULL,
 102                                                                                  (List *) parse->jointree->quals);
 103                 *sorted_path = NULL;
 104                 return;
 105         }
 106
 107         /*
 108          * Pull out any non-variable WHERE clauses so these can be put in a
 109          * toplevel "Result" node, where they will gate execution of the whole
 110          * plan (the Result will not invoke its descendant plan unless the
 111          * quals are true).  Note that any *really* non-variable quals will
 112          * have been optimized away by eval_const_expressions().  What we're
 113          * mostly interested in here is quals that depend only on outer-level
 114          * vars, although if the qual reduces to "WHERE FALSE" this path will
 115          * also be taken.
 116          */
 117         parse->jointree->quals = (Node *)
 118                 pull_constant_clauses((List *) parse->jointree->quals,
 119                                                           &constant_quals);
 120
 121         /*
 122          * Init planner lists to empty.  We create the base_rel_array with a
 123          * size that will be sufficient if no pullups or inheritance additions
 124          * happen ... otherwise it will be enlarged as needed.
 125          *
 126          * NOTE: in_info_list was set up by subquery_planner, do not touch here
 127          */
 128         root->base_rel_array_size = list_length(parse->rtable) + 1;
 129         root->base_rel_array = (RelOptInfo **)
 130                 palloc0(root->base_rel_array_size * sizeof(RelOptInfo *));
 131         root->join_rel_list = NIL;
 132         root->join_rel_hash = NULL;
 133         root->equi_key_list = NIL;
 134         root->left_join_clauses = NIL;
 135         root->right_join_clauses = NIL;
 136         root->full_join_clauses = NIL;
 137
 138         /*
 139          * Construct RelOptInfo nodes for all base relations in query.
 140          */
 141         add_base_rels_to_query(root, (Node *) parse->jointree);
 142
 143         /*
 144          * Examine the targetlist and qualifications, adding entries to
 145          * baserel targetlists for all referenced Vars.  Restrict and join
 146          * clauses are added to appropriate lists belonging to the mentioned
 147          * relations.  We also build lists of equijoined keys for pathkey
 148          * construction.
 149          *
 150          * Note: all subplan nodes will have "flat" (var-only) tlists. This
 151          * implies that all expression evaluations are done at the root of the
 152          * plan tree.  Once upon a time there was code to try to push
 153          * expensive function calls down to lower plan nodes, but that's dead
 154          * code and has been for a long time...
 155          */
 156         build_base_rel_tlists(root, tlist);
 157
 158         (void) distribute_quals_to_rels(root, (Node *) parse->jointree);
 159
 160         /*
 161          * Use the completed lists of equijoined keys to deduce any implied
 162          * but unstated equalities (for example, A=B and B=C imply A=C).
 163          */
 164         generate_implied_equalities(root);
 165
 166         /*
 167          * We should now have all the pathkey equivalence sets built, so it's
 168          * now possible to convert the requested query_pathkeys to canonical
 169          * form.  Also canonicalize the groupClause and sortClause pathkeys
 170          * for use later.
 171          */
 172         root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 173         root->group_pathkeys = canonicalize_pathkeys(root, root->group_pathkeys);
 174         root->sort_pathkeys = canonicalize_pathkeys(root, root->sort_pathkeys);
 175
 176         /*
 177          * Ready to do the primary planning.
 178          */
 179         final_rel = make_one_rel(root);
 180
 181         if (!final_rel || !final_rel->cheapest_total_path)
 182                 elog(ERROR, "failed to construct the join relation");
 183
 184         /*
 185          * If there's grouping going on, estimate the number of result groups.
 186          * We couldn't do this any earlier because it depends on relation size
 187          * estimates that were set up above.
 188          *
 189          * Then convert tuple_fraction to fractional form if it is absolute,
 190          * and adjust it based on the knowledge that grouping_planner will be
 191          * doing grouping or aggregation work with our result.
 192          *
 193          * This introduces some undesirable coupling between this code and
 194          * grouping_planner, but the alternatives seem even uglier; we couldn't
 195          * pass back completed paths without making these decisions here.
 196          */
 197         if (parse->groupClause)
 198         {
 199                 List       *groupExprs;
 200
 201                 groupExprs = get_sortgrouplist_exprs(parse->groupClause,
 202                                                                                          parse->targetList);
 203                 *num_groups = estimate_num_groups(root,
 204                                                                                   groupExprs,
 205                                                                                   final_rel->rows);
 206
 207                 /*
 208                  * In GROUP BY mode, an absolute LIMIT is relative to the number
 209                  * of groups not the number of tuples.  If the caller gave us
 210                  * a fraction, keep it as-is.  (In both cases, we are effectively
 211                  * assuming that all the groups are about the same size.)
 212                  */
 213                 if (tuple_fraction >= 1.0)
 214                         tuple_fraction /= *num_groups;
 215
 216                 /*
 217                  * If both GROUP BY and ORDER BY are specified, we will need two
 218                  * levels of sort --- and, therefore, certainly need to read all
 219                  * the tuples --- unless ORDER BY is a subset of GROUP BY.
 220                  */
 221                 if (parse->groupClause && parse->sortClause &&
 222                         !pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys))
 223                         tuple_fraction = 0.0;
 224         }
 225         else if (parse->hasAggs || root->hasHavingQual)
 226         {
 227                 /*
 228                  * Ungrouped aggregate will certainly want to read all the tuples,
 229                  * and it will deliver a single result row (so leave *num_groups 1).
 230                  */
 231                 tuple_fraction = 0.0;
 232         }
 233         else if (parse->distinctClause)
 234         {
 235                 /*
 236                  * Since there was no grouping or aggregation, it's reasonable to
 237                  * assume the UNIQUE filter has effects comparable to GROUP BY.
 238                  * Return the estimated number of output rows for use by caller.
 239                  * (If DISTINCT is used with grouping, we ignore its effects for
 240                  * rowcount estimation purposes; this amounts to assuming the grouped
 241                  * rows are distinct already.)
 242                  */
 243                 List       *distinctExprs;
 244
 245                 distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
 246                                                                                                 parse->targetList);
 247                 *num_groups = estimate_num_groups(root,
 248                                                                                   distinctExprs,
 249                                                                                   final_rel->rows);
 250
 251                 /*
 252                  * Adjust tuple_fraction the same way as for GROUP BY, too.
 253                  */
 254                 if (tuple_fraction >= 1.0)
 255                         tuple_fraction /= *num_groups;
 256         }
 257         else
 258         {
 259                 /*
 260                  * Plain non-grouped, non-aggregated query: an absolute tuple
 261                  * fraction can be divided by the number of tuples.
 262                  */
 263                 if (tuple_fraction >= 1.0)
 264                         tuple_fraction /= final_rel->rows;
 265         }
 266
 267         /*
 268          * Pick out the cheapest-total path and the cheapest presorted path
 269          * for the requested pathkeys (if there is one).  We should take the
 270          * tuple fraction into account when selecting the cheapest presorted
 271          * path, but not when selecting the cheapest-total path, since if we
 272          * have to sort then we'll have to fetch all the tuples.  (But there's
 273          * a special case: if query_pathkeys is NIL, meaning order doesn't
 274          * matter, then the "cheapest presorted" path will be the cheapest
 275          * overall for the tuple fraction.)
 276          *
 277          * The cheapest-total path is also the one to use if grouping_planner
 278          * decides to use hashed aggregation, so we return it separately even
 279          * if this routine thinks the presorted path is the winner.
 280          */
 281         cheapestpath = final_rel->cheapest_total_path;
 282
 283         sortedpath =
 284                 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 285                                                                                                   root->query_pathkeys,
 286                                                                                                   tuple_fraction);
 287
 288         /* Don't return same path in both guises; just wastes effort */
 289         if (sortedpath == cheapestpath)
 290                 sortedpath = NULL;
 291
 292         /*
 293          * Forget about the presorted path if it would be cheaper to sort the
 294          * cheapest-total path.  Here we need consider only the behavior at
 295          * the tuple fraction point.
 296          */
 297         if (sortedpath)
 298         {
 299                 Path            sort_path;      /* dummy for result of cost_sort */
 300
 301                 if (root->query_pathkeys == NIL ||
 302                         pathkeys_contained_in(root->query_pathkeys,
 303                                                                   cheapestpath->pathkeys))
 304                 {
 305                         /* No sort needed for cheapest path */
 306                         sort_path.startup_cost = cheapestpath->startup_cost;
 307                         sort_path.total_cost = cheapestpath->total_cost;
 308                 }
 309                 else
 310                 {
 311                         /* Figure cost for sorting */
 312                         cost_sort(&sort_path, root, root->query_pathkeys,
 313                                           cheapestpath->total_cost,
 314                                           final_rel->rows, final_rel->width);
 315                 }
 316
 317                 if (compare_fractional_path_costs(sortedpath, &sort_path,
 318                                                                                   tuple_fraction) > 0)
 319                 {
 320                         /* Presorted path is a loser */
 321                         sortedpath = NULL;
 322                 }
 323         }
 324
 325         /*
 326          * If we have constant quals, add a toplevel Result step to process
 327          * them.
 328          */
 329         if (constant_quals)
 330         {
 331                 cheapestpath = (Path *) create_result_path(final_rel,
 332                                                                                                    cheapestpath,
 333                                                                                                    constant_quals);
 334                 if (sortedpath)
 335                         sortedpath = (Path *) create_result_path(final_rel,
 336                                                                                                          sortedpath,
 337                                                                                                          constant_quals);
 338         }
 339
 340         *cheapest_path = cheapestpath;
 341         *sorted_path = sortedpath;
 342 }