← Back to branch summary

~ubuntu-branches/ubuntu/lucid/postgresql-8.4/lucid-proposed

« back to all changes in this revision

Viewing changes to src/backend/optimizer/plan/planmain.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/plan/planmain.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * planmain.c
 
4
 *        Routines to plan a single query
 
5
 *
 
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.)
 
11
 *
 
12
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 
13
 * Portions Copyright (c) 1994, Regents of the University of California
 
14
 *
 
15
 *
 
16
 * IDENTIFICATION
 
17
 *        $PostgreSQL$
 
18
 *
 
19
 *-------------------------------------------------------------------------
 
20
 */
 
21
#include "postgres.h"
 
22
 
 
23
#include "optimizer/cost.h"
 
24
#include "optimizer/pathnode.h"
 
25
#include "optimizer/paths.h"
 
26
#include "optimizer/placeholder.h"
 
27
#include "optimizer/planmain.h"
 
28
#include "optimizer/tlist.h"
 
29
#include "utils/selfuncs.h"
 
30
 
 
31
 
 
32
/*
 
33
 * query_planner
 
34
 *        Generate a path (that is, a simplified plan) for a basic query,
 
35
 *        which may involve joins but not any fancier features.
 
36
 *
 
37
 * Since query_planner does not handle the toplevel processing (grouping,
 
38
 * sorting, etc) it cannot select the best path by itself.      It selects
 
39
 * two paths: the cheapest path that produces all the required tuples,
 
40
 * independent of any ordering considerations, and the cheapest path that
 
41
 * produces the expected fraction of the required tuples in the required
 
42
 * ordering, if there is a path that is cheaper for this than just sorting
 
43
 * the output of the cheapest overall path.  The caller (grouping_planner)
 
44
 * will make the final decision about which to use.
 
45
 *
 
46
 * Input parameters:
 
47
 * root describes the query to plan
 
48
 * tlist is the target list the query should produce
 
49
 *              (this is NOT necessarily root->parse->targetList!)
 
50
 * tuple_fraction is the fraction of tuples we expect will be retrieved
 
51
 * limit_tuples is a hard limit on number of tuples to retrieve,
 
52
 *              or -1 if no limit
 
53
 *
 
54
 * Output parameters:
 
55
 * *cheapest_path receives the overall-cheapest path for the query
 
56
 * *sorted_path receives the cheapest presorted path for the query,
 
57
 *                              if any (NULL if there is no useful presorted path)
 
58
 * *num_groups receives the estimated number of groups, or 1 if query
 
59
 *                              does not use grouping
 
60
 *
 
61
 * Note: the PlannerInfo node also includes a query_pathkeys field, which is
 
62
 * both an input and an output of query_planner().      The input value signals
 
63
 * query_planner that the indicated sort order is wanted in the final output
 
64
 * plan.  But this value has not yet been "canonicalized", since the needed
 
65
 * info does not get computed until we scan the qual clauses.  We canonicalize
 
66
 * it as soon as that task is done.  (The main reason query_pathkeys is a
 
67
 * PlannerInfo field and not a passed parameter is that the low-level routines
 
68
 * in indxpath.c need to see it.)
 
69
 *
 
70
 * Note: the PlannerInfo node also includes group_pathkeys, window_pathkeys,
 
71
 * distinct_pathkeys, and sort_pathkeys, which like query_pathkeys need to be
 
72
 * canonicalized once the info is available.
 
73
 *
 
74
 * tuple_fraction is interpreted as follows:
 
75
 *        0: expect all tuples to be retrieved (normal case)
 
76
 *        0 < tuple_fraction < 1: expect the given fraction of tuples available
 
77
 *              from the plan to be retrieved
 
78
 *        tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
 
79
 *              expected to be retrieved (ie, a LIMIT specification)
 
80
 * Note that a nonzero tuple_fraction could come from outer context; it is
 
81
 * therefore not redundant with limit_tuples.  We use limit_tuples to determine
 
82
 * whether a bounded sort can be used at runtime.
 
83
 */
 
84
void
 
85
query_planner(PlannerInfo *root, List *tlist,
 
86
                          double tuple_fraction, double limit_tuples,
 
87
                          Path **cheapest_path, Path **sorted_path,
 
88
                          double *num_groups)
 
