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  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.48 1999/12/09 05:58:52 tgl Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <sys/types.h>
  15
  16 #include "postgres.h"
  17
  18
  19 #include "optimizer/clauses.h"
  20 #include "optimizer/cost.h"
  21 #include "optimizer/paths.h"
  22 #include "optimizer/planmain.h"
  23 #include "optimizer/prep.h"
  24 #include "optimizer/subselect.h"
  25 #include "optimizer/tlist.h"
  26 #include "utils/lsyscache.h"
  27
  28
  29 static Plan *subplanner(Query *root, List *flat_tlist, List *qual);
  30
  31
  32 /*
  33  * query_planner
  34  *        Routine to create a query plan.  It does so by first creating a
  35  *        subplan for the topmost level of attributes in the query.  Then,
  36  *        it modifies all target list and qualifications to consider the next
  37  *        level of nesting and creates a plan for this modified query by
  38  *        recursively calling itself.  The two pieces are then merged together
  39  *        by creating a result node that indicates which attributes should
  40  *        be placed where and any relation level qualifications to be
  41  *        satisfied.
  42  *
  43  *        tlist is the target list of the query (do NOT use root->targetList!)
  44  *        qual is the qualification of the query (likewise!)
  45  *
  46  *        Note: the Query node now also includes a query_pathkeys field, which
  47  *        is both an input and an output of query_planner().  The input value
  48  *        signals query_planner that the indicated sort order is wanted in the
  49  *        final output plan.  The output value is the actual pathkeys of the
  50  *        selected path.  This might not be the same as what the caller requested;
  51  *        the caller must do pathkeys_contained_in() to decide whether an
  52  *        explicit sort is still needed.  (The main reason query_pathkeys is a
  53  *        Query field and not a passed parameter is that the low-level routines
  54  *        in indxpath.c need to see it.)
  55  *
  56  *        Returns a query plan.
  57  */
  58 Plan *
  59 query_planner(Query *root,
  60                           List *tlist,
  61                           List *qual)
  62 {
  63         List       *constant_qual = NIL;
  64         List       *var_only_tlist;
  65         Plan       *subplan;
  66
  67         /*
  68          * Note: union_planner should already have done constant folding
  69          * in both the tlist and qual, so we don't do it again here
  70          * (indeed, we may be getting a flattened var-only tlist anyway).
  71          *
  72          * Is there any value in re-folding the qual after canonicalize_qual?
  73          */
  74
  75         /*
  76          * Canonicalize the qual, and convert it to implicit-AND format.
  77          */
  78         qual = canonicalize_qual((Expr *) qual, true);
  79 #ifdef OPTIMIZER_DEBUG
  80         printf("After canonicalize_qual()\n");
  81         pprint(qual);
  82 #endif
  83
  84         /* Replace uplevel vars with Param nodes */
  85         if (PlannerQueryLevel > 1)
  86         {
  87                 tlist = (List *) SS_replace_correlation_vars((Node *) tlist);
  88                 qual = (List *) SS_replace_correlation_vars((Node *) qual);
  89         }
  90
  91         /* Expand SubLinks to SubPlans */
  92         if (root->hasSubLinks)
  93         {
  94                 tlist = (List *) SS_process_sublinks((Node *) tlist);
  95                 qual = (List *) SS_process_sublinks((Node *) qual);
  96                 if (root->groupClause != NIL)
  97                 {
  98                         /*
  99                          * Check for ungrouped variables passed to subplans.
 100                          * Note we do NOT do this for subplans in WHERE; it's legal
 101                          * there because WHERE is evaluated pre-GROUP.
 102                          */
 103                         check_subplans_for_ungrouped_vars((Node *) tlist, root, tlist);
 104                 }
 105         }
 106
 107         /*
 108          * If the query contains no relation references at all, it must be
 109          * something like "SELECT 2+2;".  Build a trivial "Result" plan.
 110          */
 111         if (root->rtable == NIL)
 112         {
 113                 /* If it's not a select, it should have had a target relation... */
 114                 if (root->commandType != CMD_SELECT)
 115                         elog(ERROR, "Empty range table for non-SELECT query");
 116
 117                 root->query_pathkeys = NIL; /* signal unordered result */
 118
 119                 /* Make childless Result node to evaluate given tlist. */
 120                 return (Plan *) make_result(tlist, (Node *) qual, (Plan *) NULL);
 121         }
 122
 123         /*
 124          * Pull out any non-variable qual clauses so these can be put in a
 125          * toplevel "Result" node, where they will gate execution of the whole
 126          * plan (the Result will not invoke its descendant plan unless the
 127          * quals are true).  Note that any *really* non-variable quals will
 128          * have been optimized away by eval_const_expressions().  What we're
 129          * mostly interested in here is quals that depend only on outer-level
 130          * vars, although if the qual reduces to "WHERE FALSE" this path will
 131          * also be taken.
 132          */
 133         qual = pull_constant_clauses(qual, &constant_qual);
 134
 135         /*
 136          * Create a target list that consists solely of (resdom var) target
 137          * list entries, i.e., contains no arbitrary expressions.
 138          *
 139          * All subplan nodes will have "flat" (var-only) tlists.
 140          *
 141          * This implies that all expression evaluations are done at the root
 142          * of the 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         var_only_tlist = flatten_tlist(tlist);
 147
 148         /*
 149          * Choose the best access path and build a plan for it.
 150          */
 151         subplan = subplanner(root, var_only_tlist, qual);
 152
 153         /*
 154          * Build a result node to control the plan if we have constant quals.
 155          */
 156         if (constant_qual)
 157         {
 158                 /*
 159                  * The result node will also be responsible for evaluating
 160                  * the originally requested tlist.
 161                  */
 162                 subplan = (Plan *) make_result(tlist,
 163                                                                            (Node *) constant_qual,
 164                                                                            subplan);
 165         }
 166         else
 167         {
 168                 /*
 169                  * Replace the toplevel plan node's flattened target list with the
 170                  * targetlist given by my caller, so that expressions are evaluated.
 171                  */
 172                 subplan->targetlist = tlist;
 173         }
 174
 175         return subplan;
 176
 177 #ifdef NOT_USED
 178
 179         /*
 180          * Destructively modify the query plan's targetlist to add fjoin lists
 181          * to flatten functions that return sets of base types
 182          */
 183         subplan->targetlist = generate_fjoin(subplan->targetlist);
 184 #endif
 185
 186 }
 187
 188 /*
 189  * subplanner
 190  *
 191  *       Subplanner creates an entire plan consisting of joins and scans
 192  *       for processing a single level of attributes.
 193  *
 194  *       flat_tlist is the flattened target list
 195  *       qual is the qualification to be satisfied
 196  *
 197  *       Returns a subplan.
 198  *
 199  */
 200 static Plan *
 201 subplanner(Query *root,
 202                    List *flat_tlist,
 203                    List *qual)
 204 {
 205         RelOptInfo *final_rel;
 206         Cost            cheapest_cost;
 207         Path       *sortedpath;
 208
 209         /*
 210          * Initialize the targetlist and qualification, adding entries to
 211          * base_rel_list as relation references are found (e.g., in the
 212          * qualification, the targetlist, etc.)
 213          */
 214         root->base_rel_list = NIL;
 215         root->join_rel_list = NIL;
 216
 217         make_var_only_tlist(root, flat_tlist);
 218         add_restrict_and_join_to_rels(root, qual);
 219         add_missing_rels_to_query(root);
 220
 221         set_joininfo_mergeable_hashable(root->base_rel_list);
 222
 223         final_rel = make_one_rel(root, root->base_rel_list);
 224
 225         if (! final_rel)
 226         {
 227                 /*
 228                  * We expect to end up here for a trivial INSERT ... VALUES query
 229                  * (which will have a target relation, so it gets past query_planner's
 230                  * check for empty range table; but the target rel is unreferenced
 231                  * and not marked inJoinSet, so we find there is nothing to join).
 232                  *
 233                  * It's also possible to get here if the query was rewritten by the
 234                  * rule processor (creating rangetable entries not marked inJoinSet)
 235                  * but the rules either did nothing or were simplified to nothing
 236                  * by constant-expression folding.  So, don't complain.
 237                  */
 238                 root->query_pathkeys = NIL; /* signal unordered result */
 239
 240                 /* Make childless Result node to evaluate given tlist. */
 241                 return (Plan *) make_result(flat_tlist, (Node *) qual, (Plan *) NULL);
 242         }
 243
 244 #ifdef NOT_USED                                 /* fix xfunc */
 245
 246         /*
 247          * Perform Predicate Migration on each path, to optimize and correctly
 248          * assess the cost of each before choosing the cheapest one. -- JMH,
 249          * 11/16/92
 250          *
 251          * Needn't do so if the top rel is pruneable: that means there's no
 252          * expensive functions left to pull up.  -- JMH, 11/22/92
 253          */
 254         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 255                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 256         {
 257                 List       *pathnode;
 258
 259                 foreach(pathnode, final_rel->pathlist)
 260                 {
 261                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 262                                 set_cheapest(final_rel, final_rel->pathlist);
 263                 }
 264         }
 265 #endif
 266
 267         /*
 268          * Determine the cheapest path and create a subplan to execute it.
 269          *
 270          * If no special sort order is wanted, or if the cheapest path is
 271          * already appropriately ordered, just use the cheapest path.
 272          */
 273         if (root->query_pathkeys == NIL ||
 274                 pathkeys_contained_in(root->query_pathkeys,
 275                                                           final_rel->cheapestpath->pathkeys))
 276         {
 277                 root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 278                 return create_plan(final_rel->cheapestpath);
 279         }
 280
 281         /*
 282          * Otherwise, look to see if we have an already-ordered path that is
 283          * cheaper than doing an explicit sort on cheapestpath.
 284          */
 285         cheapest_cost = final_rel->cheapestpath->path_cost +
 286                 cost_sort(root->query_pathkeys, final_rel->size, final_rel->width);
 287
 288         sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
 289                                                                                                 root->query_pathkeys,
 290                                                                                                 false);
 291         if (sortedpath)
 292         {
 293                 if (sortedpath->path_cost <= cheapest_cost)
 294                 {
 295                         /* Found a better presorted path, use it */
 296                         root->query_pathkeys = sortedpath->pathkeys;
 297                         return create_plan(sortedpath);
 298                 }
 299                 /* otherwise, doing it the hard way is still cheaper */
 300         }
 301         else
 302         {
 303                 /*
 304                  * If we found no usable presorted path at all, it is possible
 305                  * that the user asked for descending sort order.  Check to see
 306                  * if we can satisfy the pathkeys by using a backwards indexscan.
 307                  * To do this, we commute all the operators in the pathkeys and
 308                  * then look for a matching path that is an IndexPath.
 309                  */
 310                 List       *commuted_pathkeys = copyObject(root->query_pathkeys);
 311
 312                 if (commute_pathkeys(commuted_pathkeys))
 313                 {
 314                         /* pass 'true' to force only IndexPaths to be considered */
 315                         sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
 316                                                                                                                 commuted_pathkeys,
 317                                                                                                                 true);
 318                         if (sortedpath && sortedpath->path_cost <= cheapest_cost)
 319                         {
 320                                 /*
 321                                  * Kluge here: since IndexPath has no representation for
 322                                  * backwards scan, we have to convert to Plan format and
 323                                  * then poke the result.
 324                                  */
 325                                 Plan       *sortedplan = create_plan(sortedpath);
 326                                 List       *sortedpathkeys;
 327
 328                                 Assert(IsA(sortedplan, IndexScan));
 329                                 ((IndexScan *) sortedplan)->indxorderdir = BackwardScanDirection;
 330                                 /*
 331                                  * Need to generate commuted keys representing the actual
 332                                  * sort order.  This should succeed, probably, but just in
 333                                  * case it does not, use the original root->query_pathkeys
 334                                  * as a conservative approximation.
 335                                  */
 336                                 sortedpathkeys = copyObject(sortedpath->pathkeys);
 337                                 if (commute_pathkeys(sortedpathkeys))
 338                                         root->query_pathkeys = sortedpathkeys;
 339
 340                                 return sortedplan;
 341                         }
 342                 }
 343         }
 344
 345         /*
 346          * Nothing for it but to sort the cheapestpath --- but we let the
 347          * caller do that.  union_planner has to be able to add a sort node
 348          * anyway, so no need for extra code here.  (Furthermore, the given
 349          * pathkeys might involve something we can't compute here, such as
 350          * an aggregate function...)
 351          */
 352         root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 353         return create_plan(final_rel->cheapestpath);
 354 }