1 /*-------------------------------------------------------------------------
4 * Routines to plan a single query
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.)
12 * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
13 * Portions Copyright (c) 1994, Regents of the University of California
17 * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.58 2000/08/13 02:50:07 tgl Exp $
19 *-------------------------------------------------------------------------
23 #include <sys/types.h>
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 "utils/memutils.h"
34 static Plan *subplanner(Query *root, List *flat_tlist, List *qual,
35 double tuple_fraction);
38 /*--------------------
40 * Generate a plan for a basic query, which may involve joins but
41 * not any fancier features.
43 * tlist is the target list the query should produce (NOT root->targetList!)
44 * qual is the qualification of the query (likewise!)
45 * tuple_fraction is the fraction of tuples we expect will be retrieved
47 * qual must already have been converted to implicit-AND form.
49 * Note: the Query node now also includes a query_pathkeys field, which
50 * is both an input and an output of query_planner(). The input value
51 * signals query_planner that the indicated sort order is wanted in the
52 * final output plan. The output value is the actual pathkeys of the
53 * selected path. This might not be the same as what the caller requested;
54 * the caller must do pathkeys_contained_in() to decide whether an
55 * explicit sort is still needed. (The main reason query_pathkeys is a
56 * Query field and not a passed parameter is that the low-level routines
57 * in indxpath.c need to see it.) The pathkeys value passed to query_planner
58 * has not yet been "canonicalized", since the necessary info does not get
59 * computed until subplanner() scans the qual clauses. We canonicalize it
60 * inside subplanner() as soon as that task is done. The output value
61 * will be in canonical form as well.
63 * tuple_fraction is interpreted as follows:
64 * 0 (or less): expect all tuples to be retrieved (normal case)
65 * 0 < tuple_fraction < 1: expect the given fraction of tuples available
66 * from the plan to be retrieved
67 * tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
68 * expected to be retrieved (ie, a LIMIT specification)
69 * Note that while this routine and its subroutines treat a negative
70 * tuple_fraction the same as 0, union_planner has a different interpretation.
72 * Returns a query plan.
76 query_planner(Query *root,
79 double tuple_fraction)
81 List *noncachable_qual;
87 * If the query contains no relation references at all, it must be
88 * something like "SELECT 2+2;". Build a trivial "Result" plan.
90 if (root->rtable == NIL)
92 /* If it's not a select, it should have had a target relation... */
93 if (root->commandType != CMD_SELECT)
94 elog(ERROR, "Empty range table for non-SELECT query");
96 root->query_pathkeys = NIL; /* signal unordered result */
98 /* Make childless Result node to evaluate given tlist. */
99 return (Plan *) make_result(tlist, (Node *) qual, (Plan *) NULL);
103 * Pull out any non-variable qual clauses so these can be put in a
104 * toplevel "Result" node, where they will gate execution of the whole
105 * plan (the Result will not invoke its descendant plan unless the
106 * quals are true). Note that any *really* non-variable quals will
107 * have been optimized away by eval_const_expressions(). What we're
108 * mostly interested in here is quals that depend only on outer-level
109 * vars, although if the qual reduces to "WHERE FALSE" this path will
110 * also be taken. We also need a special case for quals that contain
111 * noncachable functions but no vars, such as "WHERE random() < 0.5".
112 * These cannot be treated as normal restriction or join quals, but
113 * they're not constants either. Instead, attach them to the qpqual
114 * of the top-level plan, so that they get evaluated once per potential
117 qual = pull_constant_clauses(qual, &noncachable_qual, &constant_qual);
120 * Create a target list that consists solely of (resdom var) target
121 * list entries, i.e., contains no arbitrary expressions.
123 * All subplan nodes will have "flat" (var-only) tlists.
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...
130 var_only_tlist = flatten_tlist(tlist);
133 * Choose the best access path and build a plan for it.
135 subplan = subplanner(root, var_only_tlist, qual, tuple_fraction);
138 * Handle the noncachable quals.
140 if (noncachable_qual)
141 subplan->qual = nconc(subplan->qual, noncachable_qual);
144 * Build a result node to control the plan if we have constant quals.
150 * The result node will also be responsible for evaluating the
151 * originally requested tlist.
153 subplan = (Plan *) make_result(tlist,
154 (Node *) constant_qual,
161 * Replace the toplevel plan node's flattened target list with the
162 * targetlist given by my caller, so that expressions are
165 subplan->targetlist = tlist;
174 * Subplanner creates an entire plan consisting of joins and scans
175 * for processing a single level of attributes.
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
181 * See query_planner() comments about the interpretation of tuple_fraction.
186 subplanner(Query *root,
189 double tuple_fraction)
191 RelOptInfo *final_rel;
193 MemoryContext mycontext;
194 MemoryContext oldcxt;
199 * Initialize the targetlist and qualification, adding entries to
200 * base_rel_list as relation references are found (e.g., in the
201 * qualification, the targetlist, etc.). Restrict and join clauses
202 * are added to appropriate lists belonging to the mentioned
203 * relations. We also build lists of equijoined keys for pathkey
206 root->base_rel_list = NIL;
207 root->join_rel_list = NIL;
208 root->equi_key_list = NIL;
210 make_var_only_tlist(root, flat_tlist);
211 add_restrict_and_join_to_rels(root, qual);
214 * Make sure we have RelOptInfo nodes for all relations used.
216 add_missing_rels_to_query(root);
219 * Use the completed lists of equijoined keys to deduce any implied
220 * but unstated equalities (for example, A=B and B=C imply A=C).
222 generate_implied_equalities(root);
225 * We should now have all the pathkey equivalence sets built, so it's
226 * now possible to convert the requested query_pathkeys to canonical
229 root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
232 * We might allocate quite a lot of storage during planning (due to
233 * constructing lots of Paths), but all of it can be reclaimed after
234 * we generate the finished Plan tree. Work in a temporary context
235 * to let that happen. We make the context a child of
236 * TransactionCommandContext so it will be freed if error abort.
238 * Note: beware of trying to move this up to the start of this routine.
239 * Some of the data structures built above --- notably the pathkey
240 * equivalence sets --- will still be needed after this routine exits.
242 mycontext = AllocSetContextCreate(TransactionCommandContext,
244 ALLOCSET_DEFAULT_MINSIZE,
245 ALLOCSET_DEFAULT_INITSIZE,
246 ALLOCSET_DEFAULT_MAXSIZE);
247 oldcxt = MemoryContextSwitchTo(mycontext);
250 * Ready to do the primary planning.
252 final_rel = make_one_rel(root);
258 * We expect to end up here for a trivial INSERT ... VALUES query
259 * (which will have a target relation, so it gets past
260 * query_planner's check for empty range table; but the target rel
261 * is unreferenced and not marked inJoinSet, so we find there is
264 * It's also possible to get here if the query was rewritten by the
265 * rule processor (creating rangetable entries not marked
266 * inJoinSet) but the rules either did nothing or were simplified
267 * to nothing by constant-expression folding. So, don't complain.
269 root->query_pathkeys = NIL; /* signal unordered result */
271 /* Make childless Result node to evaluate given tlist. */
272 resultplan = (Plan *) make_result(flat_tlist, (Node *) qual,
277 #ifdef NOT_USED /* fix xfunc */
280 * Perform Predicate Migration on each path, to optimize and correctly
281 * assess the cost of each before choosing the cheapest one. -- JMH,
284 * Needn't do so if the top rel is pruneable: that means there's no
285 * expensive functions left to pull up. -- JMH, 11/22/92
287 if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM &&
288 XfuncMode != XFUNC_NOPULL && !final_rel->pruneable)
292 foreach(pathnode, final_rel->pathlist)
294 if (xfunc_do_predmig((Path *) lfirst(pathnode)))
295 set_cheapest(final_rel);
301 * Now that we have an estimate of the final rel's size, we can
302 * convert a tuple_fraction specified as an absolute count (ie, a
303 * LIMIT option) into a fraction of the total tuples.
305 if (tuple_fraction >= 1.0)
306 tuple_fraction /= final_rel->rows;
309 * Determine the cheapest path, independently of any ordering
310 * considerations. We do, however, take into account whether the
311 * whole plan is expected to be evaluated or not.
313 if (tuple_fraction <= 0.0 || tuple_fraction >= 1.0)
314 cheapestpath = final_rel->cheapest_total_path;
317 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
321 Assert(cheapestpath != NULL);
324 * Select the best path and create a subplan to execute it.
326 * If no special sort order is wanted, or if the cheapest path is already
327 * appropriately ordered, we use the cheapest path found above.
329 if (root->query_pathkeys == NIL ||
330 pathkeys_contained_in(root->query_pathkeys,
331 cheapestpath->pathkeys))
333 root->query_pathkeys = cheapestpath->pathkeys;
334 resultplan = create_plan(root, cheapestpath);
339 * Otherwise, look to see if we have an already-ordered path that is
340 * cheaper than doing an explicit sort on the cheapest-total-cost
343 cheapestpath = final_rel->cheapest_total_path;
345 get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
346 root->query_pathkeys,
350 Path sort_path; /* dummy for result of cost_sort */
352 cost_sort(&sort_path, root->query_pathkeys,
353 final_rel->rows, final_rel->width);
354 sort_path.startup_cost += cheapestpath->total_cost;
355 sort_path.total_cost += cheapestpath->total_cost;
356 if (compare_fractional_path_costs(presortedpath, &sort_path,
357 tuple_fraction) <= 0)
359 /* Presorted path is cheaper, use it */
360 root->query_pathkeys = presortedpath->pathkeys;
361 resultplan = create_plan(root, presortedpath);
364 /* otherwise, doing it the hard way is still cheaper */
368 * Nothing for it but to sort the cheapest-total-cost path --- but we
369 * let the caller do that. union_planner has to be able to add a sort
370 * node anyway, so no need for extra code here. (Furthermore, the
371 * given pathkeys might involve something we can't compute here, such
372 * as an aggregate function...)
374 root->query_pathkeys = cheapestpath->pathkeys;
375 resultplan = create_plan(root, cheapestpath);
380 * Must copy the completed plan tree and its pathkeys out of temporary
383 MemoryContextSwitchTo(oldcxt);
385 resultplan = copyObject(resultplan);
387 root->query_pathkeys = copyObject(root->query_pathkeys);
390 * Now we can release the Path storage.
392 MemoryContextDelete(mycontext);