89
{
 
90
        Query      *parse = root->parse;
 
91
        List       *joinlist;
 
92
        RelOptInfo *final_rel;
 
93
        Path       *cheapestpath;
 
94
        Path       *sortedpath;
 
95
        Index           rti;
 
96
        ListCell   *lc;
 
97
        double          total_pages;
 
98
 
 
99
        /* Make tuple_fraction accessible to lower-level routines */
 
100
        root->tuple_fraction = tuple_fraction;
 
101
 
 
102
        *num_groups = 1;                        /* default result */
 
103
 
 
104
        /*
 
105
         * If the query has an empty join tree, then it's something easy like
 
106
         * "SELECT 2+2;" or "INSERT ... VALUES()".      Fall through quickly.
 
107
         */
 
108
        if (parse->jointree->fromlist == NIL)
 
109
        {
 
110
                /* We need a trivial path result */
 
111
                *cheapest_path = (Path *)
 
112
                        create_result_path((List *) parse->jointree->quals);
 
113
                *sorted_path = NULL;
 
114
 
 
115
                /*
 
116
                 * We still are required to canonicalize any pathkeys, in case it's
 
117
                 * something like "SELECT 2+2 ORDER BY 1".
 
118
                 */
 
119
                root->canon_pathkeys = NIL;
 
120
                root->query_pathkeys = canonicalize_pathkeys(root,
 
121
                                                                                                         root->query_pathkeys);
 
122
                root->group_pathkeys = canonicalize_pathkeys(root,
 
123
                                                                                                         root->group_pathkeys);
 
124
                root->window_pathkeys = canonicalize_pathkeys(root,
 
125
                                                                                                          root->window_pathkeys);
 
126
                root->distinct_pathkeys = canonicalize_pathkeys(root,
 
127
                                                                                                        root->distinct_pathkeys);
 
128
                root->sort_pathkeys = canonicalize_pathkeys(root,
 
129
                                                                                                        root->sort_pathkeys);
 
130
                return;
 
131
        }
 
132
 
 
133
        /*
 
134
         * Init planner lists to empty, and set up the array to hold RelOptInfos
 
135
         * for "simple" rels.
 
136
         *
 
137
         * NOTE: append_rel_list was set up by subquery_planner, so do not touch
 
138
         * here; eq_classes may contain data already, too.
 
139
         */
 
140
        root->simple_rel_array_size = list_length(parse->rtable) + 1;
 
141
        root->simple_rel_array = (RelOptInfo **)
 
142
                palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));
 
143
        root->join_rel_list = NIL;
 
144
        root->join_rel_hash = NULL;
 
145
        root->canon_pathkeys = NIL;
 
146
        root->left_join_clauses = NIL;
 
147
        root->right_join_clauses = NIL;
 
148
        root->full_join_clauses = NIL;
 
149
        root->join_info_list = NIL;
 
150
        root->placeholder_list = NIL;
 
151
        root->initial_rels = NIL;
 
152
 
 
153
        /*
 
154
         * Make a flattened version of the rangetable for faster access (this is
 
155
         * OK because the rangetable won't change any more).
 
156
         */
 
157
        root->simple_rte_array = (RangeTblEntry **)
 
158
                palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *));
 
159
        rti = 1;
 
160
        foreach(lc, parse->rtable)
 
161
        {
 
162
                RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
 
163
 
 
164
                root->simple_rte_array[rti++] = rte;
 
165
        }
 
166
 
 
167
        /*
 
168
         * Construct RelOptInfo nodes for all base relations in query, and
 
169
         * indirectly for all appendrel member relations ("other rels").  This
 
170
         * will give us a RelOptInfo for every "simple" (non-join) rel involved in
 
171
         * the query.
 
172
         *
 
173
         * Note: the reason we find the rels by searching the jointree and
 
174
         * appendrel list, rather than just scanning the rangetable, is that the
 
175
         * rangetable may contain RTEs for rels not actively part of the query,
 
176
         * for example views.  We don't want to make RelOptInfos for them.
 
177
         */
 
178
        add_base_rels_to_query(root, (Node *) parse->jointree);
 
179
 
 
180
        /*
 
181
         * We should now have size estimates for every actual table involved in
 
182
         * the query, so we can compute total_table_pages.      Note that appendrels
 
183
         * are not double-counted here, even though we don't bother to distinguish
 
184
         * RelOptInfos for appendrel parents, because the parents will still have
 
185
         * size zero.
 
186
         *
 
187
         * XXX if a table is self-joined, we will count it once per appearance,
 
188
         * which perhaps is the wrong thing ... but that's not completely clear,
 
189
         * and detecting self-joins here is difficult, so ignore it for now.
 
190
         */
 
191
        total_pages = 0;
 
192
        for (rti = 1; rti < root->simple_rel_array_size; rti++)
 
193
        {
 
194
                RelOptInfo *brel = root->simple_rel_array[rti];
 
195
 
 
196
                if (brel == NULL)
 
197
                        continue;
 
198
 
 
199
                Assert(brel->relid == rti);             /* sanity check on array */
 
200
 
 
201
                total_pages += (double) brel->pages;
 
202
        }
 
