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.86 2005/07/02 23:00:41 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
  29
  30 /*--------------------
  31  * query_planner
  32  *        Generate a path (that is, a simplified plan) for a basic query,
  33  *        which may involve joins but not any fancier features.
  34  *
  35  * Since query_planner does not handle the toplevel processing (grouping,
  36  * sorting, etc) it cannot select the best path by itself.      It selects
  37  * two paths: the cheapest path that produces all the required tuples,
  38  * independent of any ordering considerations, and the cheapest path that
  39  * produces the expected fraction of the required tuples in the required
  40  * ordering, if there is a path that is cheaper for this than just sorting
  41  * the output of the cheapest overall path.  The caller (grouping_planner)
  42  * will make the final decision about which to use.
  43  *
  44  * Input parameters:
  45  * root describes the query to plan
  46  * tlist is the target list the query should produce
  47  *              (this is NOT necessarily root->parse->targetList!)
  48  * tuple_fraction is the fraction of tuples we expect will be retrieved
  49  *
  50  * Output parameters:
  51  * *cheapest_path receives the overall-cheapest path for the query
  52  * *sorted_path receives the cheapest presorted path for the query,
  53  *                              if any (NULL if there is no useful presorted path)
  54  *
  55  * Note: the PlannerInfo node also includes a query_pathkeys field, which is
  56  * both an input and an output of query_planner().  The input value signals
  57  * query_planner that the indicated sort order is wanted in the final output
  58  * plan.  But this value has not yet been "canonicalized", since the needed
  59  * info does not get computed until we scan the qual clauses.  We canonicalize
  60  * it as soon as that task is done.  (The main reason query_pathkeys is a
  61  * PlannerInfo field and not a passed parameter is that the low-level routines
  62  * in indxpath.c need to see it.)
  63  *
  64  * tuple_fraction is interpreted as follows:
  65  *        0: expect all tuples to be retrieved (normal case)
  66  *        0 < tuple_fraction < 1: expect the given fraction of tuples available
  67  *              from the plan to be retrieved
  68  *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
  69  *              expected to be retrieved (ie, a LIMIT specification)
  70  *--------------------
  71  */
  72 void
  73 query_planner(PlannerInfo *root, List *tlist, double tuple_fraction,
  74                           Path **cheapest_path, Path **sorted_path)
  75 {
  76         Query      *parse = root->parse;
  77         List       *constant_quals;
  78         RelOptInfo *final_rel;
  79         Path       *cheapestpath;
  80         Path       *sortedpath;
  81
  82         /* Make tuple_fraction accessible to lower-level routines */
  83         root->tuple_fraction = tuple_fraction;
  84
  85         /*
  86          * If the query has an empty join tree, then it's something easy like
  87          * "SELECT 2+2;" or "INSERT ... VALUES()".      Fall through quickly.
  88          */
  89         if (parse->jointree->fromlist == NIL)
  90         {
  91                 *cheapest_path = (Path *) create_result_path(NULL, NULL,
  92                                                                                  (List *) parse->jointree->quals);
  93                 *sorted_path = NULL;
  94                 return;
  95         }
  96
  97         /*
  98          * Pull out any non-variable WHERE clauses so these can be put in a
  99          * toplevel "Result" node, where they will gate execution of the whole
 100          * plan (the Result will not invoke its descendant plan unless the
 101          * quals are true).  Note that any *really* non-variable quals will
 102          * have been optimized away by eval_const_expressions().  What we're
 103          * mostly interested in here is quals that depend only on outer-level
 104          * vars, although if the qual reduces to "WHERE FALSE" this path will
 105          * also be taken.
 106          */
 107         parse->jointree->quals = (Node *)
 108                 pull_constant_clauses((List *) parse->jointree->quals,
 109                                                           &constant_quals);
 110
 111         /*
 112          * Init planner lists to empty.  We create the base_rel_array with a
 113          * size that will be sufficient if no pullups or inheritance additions
 114          * happen ... otherwise it will be enlarged as needed.
 115          *
 116          * NOTE: in_info_list was set up by subquery_planner, do not touch here
 117          */
 118         root->base_rel_array_size = list_length(parse->rtable) + 1;
 119         root->base_rel_array = (RelOptInfo **)
 120                 palloc0(root->base_rel_array_size * sizeof(RelOptInfo *));
 121         root->join_rel_list = NIL;
 122         root->join_rel_hash = NULL;
 123         root->equi_key_list = NIL;
 124         root->left_join_clauses = NIL;
 125         root->right_join_clauses = NIL;
 126         root->full_join_clauses = NIL;
 127
 128         /*
 129          * Construct RelOptInfo nodes for all base relations in query.
 130          */
 131         add_base_rels_to_query(root, (Node *) parse->jointree);
 132
 133         /*
 134          * Examine the targetlist and qualifications, adding entries to
 135          * baserel targetlists for all referenced Vars.  Restrict and join
 136          * clauses are added to appropriate lists belonging to the mentioned
 137          * relations.  We also build lists of equijoined keys for pathkey
 138          * construction.
 139          *
 140          * Note: all subplan nodes will have "flat" (var-only) tlists. This
 141          * implies that all expression evaluations are done at the root of the
 142          * plan tree.  Once upon a time there was code to try to push
 143          * expensive function calls down to lower plan nodes, but that's dead
 144          * code and has been for a long time...
 145          */
 146         build_base_rel_tlists(root, tlist);
 147
 148         (void) distribute_quals_to_rels(root, (Node *) parse->jointree);
 149
 150         /*
 151          * Use the completed lists of equijoined keys to deduce any implied
 152          * but unstated equalities (for example, A=B and B=C imply A=C).
 153          */
 154         generate_implied_equalities(root);
 155
 156         /*
 157          * We should now have all the pathkey equivalence sets built, so it's
 158          * now possible to convert the requested query_pathkeys to canonical
 159          * form.
 160          */
 161         root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 162
 163         /*
 164          * Ready to do the primary planning.
 165          */
 166         final_rel = make_one_rel(root);
 167
 168         if (!final_rel || !final_rel->cheapest_total_path)
 169                 elog(ERROR, "failed to construct the join relation");
 170
 171         /*
 172          * Now that we have an estimate of the final rel's size, we can
 173          * convert a tuple_fraction specified as an absolute count (ie, a
 174          * LIMIT option) into a fraction of the total tuples.
 175          */
 176         if (tuple_fraction >= 1.0)
 177                 tuple_fraction /= final_rel->rows;
 178
 179         /*
 180          * Pick out the cheapest-total path and the cheapest presorted path
 181          * for the requested pathkeys (if there is one).  We should take the
 182          * tuple fraction into account when selecting the cheapest presorted
 183          * path, but not when selecting the cheapest-total path, since if we
 184          * have to sort then we'll have to fetch all the tuples.  (But there's
 185          * a special case: if query_pathkeys is NIL, meaning order doesn't
 186          * matter, then the "cheapest presorted" path will be the cheapest
 187          * overall for the tuple fraction.)
 188          *
 189          * The cheapest-total path is also the one to use if grouping_planner
 190          * decides to use hashed aggregation, so we return it separately even
 191          * if this routine thinks the presorted path is the winner.
 192          */
 193         cheapestpath = final_rel->cheapest_total_path;
 194
 195         sortedpath =
 196                 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 197                                                                                                   root->query_pathkeys,
 198                                                                                                   tuple_fraction);
 199
 200         /* Don't return same path in both guises; just wastes effort */
 201         if (sortedpath == cheapestpath)
 202                 sortedpath = NULL;
 203
 204         /*
 205          * Forget about the presorted path if it would be cheaper to sort the
 206          * cheapest-total path.  Here we need consider only the behavior at
 207          * the tuple fraction point.
 208          */
 209         if (sortedpath)
 210         {
 211                 Path            sort_path;      /* dummy for result of cost_sort */
 212
 213                 if (root->query_pathkeys == NIL ||
 214                         pathkeys_contained_in(root->query_pathkeys,
 215                                                                   cheapestpath->pathkeys))
 216                 {
 217                         /* No sort needed for cheapest path */
 218                         sort_path.startup_cost = cheapestpath->startup_cost;
 219                         sort_path.total_cost = cheapestpath->total_cost;
 220                 }
 221                 else
 222                 {
 223                         /* Figure cost for sorting */
 224                         cost_sort(&sort_path, root, root->query_pathkeys,
 225                                           cheapestpath->total_cost,
 226                                           final_rel->rows, final_rel->width);
 227                 }
 228
 229                 if (compare_fractional_path_costs(sortedpath, &sort_path,
 230                                                                                   tuple_fraction) > 0)
 231                 {
 232                         /* Presorted path is a loser */
 233                         sortedpath = NULL;
 234                 }
 235         }
 236
 237         /*
 238          * If we have constant quals, add a toplevel Result step to process
 239          * them.
 240          */
 241         if (constant_quals)
 242         {
 243                 cheapestpath = (Path *) create_result_path(final_rel,
 244                                                                                                    cheapestpath,
 245                                                                                                    constant_quals);
 246                 if (sortedpath)
 247                         sortedpath = (Path *) create_result_path(final_rel,
 248                                                                                                          sortedpath,
 249                                                                                                          constant_quals);
 250         }
 251
 252         *cheapest_path = cheapestpath;
 253         *sorted_path = sortedpath;
 254 }