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