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-2000, PostgreSQL, Inc
  13  * Portions Copyright (c) 1994, Regents of the University of California
  14  *
  15  *
  16  * IDENTIFICATION
  17  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.56 2000/07/24 03:11:01 tgl Exp $
  18  *
  19  *-------------------------------------------------------------------------
  20  */
  21 #include "postgres.h"
  22
  23 #include <sys/types.h>
  24
  25 #include "optimizer/clauses.h"
  26 #include "optimizer/cost.h"
  27 #include "optimizer/pathnode.h"
  28 #include "optimizer/paths.h"
  29 #include "optimizer/planmain.h"
  30 #include "optimizer/tlist.h"
  31
  32
  33 static Plan *subplanner(Query *root, List *flat_tlist, List *qual,
  34                    double tuple_fraction);
  35
  36
  37 /*--------------------
  38  * query_planner
  39  *        Generate a plan for a basic query, which may involve joins but
  40  *        not any fancier features.
  41  *
  42  * tlist is the target list the query should produce (NOT root->targetList!)
  43  * qual is the qualification of the query (likewise!)
  44  * tuple_fraction is the fraction of tuples we expect will be retrieved
  45  *
  46  * qual must already have been converted to implicit-AND form.
  47  *
  48  * Note: the Query node now also includes a query_pathkeys field, which
  49  * is both an input and an output of query_planner().  The input value
  50  * signals query_planner that the indicated sort order is wanted in the
  51  * final output plan.  The output value is the actual pathkeys of the
  52  * selected path.  This might not be the same as what the caller requested;
  53  * the caller must do pathkeys_contained_in() to decide whether an
  54  * explicit sort is still needed.  (The main reason query_pathkeys is a
  55  * Query field and not a passed parameter is that the low-level routines
  56  * in indxpath.c need to see it.)  The pathkeys value passed to query_planner
  57  * has not yet been "canonicalized", since the necessary info does not get
  58  * computed until subplanner() scans the qual clauses.  We canonicalize it
  59  * inside subplanner() as soon as that task is done.  The output value
  60  * will be in canonical form as well.
  61  *
  62  * tuple_fraction is interpreted as follows:
  63  *        0 (or less): expect all tuples to be retrieved (normal case)
  64  *        0 < tuple_fraction < 1: expect the given fraction of tuples available
  65  *              from the plan to be retrieved
  66  *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
  67  *              expected to be retrieved (ie, a LIMIT specification)
  68  * Note that while this routine and its subroutines treat a negative
  69  * tuple_fraction the same as 0, union_planner has a different interpretation.
  70  *
  71  * Returns a query plan.
  72  *--------------------
  73  */
  74 Plan *
  75 query_planner(Query *root,
  76                           List *tlist,
  77                           List *qual,
  78                           double tuple_fraction)
  79 {
  80         List       *constant_qual = NIL;
  81         List       *var_only_tlist;
  82         Plan       *subplan;
  83
  84         /*
  85          * If the query contains no relation references at all, it must be
  86          * something like "SELECT 2+2;".  Build a trivial "Result" plan.
  87          */
  88         if (root->rtable == NIL)
  89         {
  90                 /* If it's not a select, it should have had a target relation... */
  91                 if (root->commandType != CMD_SELECT)
  92                         elog(ERROR, "Empty range table for non-SELECT query");
  93
  94                 root->query_pathkeys = NIL;             /* signal unordered result */
  95
  96                 /* Make childless Result node to evaluate given tlist. */
  97                 return (Plan *) make_result(tlist, (Node *) qual, (Plan *) NULL);
  98         }
  99
 100         /*
 101          * Pull out any non-variable qual clauses so these can be put in a
 102          * toplevel "Result" node, where they will gate execution of the whole
 103          * plan (the Result will not invoke its descendant plan unless the
 104          * quals are true).  Note that any *really* non-variable quals will
 105          * have been optimized away by eval_const_expressions().  What we're
 106          * mostly interested in here is quals that depend only on outer-level
 107          * vars, although if the qual reduces to "WHERE FALSE" this path will
 108          * also be taken.
 109          */
 110         qual = pull_constant_clauses(qual, &constant_qual);
 111
 112         /*
 113          * Create a target list that consists solely of (resdom var) target
 114          * list entries, i.e., contains no arbitrary expressions.
 115          *
 116          * All subplan nodes will have "flat" (var-only) tlists.
 117          *
 118          * This implies that all expression evaluations are done at the root of
 119          * the plan tree.  Once upon a time there was code to try to push
 120          * expensive function calls down to lower plan nodes, but that's dead
 121          * code and has been for a long time...
 122          */
 123         var_only_tlist = flatten_tlist(tlist);
 124
 125         /*
 126          * Choose the best access path and build a plan for it.
 127          */
 128         subplan = subplanner(root, var_only_tlist, qual, tuple_fraction);
 129
 130         /*
 131          * Build a result node to control the plan if we have constant quals.
 132          */
 133         if (constant_qual)
 134         {
 135
 136                 /*
 137                  * The result node will also be responsible for evaluating the
 138                  * originally requested tlist.
 139                  */
 140                 subplan = (Plan *) make_result(tlist,
 141                                                                            (Node *) constant_qual,
 142                                                                            subplan);
 143         }
 144         else
 145         {
 146
 147                 /*
 148                  * Replace the toplevel plan node's flattened target list with the
 149                  * targetlist given by my caller, so that expressions are
 150                  * evaluated.
 151                  */
 152                 subplan->targetlist = tlist;
 153         }
 154
 155         return subplan;
 156 }
 157
 158 /*
 159  * subplanner
 160  *
 161  *       Subplanner creates an entire plan consisting of joins and scans
 162  *       for processing a single level of attributes.
 163  *
 164  * flat_tlist is the flattened target list
 165  * qual is the qualification to be satisfied
 166  * tuple_fraction is the fraction of tuples we expect will be retrieved
 167  *
 168  * See query_planner() comments about the interpretation of tuple_fraction.
 169  *
 170  * Returns a subplan.
 171  */
 172 static Plan *
 173 subplanner(Query *root,
 174                    List *flat_tlist,
 175                    List *qual,
 176                    double tuple_fraction)
 177 {
 178         RelOptInfo *final_rel;
 179         Path       *cheapestpath;
 180         Path       *presortedpath;
 181
 182         /*
 183          * Initialize the targetlist and qualification, adding entries to
 184          * base_rel_list as relation references are found (e.g., in the
 185          * qualification, the targetlist, etc.).  Restrict and join clauses
 186          * are added to appropriate lists belonging to the mentioned
 187          * relations.  We also build lists of equijoined keys for pathkey
 188          * construction.
 189          */
 190         root->base_rel_list = NIL;
 191         root->join_rel_list = NIL;
 192         root->equi_key_list = NIL;
 193
 194         make_var_only_tlist(root, flat_tlist);
 195         add_restrict_and_join_to_rels(root, qual);
 196
 197         /*
 198          * Make sure we have RelOptInfo nodes for all relations used.
 199          */
 200         add_missing_rels_to_query(root);
 201
 202         /*
 203          * Use the completed lists of equijoined keys to deduce any implied
 204          * but unstated equalities (for example, A=B and B=C imply A=C).
 205          */
 206         generate_implied_equalities(root);
 207
 208         /*
 209          * We should now have all the pathkey equivalence sets built, so it's
 210          * now possible to convert the requested query_pathkeys to canonical
 211          * form.
 212          */
 213         root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 214
 215         /*
 216          * Ready to do the primary planning.
 217          */
 218         final_rel = make_one_rel(root);
 219
 220         if (!final_rel)
 221         {
 222
 223                 /*
 224                  * We expect to end up here for a trivial INSERT ... VALUES query
 225                  * (which will have a target relation, so it gets past
 226                  * query_planner's check for empty range table; but the target rel
 227                  * is unreferenced and not marked inJoinSet, so we find there is
 228                  * nothing to join).
 229                  *
 230                  * It's also possible to get here if the query was rewritten by the
 231                  * rule processor (creating rangetable entries not marked
 232                  * inJoinSet) but the rules either did nothing or were simplified
 233                  * to nothing by constant-expression folding.  So, don't complain.
 234                  */
 235                 root->query_pathkeys = NIL;             /* signal unordered result */
 236
 237                 /* Make childless Result node to evaluate given tlist. */
 238                 return (Plan *) make_result(flat_tlist, (Node *) qual, (Plan *) NULL);
 239         }
 240
 241 #ifdef NOT_USED                                 /* fix xfunc */
 242
 243         /*
 244          * Perform Predicate Migration on each path, to optimize and correctly
 245          * assess the cost of each before choosing the cheapest one. -- JMH,
 246          * 11/16/92
 247          *
 248          * Needn't do so if the top rel is pruneable: that means there's no
 249          * expensive functions left to pull up.  -- JMH, 11/22/92
 250          */
 251         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 252                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 253         {
 254                 List       *pathnode;
 255
 256                 foreach(pathnode, final_rel->pathlist)
 257                 {
 258                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 259                                 set_cheapest(final_rel);
 260                 }
 261         }
 262 #endif
 263
 264         /*
 265          * Now that we have an estimate of the final rel's size, we can
 266          * convert a tuple_fraction specified as an absolute count (ie, a
 267          * LIMIT option) into a fraction of the total tuples.
 268          */
 269         if (tuple_fraction >= 1.0)
 270                 tuple_fraction /= final_rel->rows;
 271
 272         /*
 273          * Determine the cheapest path, independently of any ordering
 274          * considerations.      We do, however, take into account whether the
 275          * whole plan is expected to be evaluated or not.
 276          */
 277         if (tuple_fraction <= 0.0 || tuple_fraction >= 1.0)
 278                 cheapestpath = final_rel->cheapest_total_path;
 279         else
 280                 cheapestpath =
 281                         get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 282                                                                                                           NIL,
 283                                                                                                           tuple_fraction);
 284
 285         Assert(cheapestpath != NULL);
 286
 287         /*
 288          * Select the best path and create a subplan to execute it.
 289          *
 290          * If no special sort order is wanted, or if the cheapest path is already
 291          * appropriately ordered, we use the cheapest path found above.
 292          */
 293         if (root->query_pathkeys == NIL ||
 294                 pathkeys_contained_in(root->query_pathkeys,
 295                                                           cheapestpath->pathkeys))
 296         {
 297                 root->query_pathkeys = cheapestpath->pathkeys;
 298                 return create_plan(root, cheapestpath);
 299         }
 300
 301         /*
 302          * Otherwise, look to see if we have an already-ordered path that is
 303          * cheaper than doing an explicit sort on the cheapest-total-cost
 304          * path.
 305          */
 306         cheapestpath = final_rel->cheapest_total_path;
 307         presortedpath =
 308                 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 309                                                                                                   root->query_pathkeys,
 310                                                                                                   tuple_fraction);
 311         if (presortedpath)
 312         {
 313                 Path            sort_path;      /* dummy for result of cost_sort */
 314
 315                 cost_sort(&sort_path, root->query_pathkeys,
 316                                   final_rel->rows, final_rel->width);
 317                 sort_path.startup_cost += cheapestpath->total_cost;
 318                 sort_path.total_cost += cheapestpath->total_cost;
 319                 if (compare_fractional_path_costs(presortedpath, &sort_path,
 320                                                                                   tuple_fraction) <= 0)
 321                 {
 322                         /* Presorted path is cheaper, use it */
 323                         root->query_pathkeys = presortedpath->pathkeys;
 324                         return create_plan(root, presortedpath);
 325                 }
 326                 /* otherwise, doing it the hard way is still cheaper */
 327         }
 328
 329         /*
 330          * Nothing for it but to sort the cheapest-total-cost path --- but we
 331          * let the caller do that.      union_planner has to be able to add a sort
 332          * node anyway, so no need for extra code here.  (Furthermore, the
 333          * given pathkeys might involve something we can't compute here, such
 334          * as an aggregate function...)
 335          */
 336         root->query_pathkeys = cheapestpath->pathkeys;
 337         return create_plan(root, cheapestpath);
 338 }