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.46 1999/10/07 04:23:06 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         /* Expand SubLinks to SubPlans */
  91         if (root->hasSubLinks)
  92                 qual = (List *) SS_process_sublinks((Node *) qual);
  93
  94         /*
  95          * If the query contains no relation references at all, it must be
  96          * something like "SELECT 2+2;".  Build a trivial "Result" plan.
  97          */
  98         if (root->rtable == NIL)
  99         {
 100                 /* If it's not a select, it should have had a target relation... */
 101                 if (root->commandType != CMD_SELECT)
 102                         elog(ERROR, "Empty range table for non-SELECT query");
 103
 104                 root->query_pathkeys = NIL; /* signal unordered result */
 105
 106                 /* Make childless Result node to evaluate given tlist. */
 107                 return (Plan *) make_result(tlist, (Node *) qual, (Plan *) NULL);
 108         }
 109
 110         /*
 111          * Pull out any non-variable qual clauses so these can be put in a
 112          * toplevel "Result" node, where they will gate execution of the whole
 113          * plan (the Result will not invoke its descendant plan unless the
 114          * quals are true).  Note that any *really* non-variable quals will
 115          * have been optimized away by eval_const_expressions().  What we're
 116          * mostly interested in here is quals that depend only on outer-level
 117          * vars, although if the qual reduces to "WHERE FALSE" this path will
 118          * also be taken.
 119          */
 120         qual = pull_constant_clauses(qual, &constant_qual);
 121
 122         /*
 123          * Create a target list that consists solely of (resdom var) target
 124          * list entries, i.e., contains no arbitrary expressions.
 125          *
 126          * All subplan nodes will have "flat" (var-only) tlists.
 127          *
 128          * This implies that all expression evaluations are done at the root
 129          * of the plan tree.  Once upon a time there was code to try to push
 130          * expensive function calls down to lower plan nodes, but that's dead
 131          * code and has been for a long time...
 132          */
 133         var_only_tlist = flatten_tlist(tlist);
 134
 135         /*
 136          * Choose the best access path and build a plan for it.
 137          */
 138         subplan = subplanner(root, var_only_tlist, qual);
 139
 140         /*
 141          * Build a result node to control the plan if we have constant quals.
 142          */
 143         if (constant_qual)
 144         {
 145                 /*
 146                  * The result node will also be responsible for evaluating
 147                  * the originally requested tlist.
 148                  */
 149                 subplan = (Plan *) make_result(tlist,
 150                                                                            (Node *) constant_qual,
 151                                                                            subplan);
 152         }
 153         else
 154         {
 155                 /*
 156                  * Replace the toplevel plan node's flattened target list with the
 157                  * targetlist given by my caller, so that expressions are evaluated.
 158                  */
 159                 subplan->targetlist = tlist;
 160         }
 161
 162         return subplan;
 163
 164 #ifdef NOT_USED
 165
 166         /*
 167          * Destructively modify the query plan's targetlist to add fjoin lists
 168          * to flatten functions that return sets of base types
 169          */
 170         subplan->targetlist = generate_fjoin(subplan->targetlist);
 171 #endif
 172
 173 }
 174
 175 /*
 176  * subplanner
 177  *
 178  *       Subplanner creates an entire plan consisting of joins and scans
 179  *       for processing a single level of attributes.
 180  *
 181  *       flat_tlist is the flattened target list
 182  *       qual is the qualification to be satisfied
 183  *
 184  *       Returns a subplan.
 185  *
 186  */
 187 static Plan *
 188 subplanner(Query *root,
 189                    List *flat_tlist,
 190                    List *qual)
 191 {
 192         RelOptInfo *final_rel;
 193         Cost            cheapest_cost;
 194         Path       *sortedpath;
 195
 196         /*
 197          * Initialize the targetlist and qualification, adding entries to
 198          * base_rel_list as relation references are found (e.g., in the
 199          * qualification, the targetlist, etc.)
 200          */
 201         root->base_rel_list = NIL;
 202         root->join_rel_list = NIL;
 203
 204         make_var_only_tlist(root, flat_tlist);
 205         add_restrict_and_join_to_rels(root, qual);
 206         add_missing_rels_to_query(root);
 207
 208         set_joininfo_mergeable_hashable(root->base_rel_list);
 209
 210         final_rel = make_one_rel(root, root->base_rel_list);
 211
 212         if (! final_rel)
 213         {
 214                 /*
 215                  * We expect to end up here for a trivial INSERT ... VALUES query
 216                  * (which will have a target relation, so it gets past query_planner's
 217                  * check for empty range table; but the target rel is unreferenced
 218                  * and not marked inJoinSet, so we find there is nothing to join).
 219                  *
 220                  * It's also possible to get here if the query was rewritten by the
 221                  * rule processor (creating rangetable entries not marked inJoinSet)
 222                  * but the rules either did nothing or were simplified to nothing
 223                  * by constant-expression folding.  So, don't complain.
 224                  */
 225                 root->query_pathkeys = NIL; /* signal unordered result */
 226
 227                 /* Make childless Result node to evaluate given tlist. */
 228                 return (Plan *) make_result(flat_tlist, (Node *) qual, (Plan *) NULL);
 229         }
 230
 231 #ifdef NOT_USED                                 /* fix xfunc */
 232
 233         /*
 234          * Perform Predicate Migration on each path, to optimize and correctly
 235          * assess the cost of each before choosing the cheapest one. -- JMH,
 236          * 11/16/92
 237          *
 238          * Needn't do so if the top rel is pruneable: that means there's no
 239          * expensive functions left to pull up.  -- JMH, 11/22/92
 240          */
 241         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 242                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 243         {
 244                 List       *pathnode;
 245
 246                 foreach(pathnode, final_rel->pathlist)
 247                 {
 248                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 249                                 set_cheapest(final_rel, final_rel->pathlist);
 250                 }
 251         }
 252 #endif
 253
 254         /*
 255          * Determine the cheapest path and create a subplan to execute it.
 256          *
 257          * If no special sort order is wanted, or if the cheapest path is
 258          * already appropriately ordered, just use the cheapest path.
 259          */
 260         if (root->query_pathkeys == NIL ||
 261                 pathkeys_contained_in(root->query_pathkeys,
 262                                                           final_rel->cheapestpath->pathkeys))
 263         {
 264                 root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 265                 return create_plan(final_rel->cheapestpath);
 266         }
 267
 268         /*
 269          * Otherwise, look to see if we have an already-ordered path that is
 270          * cheaper than doing an explicit sort on cheapestpath.
 271          */
 272         cheapest_cost = final_rel->cheapestpath->path_cost +
 273                 cost_sort(root->query_pathkeys, final_rel->size, final_rel->width);
 274
 275         sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
 276                                                                                                 root->query_pathkeys,
 277                                                                                                 false);
 278         if (sortedpath)
 279         {
 280                 if (sortedpath->path_cost <= cheapest_cost)
 281                 {
 282                         /* Found a better presorted path, use it */
 283                         root->query_pathkeys = sortedpath->pathkeys;
 284                         return create_plan(sortedpath);
 285                 }
 286                 /* otherwise, doing it the hard way is still cheaper */
 287         }
 288         else
 289         {
 290                 /*
 291                  * If we found no usable presorted path at all, it is possible
 292                  * that the user asked for descending sort order.  Check to see
 293                  * if we can satisfy the pathkeys by using a backwards indexscan.
 294                  * To do this, we commute all the operators in the pathkeys and
 295                  * then look for a matching path that is an IndexPath.
 296                  */
 297                 List       *commuted_pathkeys = copyObject(root->query_pathkeys);
 298
 299                 if (commute_pathkeys(commuted_pathkeys))
 300                 {
 301                         /* pass 'true' to force only IndexPaths to be considered */
 302                         sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
 303                                                                                                                 commuted_pathkeys,
 304                                                                                                                 true);
 305                         if (sortedpath && sortedpath->path_cost <= cheapest_cost)
 306                         {
 307                                 /*
 308                                  * Kluge here: since IndexPath has no representation for
 309                                  * backwards scan, we have to convert to Plan format and
 310                                  * then poke the result.
 311                                  */
 312                                 Plan       *sortedplan = create_plan(sortedpath);
 313                                 List       *sortedpathkeys;
 314
 315                                 Assert(IsA(sortedplan, IndexScan));
 316                                 ((IndexScan *) sortedplan)->indxorderdir = BackwardScanDirection;
 317                                 /*
 318                                  * Need to generate commuted keys representing the actual
 319                                  * sort order.  This should succeed, probably, but just in
 320                                  * case it does not, use the original root->query_pathkeys
 321                                  * as a conservative approximation.
 322                                  */
 323                                 sortedpathkeys = copyObject(sortedpath->pathkeys);
 324                                 if (commute_pathkeys(sortedpathkeys))
 325                                         root->query_pathkeys = sortedpathkeys;
 326
 327                                 return sortedplan;
 328                         }
 329                 }
 330         }
 331
 332         /*
 333          * Nothing for it but to sort the cheapestpath --- but we let the
 334          * caller do that.  union_planner has to be able to add a sort node
 335          * anyway, so no need for extra code here.  (Furthermore, the given
 336          * pathkeys might involve something we can't compute here, such as
 337          * an aggregate function...)
 338          */
 339         root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 340         return create_plan(final_rel->cheapestpath);
 341 }