203
        root->total_table_pages = total_pages;
 
204
 
 
205
        /*
 
206
         * Examine the targetlist and qualifications, adding entries to baserel
 
207
         * targetlists for all referenced Vars.  Restrict and join clauses are
 
208
         * added to appropriate lists belonging to the mentioned relations.  We
 
209
         * also build EquivalenceClasses for provably equivalent expressions, and
 
210
         * form a target joinlist for make_one_rel() to work from.
 
211
         */
 
212
        build_base_rel_tlists(root, tlist);
 
213
 
 
214
        joinlist = deconstruct_jointree(root);
 
215
 
 
216
        /*
 
217
         * Reconsider any postponed outer-join quals now that we have built up
 
218
         * equivalence classes.  (This could result in further additions or
 
219
         * mergings of classes.)
 
220
         */
 
221
        reconsider_outer_join_clauses(root);
 
222
 
 
223
        /*
 
224
         * If we formed any equivalence classes, generate additional restriction
 
225
         * clauses as appropriate.      (Implied join clauses are formed on-the-fly
 
226
         * later.)
 
227
         */
 
228
        generate_base_implied_equalities(root);
 
229
 
 
230
        /*
 
231
         * We have completed merging equivalence sets, so it's now possible to
 
232
         * convert the requested query_pathkeys to canonical form.      Also
 
233
         * canonicalize the groupClause, windowClause, distinctClause and
 
234
         * sortClause pathkeys for use later.
 
235
         */
 
236
        root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 
237
        root->group_pathkeys = canonicalize_pathkeys(root, root->group_pathkeys);
 
238
        root->window_pathkeys = canonicalize_pathkeys(root, root->window_pathkeys);
 
239
        root->distinct_pathkeys = canonicalize_pathkeys(root, root->distinct_pathkeys);
 
240
        root->sort_pathkeys = canonicalize_pathkeys(root, root->sort_pathkeys);
 
241
 
 
242
        /*
 
243
         * Examine any "placeholder" expressions generated during subquery pullup.
 
244
         * Make sure that we know what level to evaluate them at, and that the
 
245
         * Vars they need are marked as needed.
 
246
         */
 
247
        fix_placeholder_eval_levels(root);
 
248
 
 
249
        /*
 
250
         * Ready to do the primary planning.
 
251
         */
 
252
        final_rel = make_one_rel(root, joinlist);
 
253
 
 
254
        if (!final_rel || !final_rel->cheapest_total_path)
 
255
                elog(ERROR, "failed to construct the join relation");
 
256
 
 
257
        /*
 
258
         * If there's grouping going on, estimate the number of result groups. We
 
259
         * couldn't do this any earlier because it depends on relation size
 
260
         * estimates that were set up above.
 
261
         *
 
262
         * Then convert tuple_fraction to fractional form if it is absolute, and
 
263
         * adjust it based on the knowledge that grouping_planner will be doing
 
264
         * grouping or aggregation work with our result.
 
265
         *
 
266
         * This introduces some undesirable coupling between this code and
 
267
         * grouping_planner, but the alternatives seem even uglier; we couldn't
 
268
         * pass back completed paths without making these decisions here.
 
269
         */
 
270
        if (parse->groupClause)
 
271
        {
 
272
                List       *groupExprs;
 
273
 
 
274
                groupExprs = get_sortgrouplist_exprs(parse->groupClause,
 
275
                                                                                         parse->targetList);
 
276
                *num_groups = estimate_num_groups(root,
 
277
                                                                                  groupExprs,
 
278
                                                                                  final_rel->rows);
 
279
 
 
280
                /*
 
281
                 * In GROUP BY mode, an absolute LIMIT is relative to the number of
 
282
                 * groups not the number of tuples.  If the caller gave us a fraction,
 
283
                 * keep it as-is.  (In both cases, we are effectively assuming that
 
284
                 * all the groups are about the same size.)
 
285
                 */
 
286
                if (tuple_fraction >= 1.0)
 
287
                        tuple_fraction /= *num_groups;
 
288
 
 
289
                /*
 
290
                 * If both GROUP BY and ORDER BY are specified, we will need two
 
291
                 * levels of sort --- and, therefore, certainly need to read all the
 
292
                 * tuples --- unless ORDER BY is a subset of GROUP BY.  Likewise if
 
293
                 * we have both DISTINCT and GROUP BY, or if we have a window
 
294
                 * specification not compatible with the GROUP BY.
 
295
                 */
 
296
                if (!pathkeys_contained_in(root->sort_pathkeys, root->group_pathkeys) ||
 
297
                        !pathkeys_contained_in(root->distinct_pathkeys, root->group_pathkeys) ||
 
298
                        !pathkeys_contained_in(root->window_pathkeys, root->group_pathkeys))
 
299
                        tuple_fraction = 0.0;
 
300
        }
 
