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.92 2006/01/31 21:39:24 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         List       *joinlist;
  87         RelOptInfo *final_rel;
  88         Path       *cheapestpath;
  89         Path       *sortedpath;
  90
  91         /* Make tuple_fraction accessible to lower-level routines */
  92         root->tuple_fraction = tuple_fraction;
  93
  94         *num_groups = 1;                        /* default result */
  95
  96         /*
  97          * If the query has an empty join tree, then it's something easy like
  98          * "SELECT 2+2;" or "INSERT ... VALUES()".      Fall through quickly.
  99          */
 100         if (parse->jointree->fromlist == NIL)
 101         {
 102                 *cheapest_path = (Path *) create_result_path(NULL, NULL,
 103                                                                                         (List *) parse->jointree->quals);
 104                 *sorted_path = NULL;
 105                 return;
 106         }
 107
 108         /*
 109          * Pull out any non-variable WHERE clauses so these can be put in a
 110          * toplevel "Result" node, where they will gate execution of the whole
 111          * plan (the Result will not invoke its descendant plan unless the quals
 112          * are true).  Note that any *really* non-variable quals will have been
 113          * optimized away by eval_const_expressions().  What we're mostly
 114          * interested in here is quals that depend only on outer-level vars,
 115          * although if the qual reduces to "WHERE FALSE" this path will also be
 116          * taken.
 117          */
 118         parse->jointree->quals = (Node *)
 119                 pull_constant_clauses((List *) parse->jointree->quals,
 120                                                           &constant_quals);
 121
 122         /*
 123          * Init planner lists to empty, and set up the array to hold RelOptInfos
 124          * for "simple" rels.
 125          *
 126          * NOTE: in_info_list and append_rel_list were set up by subquery_planner,
 127          * do not touch here
 128          */
 129         root->simple_rel_array_size = list_length(parse->rtable) + 1;
 130         root->simple_rel_array = (RelOptInfo **)
 131                 palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));
 132         root->join_rel_list = NIL;
 133         root->join_rel_hash = NULL;
 134         root->equi_key_list = NIL;
 135         root->left_join_clauses = NIL;
 136         root->right_join_clauses = NIL;
 137         root->full_join_clauses = NIL;
 138         root->oj_info_list = NIL;
 139
 140         /*
 141          * Construct RelOptInfo nodes for all base relations in query.
 142          */
 143         add_base_rels_to_query(root, (Node *) parse->jointree);
 144
 145         /*
 146          * Examine the targetlist and qualifications, adding entries to baserel
 147          * targetlists for all referenced Vars.  Restrict and join clauses are
 148          * added to appropriate lists belonging to the mentioned relations.  We
 149          * also build lists of equijoined keys for pathkey construction, and
 150          * form a target joinlist for make_one_rel() to work from.
 151          *
 152          * Note: all subplan nodes will have "flat" (var-only) tlists. This
 153          * implies that all expression evaluations are done at the root of the
 154          * plan tree. Once upon a time there was code to try to push expensive
 155          * function calls down to lower plan nodes, but that's dead code and has
 156          * been for a long time...
 157          */
 158         build_base_rel_tlists(root, tlist);
 159
 160         joinlist = deconstruct_jointree(root);
 161
 162         /*
 163          * Use the completed lists of equijoined keys to deduce any implied but
 164          * unstated equalities (for example, A=B and B=C imply A=C).
 165          */
 166         generate_implied_equalities(root);
 167
 168         /*
 169          * We should now have all the pathkey equivalence sets built, so it's now
 170          * possible to convert the requested query_pathkeys to canonical form.
 171          * Also canonicalize the groupClause and sortClause pathkeys for use
 172          * later.
 173          */
 174         root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 175         root->group_pathkeys = canonicalize_pathkeys(root, root->group_pathkeys);
 176         root->sort_pathkeys = canonicalize_pathkeys(root, root->sort_pathkeys);
 177
 178         /*
 179          * Ready to do the primary planning.
 180          */
 181         final_rel = make_one_rel(root, joinlist);
 182
 183         if (!final_rel || !final_rel->cheapest_total_path)
 184                 elog(ERROR, "failed to construct the join relation");
 185
 186         /*
 187          * If there's grouping going on, estimate the number of result groups. We
 188          * couldn't do this any earlier because it depends on relation size
 189          * estimates that were set up above.
 190          *
 191          * Then convert tuple_fraction to fractional form if it is absolute, and
 192          * adjust it based on the knowledge that grouping_planner will be doing
 193          * grouping or aggregation work with our result.
 194          *
 195          * This introduces some undesirable coupling between this code and
 196          * grouping_planner, but the alternatives seem even uglier; we couldn't
 197          * pass back completed paths without making these decisions here.
 198          */
 199         if (parse->groupClause)
 200         {
 201                 List       *groupExprs;
 202
 203                 groupExprs = get_sortgrouplist_exprs(parse->groupClause,
 204                                                                                          parse->targetList);
 205                 *num_groups = estimate_num_groups(root,
 206                                                                                   groupExprs,
 207                                                                                   final_rel->rows);
 208
 209                 /*
 210                  * In GROUP BY mode, an absolute LIMIT is relative to the number of
 211                  * groups not the number of tuples.  If the caller gave us a fraction,
 212                  * keep it as-is.  (In both cases, we are effectively assuming that
 213                  * all the groups are about the same size.)
 214                  */
 215                 if (tuple_fraction >= 1.0)
 216                         tuple_fraction /= *num_groups;
 217
 218                 /*
 219                  * If both GROUP BY and ORDER BY are specified, we will need two
 220                  * levels of sort --- and, therefore, certainly need to read all the
 221                  * tuples --- unless ORDER BY is a subset of GROUP BY.
 222                  */
 223                 if (parse->groupClause && parse->sortClause &&
 224                         !pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys))
 225                         tuple_fraction = 0.0;
 226         }
 227         else if (parse->hasAggs || root->hasHavingQual)
 228         {
 229                 /*
 230                  * Ungrouped aggregate will certainly want to read all the tuples, and
 231                  * it will deliver a single result row (so leave *num_groups 1).
 232                  */
 233                 tuple_fraction = 0.0;
 234         }
 235         else if (parse->distinctClause)
 236         {
 237                 /*
 238                  * Since there was no grouping or aggregation, it's reasonable to
 239                  * assume the UNIQUE filter has effects comparable to GROUP BY. Return
 240                  * the estimated number of output rows for use by caller. (If DISTINCT
 241                  * is used with grouping, we ignore its effects for rowcount
 242                  * estimation purposes; this amounts to assuming the grouped rows are
 243                  * distinct already.)
 244                  */
 245                 List       *distinctExprs;
 246
 247                 distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
 248                                                                                                 parse->targetList);
 249                 *num_groups = estimate_num_groups(root,
 250                                                                                   distinctExprs,
 251                                                                                   final_rel->rows);
 252
 253                 /*
 254                  * Adjust tuple_fraction the same way as for GROUP BY, too.
 255                  */
 256                 if (tuple_fraction >= 1.0)
 257                         tuple_fraction /= *num_groups;
 258         }
 259         else
 260         {
 261                 /*
 262                  * Plain non-grouped, non-aggregated query: an absolute tuple fraction
 263                  * can be divided by the number of tuples.
 264                  */
 265                 if (tuple_fraction >= 1.0)
 266                         tuple_fraction /= final_rel->rows;
 267         }
 268
 269         /*
 270          * Pick out the cheapest-total path and the cheapest presorted path for
 271          * the requested pathkeys (if there is one).  We should take the tuple
 272          * fraction into account when selecting the cheapest presorted path, but
 273          * not when selecting the cheapest-total path, since if we have to sort
 274          * then we'll have to fetch all the tuples.  (But there's a special case:
 275          * if query_pathkeys is NIL, meaning order doesn't matter, then the
 276          * "cheapest presorted" path will be the cheapest overall for the tuple
 277          * fraction.)
 278          *
 279          * The cheapest-total path is also the one to use if grouping_planner
 280          * decides to use hashed aggregation, so we return it separately even if
 281          * this routine thinks the presorted path is the winner.
 282          */
 283         cheapestpath = final_rel->cheapest_total_path;
 284
 285         sortedpath =
 286                 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 287                                                                                                   root->query_pathkeys,
 288                                                                                                   tuple_fraction);
 289
 290         /* Don't return same path in both guises; just wastes effort */
 291         if (sortedpath == cheapestpath)
 292                 sortedpath = NULL;
 293
 294         /*
 295          * Forget about the presorted path if it would be cheaper to sort the
 296          * cheapest-total path.  Here we need consider only the behavior at the
 297          * tuple fraction point.
 298          */
 299         if (sortedpath)
 300         {
 301                 Path            sort_path;      /* dummy for result of cost_sort */
 302
 303                 if (root->query_pathkeys == NIL ||
 304                         pathkeys_contained_in(root->query_pathkeys,
 305                                                                   cheapestpath->pathkeys))
 306                 {
 307                         /* No sort needed for cheapest path */
 308                         sort_path.startup_cost = cheapestpath->startup_cost;
 309                         sort_path.total_cost = cheapestpath->total_cost;
 310                 }
 311                 else
 312                 {
 313                         /* Figure cost for sorting */
 314                         cost_sort(&sort_path, root, root->query_pathkeys,
 315                                           cheapestpath->total_cost,
 316                                           final_rel->rows, final_rel->width);
 317                 }
 318
 319                 if (compare_fractional_path_costs(sortedpath, &sort_path,
 320                                                                                   tuple_fraction) > 0)
 321                 {
 322                         /* Presorted path is a loser */
 323                         sortedpath = NULL;
 324                 }
 325         }
 326
 327         /*
 328          * If we have constant quals, add a toplevel Result step to process them.
 329          */
 330         if (constant_quals)
 331         {
 332                 cheapestpath = (Path *) create_result_path(final_rel,
 333                                                                                                    cheapestpath,
 334                                                                                                    constant_quals);
 335                 if (sortedpath)
 336                         sortedpath = (Path *) create_result_path(final_rel,
 337                                                                                                          sortedpath,
 338                                                                                                          constant_quals);
 339         }
 340
 341         *cheapest_path = cheapestpath;
 342         *sorted_path = sortedpath;
 343 }