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.44 1999/09/13 00:17:25 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  * query_planner
  33  *        Routine to create a query plan.  It does so by first creating a
  34  *        subplan for the topmost level of attributes in the query.  Then,
  35  *        it modifies all target list and qualifications to consider the next
  36  *        level of nesting and creates a plan for this modified query by
  37  *        recursively calling itself.  The two pieces are then merged together
  38  *        by creating a result node that indicates which attributes should
  39  *        be placed where and any relation level qualifications to be
  40  *        satisfied.
  41  *
  42  *        command-type is the query command, e.g., select, delete, etc.
  43  *        tlist is the target list of the query
  44  *        qual is the qualification of the query
  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                           int command_type,
  61                           List *tlist,
  62                           List *qual)
  63 {
  64         List       *constant_qual = NIL;
  65         List       *var_only_tlist;
  66         List       *level_tlist;
  67         Plan       *subplan;
  68
  69         if (PlannerQueryLevel > 1)
  70         {
  71                 /* should copy be made ? */
  72                 tlist = (List *) SS_replace_correlation_vars((Node *) tlist);
  73                 qual = (List *) SS_replace_correlation_vars((Node *) qual);
  74         }
  75         if (root->hasSubLinks)
  76                 qual = (List *) SS_process_sublinks((Node *) qual);
  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         /*
  85          * Pull out any non-variable qualifications so these can be put in the
  86          * topmost result node.
  87          */
  88         qual = pull_constant_clauses(qual, &constant_qual);
  89
  90         /*
  91          * Create a target list that consists solely of (resdom var) target
  92          * list entries, i.e., contains no arbitrary expressions.
  93          */
  94         var_only_tlist = flatten_tlist(tlist);
  95         if (var_only_tlist)
  96                 level_tlist = var_only_tlist;
  97         else
  98                 /* from old code. the logic is beyond me. - ay 2/95 */
  99                 level_tlist = tlist;
 100
 101         /*
 102          * A query may have a non-variable target list and a non-variable
 103          * qualification only under certain conditions: - the query creates
 104          * all-new tuples, or - the query is a replace (a scan must still be
 105          * done in this case).
 106          */
 107         if (var_only_tlist == NULL && qual == NULL)
 108         {
 109                 root->query_pathkeys = NIL; /* these plans make unordered results */
 110
 111                 switch (command_type)
 112                 {
 113                         case CMD_SELECT:
 114                         case CMD_INSERT:
 115                                 return ((Plan *) make_result(tlist,
 116                                                                                          (Node *) constant_qual,
 117                                                                                          (Plan *) NULL));
 118                                 break;
 119                         case CMD_DELETE:
 120                         case CMD_UPDATE:
 121                                 {
 122                                         SeqScan    *scan = make_seqscan(tlist,
 123                                                                                                         NIL,
 124                                                                                                         root->resultRelation);
 125
 126                                         if (constant_qual != NULL)
 127                                                 return ((Plan *) make_result(tlist,
 128                                                                                                          (Node *) constant_qual,
 129                                                                                                          (Plan *) scan));
 130                                         else
 131                                                 return (Plan *) scan;
 132                                 }
 133                                 break;
 134                         default:
 135                                 return (Plan *) NULL;
 136                 }
 137         }
 138
 139         /*
 140          * Choose the best access path and build a plan for it.
 141          */
 142         subplan = subplanner(root, level_tlist, qual);
 143
 144         /*
 145          * Build a result node linking the plan if we have constant quals
 146          */
 147         if (constant_qual)
 148         {
 149                 subplan = (Plan *) make_result(tlist,
 150                                                                            (Node *) constant_qual,
 151                                                                            subplan);
 152
 153                 root->query_pathkeys = NIL; /* result is unordered, no? */
 154
 155                 return subplan;
 156         }
 157
 158         /*
 159          * Replace the toplevel plan node's flattened target list with the
 160          * targetlist given by my caller, so that expressions are evaluated.
 161          *
 162          * This implies that all expression evaluations are done at the root
 163          * of the plan tree.  Once upon a time there was code to try to push
 164          * expensive function calls down to lower plan nodes, but that's dead
 165          * code and has been for a long time...
 166          */
 167         else
 168         {
 169                 subplan->targetlist = tlist;
 170
 171                 return subplan;
 172         }
 173
 174 #ifdef NOT_USED
 175
 176         /*
 177          * Destructively modify the query plan's targetlist to add fjoin lists
 178          * to flatten functions that return sets of base types
 179          */
 180         subplan->targetlist = generate_fjoin(subplan->targetlist);
 181 #endif
 182
 183 }
 184
 185 /*
 186  * subplanner
 187  *
 188  *       Subplanner creates an entire plan consisting of joins and scans
 189  *       for processing a single level of attributes.
 190  *
 191  *       flat_tlist is the flattened target list
 192  *       qual is the qualification to be satisfied
 193  *
 194  *       Returns a subplan.
 195  *
 196  */
 197 static Plan *
 198 subplanner(Query *root,
 199                    List *flat_tlist,
 200                    List *qual)
 201 {
 202         RelOptInfo *final_rel;
 203         Cost            cheapest_cost;
 204         Path       *sortedpath;
 205
 206         /*
 207          * Initialize the targetlist and qualification, adding entries to
 208          * base_rel_list as relation references are found (e.g., in the
 209          * qualification, the targetlist, etc.)
 210          */
 211         root->base_rel_list = NIL;
 212         root->join_rel_list = NIL;
 213
 214         make_var_only_tlist(root, flat_tlist);
 215         add_restrict_and_join_to_rels(root, qual);
 216         add_missing_vars_to_tlist(root, flat_tlist);
 217
 218         set_joininfo_mergeable_hashable(root->base_rel_list);
 219
 220         final_rel = make_one_rel(root, root->base_rel_list);
 221
 222 #ifdef NOT_USED                                 /* fix xfunc */
 223
 224         /*
 225          * Perform Predicate Migration on each path, to optimize and correctly
 226          * assess the cost of each before choosing the cheapest one. -- JMH,
 227          * 11/16/92
 228          *
 229          * Needn't do so if the top rel is pruneable: that means there's no
 230          * expensive functions left to pull up.  -- JMH, 11/22/92
 231          */
 232         if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
 233                 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
 234         {
 235                 List       *pathnode;
 236
 237                 foreach(pathnode, final_rel->pathlist)
 238                 {
 239                         if (xfunc_do_predmig((Path *) lfirst(pathnode)))
 240                                 set_cheapest(final_rel, final_rel->pathlist);
 241                 }
 242         }
 243 #endif
 244
 245         if (! final_rel)
 246         {
 247                 elog(NOTICE, "final relation is null");
 248                 root->query_pathkeys = NIL; /* result is unordered, no? */
 249                 return create_plan((Path *) NULL);
 250         }
 251
 252         /*
 253          * Determine the cheapest path and create a subplan to execute it.
 254          *
 255          * If no special sort order is wanted, or if the cheapest path is
 256          * already appropriately ordered, just use the cheapest path.
 257          */
 258         if (root->query_pathkeys == NIL ||
 259                 pathkeys_contained_in(root->query_pathkeys,
 260                                                           final_rel->cheapestpath->pathkeys))
 261         {
 262                 root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 263                 return create_plan(final_rel->cheapestpath);
 264         }
 265
 266         /*
 267          * Otherwise, look to see if we have an already-ordered path that is
 268          * cheaper than doing an explicit sort on cheapestpath.
 269          */
 270         cheapest_cost = final_rel->cheapestpath->path_cost +
 271                 cost_sort(root->query_pathkeys, final_rel->size, final_rel->width);
 272
 273         sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
 274                                                                                                 root->query_pathkeys,
 275                                                                                                 false);
 276         if (sortedpath)
 277         {
 278                 if (sortedpath->path_cost <= cheapest_cost)
 279                 {
 280                         /* Found a better presorted path, use it */
 281                         root->query_pathkeys = sortedpath->pathkeys;
 282                         return create_plan(sortedpath);
 283                 }
 284                 /* otherwise, doing it the hard way is still cheaper */
 285         }
 286         else
 287         {
 288                 /*
 289                  * If we found no usable presorted path at all, it is possible
 290                  * that the user asked for descending sort order.  Check to see
 291                  * if we can satisfy the pathkeys by using a backwards indexscan.
 292                  * To do this, we commute all the operators in the pathkeys and
 293                  * then look for a matching path that is an IndexPath.
 294                  */
 295                 List       *commuted_pathkeys = copyObject(root->query_pathkeys);
 296
 297                 if (commute_pathkeys(commuted_pathkeys))
 298                 {
 299                         /* pass 'true' to force only IndexPaths to be considered */
 300                         sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
 301                                                                                                                 commuted_pathkeys,
 302                                                                                                                 true);
 303                         if (sortedpath && sortedpath->path_cost <= cheapest_cost)
 304                         {
 305                                 /*
 306                                  * Kluge here: since IndexPath has no representation for
 307                                  * backwards scan, we have to convert to Plan format and
 308                                  * then poke the result.
 309                                  */
 310                                 Plan       *sortedplan = create_plan(sortedpath);
 311                                 List       *sortedpathkeys;
 312
 313                                 Assert(IsA(sortedplan, IndexScan));
 314                                 ((IndexScan *) sortedplan)->indxorderdir = BackwardScanDirection;
 315                                 /*
 316                                  * Need to generate commuted keys representing the actual
 317                                  * sort order.  This should succeed, probably, but just in
 318                                  * case it does not, use the original root->query_pathkeys
 319                                  * as a conservative approximation.
 320                                  */
 321                                 sortedpathkeys = copyObject(sortedpath->pathkeys);
 322                                 if (commute_pathkeys(sortedpathkeys))
 323                                         root->query_pathkeys = sortedpathkeys;
 324
 325                                 return sortedplan;
 326                         }
 327                 }
 328         }
 329
 330         /* Nothing for it but to sort the cheapestpath --- but we let the
 331          * caller do that.  union_planner has to be able to add a sort node
 332          * anyway, so no need for extra code here.  (Furthermore, the given
 333          * pathkeys might involve something we can't compute yet, such as
 334          * an aggregate function...)
 335          */
 336         root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 337         return create_plan(final_rel->cheapestpath);
 338 }