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