301
        else if (parse->hasAggs || root->hasHavingQual)
 
302
        {
 
303
                /*
 
304
                 * Ungrouped aggregate will certainly want to read all the tuples, and
 
305
                 * it will deliver a single result row (so leave *num_groups 1).
 
306
                 */
 
307
                tuple_fraction = 0.0;
 
308
        }
 
309
        else if (parse->distinctClause)
 
310
        {
 
311
                /*
 
312
                 * Since there was no grouping or aggregation, it's reasonable to
 
313
                 * assume the UNIQUE filter has effects comparable to GROUP BY. Return
 
314
                 * the estimated number of output rows for use by caller. (If DISTINCT
 
315
                 * is used with grouping, we ignore its effects for rowcount
 
316
                 * estimation purposes; this amounts to assuming the grouped rows are
 
317
                 * distinct already.)
 
318
                 */
 
319
                List       *distinctExprs;
 
320
 
 
321
                distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
 
322
                                                                                                parse->targetList);
 
323
                *num_groups = estimate_num_groups(root,
 
324
                                                                                  distinctExprs,
 
325
                                                                                  final_rel->rows);
 
326
 
 
327
                /*
 
328
                 * Adjust tuple_fraction the same way as for GROUP BY, too.
 
329
                 */
 
330
                if (tuple_fraction >= 1.0)
 
331
                        tuple_fraction /= *num_groups;
 
332
        }
 
333
        else
 
334
        {
 
335
                /*
 
336
                 * Plain non-grouped, non-aggregated query: an absolute tuple fraction
 
337
                 * can be divided by the number of tuples.
 
338
                 */
 
339
                if (tuple_fraction >= 1.0)
 
340
                        tuple_fraction /= final_rel->rows;
 
341
        }
 
342
 
 
343
        /*
 
344
         * Pick out the cheapest-total path and the cheapest presorted path for
 
345
         * the requested pathkeys (if there is one).  We should take the tuple
 
346
         * fraction into account when selecting the cheapest presorted path, but
 
347
         * not when selecting the cheapest-total path, since if we have to sort
 
348
         * then we'll have to fetch all the tuples.  (But there's a special case:
 
349
         * if query_pathkeys is NIL, meaning order doesn't matter, then the
 
350
         * "cheapest presorted" path will be the cheapest overall for the tuple
 
351
         * fraction.)
 
352
         *
 
353
         * The cheapest-total path is also the one to use if grouping_planner
 
354
         * decides to use hashed aggregation, so we return it separately even if
 
355
         * this routine thinks the presorted path is the winner.
 
356
         */
 
357
        cheapestpath = final_rel->cheapest_total_path;
 
358
 
 
359
        sortedpath =
 
360
                get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 
361
                                                                                                  root->query_pathkeys,
 
362
                                                                                                  tuple_fraction);
 
363
 
 
364
        /* Don't return same path in both guises; just wastes effort */
 
365
        if (sortedpath == cheapestpath)
 
366
                sortedpath = NULL;
 
367
 
 
368
        /*
 
369
         * Forget about the presorted path if it would be cheaper to sort the
 
370
         * cheapest-total path.  Here we need consider only the behavior at the
 
371
         * tuple fraction point.
 
372
         */
 
373
        if (sortedpath)
 
374
        {
 
375
                Path            sort_path;      /* dummy for result of cost_sort */
 
376
 
 
377
                if (root->query_pathkeys == NIL ||
 
378
                        pathkeys_contained_in(root->query_pathkeys,
 
379
                                                                  cheapestpath->pathkeys))
 
380
                {
 
381
                        /* No sort needed for cheapest path */
 
382
                        sort_path.startup_cost = cheapestpath->startup_cost;
 
383
                        sort_path.total_cost = cheapestpath->total_cost;
 
384
                }
 
385
                else
 
386
                {
 
387
                        /* Figure cost for sorting */
 
388
                        cost_sort(&sort_path, root, root->query_pathkeys,
 
389
                                          cheapestpath->total_cost,
 
390
                                          final_rel->rows, final_rel->width,
 
391
                                          limit_tuples);
 
392
                }
 
393
 
 
394
                if (compare_fractional_path_costs(sortedpath, &sort_path,
 
395
                                                                                  tuple_fraction) > 0)
 
396
                {
 
397
                        /* Presorted path is a loser */
 
398
                        sortedpath = NULL;
 
399
                }
 
400
        }
 
401
 
 
402
        *cheapest_path = cheapestpath;
 
403
        *sorted_path = sortedpath;
 
404
}