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.59 2000/09/12 21:06:54 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 #include "parser/parsetree.h"
  32 #include "utils/memutils.h"
  33
  34
  35 static Plan *subplanner(Query *root, List *flat_tlist, List *qual,
  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, union_planner has a different interpretation.
  69  *
  70  * Returns a query plan.
  71  *--------------------
  72  */
  73 Plan *
  74 query_planner(Query *root,
  75                           List *tlist,
  76                           double tuple_fraction)
  77 {
  78         List       *normal_qual;
  79         List       *noncachable_qual;
  80         List       *constant_qual;
  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, root->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.  We also need a special case for quals that contain
 109          * noncachable functions but no vars, such as "WHERE random() < 0.5".
 110          * These cannot be treated as normal restriction or join quals, but
 111          * they're not constants either.  Instead, attach them to the qpqual
 112          * of the top plan, so that they get evaluated once per potential
 113          * output tuple.
 114          */
 115         normal_qual = pull_constant_clauses((List *) root->qual,
 116                                                                                 &noncachable_qual,
 117                                                                                 &constant_qual);
 118
 119         /*
 120          * Create a target list that consists solely of (resdom var) target
 121          * list entries, i.e., contains no arbitrary expressions.
 122          *
 123          * All subplan nodes will have "flat" (var-only) tlists.
 124          *
 125          * This implies that all expression evaluations are done at the root of
 126          * the plan tree.  Once upon a time there was code to try to push
 127          * expensive function calls down to lower plan nodes, but that's dead
 128          * code and has been for a long time...
 129          */
 130         var_only_tlist = flatten_tlist(tlist);
 131
 132         /*
 133          * Choose the best access path and build a plan for it.
 134          */
 135         subplan = subplanner(root, var_only_tlist, normal_qual, tuple_fraction);
 136
 137         /*
 138          * Handle the noncachable quals.
 139          */
 140         if (noncachable_qual)
 141                 subplan->qual = nconc(subplan->qual, noncachable_qual);
 142
 143         /*
 144          * Build a result node to control the plan if we have constant quals.
 145          */
 146         if (constant_qual)
 147         {
 148
 149                 /*
 150                  * The result node will also be responsible for evaluating the
 151                  * originally requested tlist.
 152                  */
 153                 subplan = (Plan *) make_result(tlist,
 154                                                                            (Node *) constant_qual,
 155                                                                            subplan);
 156         }
 157         else
 158         {
 159
 160                 /*
 161                  * Replace the toplevel plan node's flattened target list with the
 162                  * targetlist given by my caller, so that expressions are
 163                  * evaluated.
 164                  */
 165                 subplan->targetlist = tlist;
 166         }
 167
 168         return subplan;
 169 }
 170
 171 /*
 172  * subplanner
 173  *
 174  *       Subplanner creates an entire plan consisting of joins and scans
 175  *       for processing a single level of attributes.
 176  *
 177  * flat_tlist is the flattened target list
 178  * qual is the qualification to be satisfied (restrict and join quals only)
 179  * tuple_fraction is the fraction of tuples we expect will be retrieved
 180  *
 181  * See query_planner() comments about the interpretation of tuple_fraction.
 182  *
 183  * Returns a subplan.
 184  */
 185 static Plan *
 186 subplanner(Query *root,
 187                    List *flat_tlist,
 188                    List *qual,
 189                    double tuple_fraction)
 190 {
 191         List       *joined_rels;
 192         List       *brel;
 193         RelOptInfo *final_rel;
 194         Plan       *resultplan;
 195         MemoryContext mycontext;
 196         MemoryContext oldcxt;
 197         Path       *cheapestpath;
 198         Path       *presortedpath;
 199
 200         /*
 201          * Examine the targetlist and qualifications, adding entries to
 202          * base_rel_list as relation references are found (e.g., in the
 203          * qualification, the targetlist, etc.).  Restrict and join clauses
 204          * are added to appropriate lists belonging to the mentioned
 205          * relations.  We also build lists of equijoined keys for pathkey
 206          * construction.
 207          */
 208         root->base_rel_list = NIL;
 209         root->join_rel_list = NIL;
 210         root->equi_key_list = NIL;
 211
 212         build_base_rel_tlists(root, flat_tlist);
 213         (void) add_join_quals_to_rels(root, (Node *) root->jointree);
 214         /* this must happen after add_join_quals_to_rels: */
 215         add_restrict_and_join_to_rels(root, qual);
 216
 217         /*
 218          * Make sure we have RelOptInfo nodes for all relations to be joined.
 219          */
 220         joined_rels = add_missing_rels_to_query(root, (Node *) root->jointree);
 221
 222         /*
 223          * Check that the join tree includes all the base relations used in
 224          * the query --- otherwise, the parser or rewriter messed up.
 225          */
 226         foreach(brel, root->base_rel_list)
 227         {
 228                 RelOptInfo *baserel = (RelOptInfo *) lfirst(brel);
 229                 int             relid = lfirsti(baserel->relids);
 230
 231                 if (! ptrMember(baserel, joined_rels))
 232                         elog(ERROR, "Internal error: no jointree entry for rel %s (%d)",
 233                                  rt_fetch(relid, root->rtable)->eref->relname, relid);
 234         }
 235
 236         /*
 237          * Use the completed lists of equijoined keys to deduce any implied
 238          * but unstated equalities (for example, A=B and B=C imply A=C).
 239          */
 240         generate_implied_equalities(root);
 241
 242         /*
 243          * We should now have all the pathkey equivalence sets built, so it's
 244          * now possible to convert the requested query_pathkeys to canonical
 245          * form.
 246          */
 247         root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 248
 249         /*
 250          * We might allocate quite a lot of storage during planning (due to
 251          * constructing lots of Paths), but all of it can be reclaimed after
 252          * we generate the finished Plan tree.  Work in a temporary context
 253          * to let that happen.  We make the context a child of
 254          * TransactionCommandContext so it will be freed if error abort.
 255          *
 256          * Note: beware of trying to move this up to the start of this routine.
 257          * Some of the data structures built above --- notably the pathkey
 258          * equivalence sets --- will still be needed after this routine exits.
 259          */
 260         mycontext = AllocSetContextCreate(TransactionCommandContext,
 261                                                                           "Planner",
 262                                                                           ALLOCSET_DEFAULT_MINSIZE,
 263                                                                           ALLOCSET_DEFAULT_INITSIZE,
 264                                                                           ALLOCSET_DEFAULT_MAXSIZE);
 265         oldcxt = MemoryContextSwitchTo(mycontext);
 266
 267         /*
 268          * Ready to do the primary planning.
 269          */
 270         final_rel = make_one_rel(root);
 271
 272         if (!final_rel)
 273         {
 274
 275                 /*
 276                  * We expect to end up here for a trivial INSERT ... VALUES query
 277                  * (which will have a target relation, so it gets past
 278                  * query_planner's check for empty range table; but the target rel
 279                  * is not in the join tree, so we find there is nothing to join).
 280                  *
 281                  * It's also possible to get here if the query was rewritten by the
 282                  * rule processor (creating dummy rangetable entries that are not in
 283                  * the join tree) but the rules either did nothing or were simplified
 284                  * to nothing by constant-expression folding.  So, don't complain.
 285                  */
 286                 root->query_pathkeys = NIL;             /* signal unordered result */
 287
 288                 /* Make childless Result node to evaluate given tlist. */
 289                 resultplan = (Plan *) make_result(flat_tlist, (Node *) qual,
 290                                                                                   (Plan *) NULL);
 291                 goto plan_built;
 292         }
 293
 294 #ifdef NOT_USED                                 /* fix xfunc */
 295
 296         /*
 297          * Perform Predicate Migration on each path, to optimize and correctly
 298          * assess the cost of each before choosing the cheapest one. -- JMH,
 299          * 11/16/92
 300          *
 301          * Needn't do so if the top rel is pruneable: that means there's no
 302          * expensive functions left to pull up.  -- JMH, 11/22/92
 303          */
 304         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 305                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 306         {
 307                 List       *pathnode;
 308
 309                 foreach(pathnode, final_rel->pathlist)
 310                 {
 311                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 312                                 set_cheapest(final_rel);
 313                 }
 314         }
 315 #endif
 316
 317         /*
 318          * Now that we have an estimate of the final rel's size, we can
 319          * convert a tuple_fraction specified as an absolute count (ie, a
 320          * LIMIT option) into a fraction of the total tuples.
 321          */
 322         if (tuple_fraction >= 1.0)
 323                 tuple_fraction /= final_rel->rows;
 324
 325         /*
 326          * Determine the cheapest path, independently of any ordering
 327          * considerations.      We do, however, take into account whether the
 328          * whole plan is expected to be evaluated or not.
 329          */
 330         if (tuple_fraction <= 0.0 || tuple_fraction >= 1.0)
 331                 cheapestpath = final_rel->cheapest_total_path;
 332         else
 333                 cheapestpath =
 334                         get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 335                                                                                                           NIL,
 336                                                                                                           tuple_fraction);
 337
 338         Assert(cheapestpath != NULL);
 339
 340         /*
 341          * Select the best path and create a subplan to execute it.
 342          *
 343          * If no special sort order is wanted, or if the cheapest path is already
 344          * appropriately ordered, we use the cheapest path found above.
 345          */
 346         if (root->query_pathkeys == NIL ||
 347                 pathkeys_contained_in(root->query_pathkeys,
 348                                                           cheapestpath->pathkeys))
 349         {
 350                 root->query_pathkeys = cheapestpath->pathkeys;
 351                 resultplan = create_plan(root, cheapestpath);
 352                 goto plan_built;
 353         }
 354
 355         /*
 356          * Otherwise, look to see if we have an already-ordered path that is
 357          * cheaper than doing an explicit sort on the cheapest-total-cost
 358          * path.
 359          */
 360         cheapestpath = final_rel->cheapest_total_path;
 361         presortedpath =
 362                 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 363                                                                                                   root->query_pathkeys,
 364                                                                                                   tuple_fraction);
 365         if (presortedpath)
 366         {
 367                 Path            sort_path;      /* dummy for result of cost_sort */
 368
 369                 cost_sort(&sort_path, root->query_pathkeys,
 370                                   final_rel->rows, final_rel->width);
 371                 sort_path.startup_cost += cheapestpath->total_cost;
 372                 sort_path.total_cost += cheapestpath->total_cost;
 373                 if (compare_fractional_path_costs(presortedpath, &sort_path,
 374                                                                                   tuple_fraction) <= 0)
 375                 {
 376                         /* Presorted path is cheaper, use it */
 377                         root->query_pathkeys = presortedpath->pathkeys;
 378                         resultplan = create_plan(root, presortedpath);
 379                         goto plan_built;
 380                 }
 381                 /* otherwise, doing it the hard way is still cheaper */
 382         }
 383
 384         /*
 385          * Nothing for it but to sort the cheapest-total-cost path --- but we
 386          * let the caller do that.      union_planner has to be able to add a sort
 387          * node anyway, so no need for extra code here.  (Furthermore, the
 388          * given pathkeys might involve something we can't compute here, such
 389          * as an aggregate function...)
 390          */
 391         root->query_pathkeys = cheapestpath->pathkeys;
 392         resultplan = create_plan(root, cheapestpath);
 393
 394 plan_built:
 395
 396         /*
 397          * Must copy the completed plan tree and its pathkeys out of temporary
 398          * context.
 399          */
 400         MemoryContextSwitchTo(oldcxt);
 401
 402         resultplan = copyObject(resultplan);
 403
 404         root->query_pathkeys = copyObject(root->query_pathkeys);
 405
 406         /*
 407          * Now we can release the Path storage.
 408          */
 409         MemoryContextDelete(mycontext);
 410
 411         return resultplan;
 412 }