← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

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

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

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-2005, PostgreSQL Global Development Group
 
13
 * Portions Copyright (c) 1994, Regents of the University of California
 
14
 *
 
15
 *
 
16
 * IDENTIFICATION
 
17
 *        $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.81 2004-12-31 22:00:09 pgsql Exp $
 
18
 *
 
19
 *-------------------------------------------------------------------------
 
20
 */
 
21
#include "postgres.h"
 
22
 
 
23
#include "optimizer/clauses.h"
 
24
#include "optimizer/cost.h"
 
25
#include "optimizer/pathnode.h"
 
26
#include "optimizer/paths.h"
 
27
#include "optimizer/planmain.h"
 
28
 
 
29
 
 
30
/*--------------------
 
31
 * query_planner
 
32
 *        Generate a path (that is, a simplified plan) for a basic query,
 
33
 *        which may involve joins but not any fancier features.
 
34
 *
 
35
 * Since query_planner does not handle the toplevel processing (grouping,
 
36
 * sorting, etc) it cannot select the best path by itself.      It selects
 
37
 * two paths: the cheapest path that produces all the required tuples,
 
38
 * independent of any ordering considerations, and the cheapest path that
 
39
 * produces the expected fraction of the required tuples in the required
 
40
 * ordering, if there is a path that is cheaper for this than just sorting
 
41
 * the output of the cheapest overall path.  The caller (grouping_planner)
 
42
 * will make the final decision about which to use.
 
43
 *
 
44
 * Input parameters:
 
45
 * root is the query to plan
 
46
 * tlist is the target list the query should produce (NOT root->targetList!)
 
47
 * tuple_fraction is the fraction of tuples we expect will be retrieved
 
48
 *
 
49
 * Output parameters:
 
50
 * *cheapest_path receives the overall-cheapest path for the query
 
51
 * *sorted_path receives the cheapest presorted path for the query,
 
52
 *                              if any (NULL if there is no useful presorted path)
 
53
 *
 
54
 * Note: the Query node also includes a query_pathkeys field, which is both
 
55
 * an input and an output of query_planner().  The input value signals
 
56
 * query_planner that the indicated sort order is wanted in the final output
 
57
 * plan.  But this value has not yet been "canonicalized", since the needed
 
58
 * info does not get computed until we scan the qual clauses.  We canonicalize
 
59
 * it as soon as that task is done.  (The main reason query_pathkeys is a
 
60
 * Query field and not a passed parameter is that the low-level routines in
 
61
 * indxpath.c need to see it.)
 
62
 *
 
63
 * tuple_fraction is interpreted as follows:
 
64
 *        0: 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
 *--------------------
 
70
 */
 
71
void
 
72
query_planner(Query *root, List *tlist, double tuple_fraction,
 
73
                          Path **cheapest_path, Path **sorted_path)
 
74
{
 
75
        List       *constant_quals;
 
76
        RelOptInfo *final_rel;
 
77
        Path       *cheapestpath;
 
78
        Path       *sortedpath;
 
79
 
 
80
        /*
 
81
         * If the query has an empty join tree, then it's something easy like
 
82
         * "SELECT 2+2;" or "INSERT ... VALUES()".      Fall through quickly.
 
83
         */
 
84
        if (root->jointree->fromlist == NIL)
 
85
        {
 
86
                *cheapest_path = (Path *) create_result_path(NULL, NULL,
 
87
                                                                                 (List *) root->jointree->quals);
 
88
                *sorted_path = NULL;
 
89
                return;
 
90
        }
 
91
 
 
92
        /*
 
93
         * Pull out any non-variable WHERE clauses so these can be put in a
 
94
         * toplevel "Result" node, where they will gate execution of the whole
 
95
         * plan (the Result will not invoke its descendant plan unless the
 
96
         * quals are true).  Note that any *really* non-variable quals will
 
97
         * have been optimized away by eval_const_expressions().  What we're
 
98
         * mostly interested in here is quals that depend only on outer-level
 
99
         * vars, although if the qual reduces to "WHERE FALSE" this path will
 
100
         * also be taken.
 
101
         */
 
102
        root->jointree->quals = (Node *)
 
103
                pull_constant_clauses((List *) root->jointree->quals,
 
104
                                                          &constant_quals);
 
105
 
 
106
        /*
 
107
         * init planner lists to empty
 
108
         *
 
109
         * NOTE: in_info_list was set up by subquery_planner, do not touch here
 
110
         */
 
111
        root->base_rel_list = NIL;
 
112
        root->other_rel_list = NIL;
 
113
        root->join_rel_list = NIL;
 
114
        root->equi_key_list = NIL;
 
115
 
 
116
        /*
 
117
         * Construct RelOptInfo nodes for all base relations in query.
 
118
         */
 
119
        add_base_rels_to_query(root, (Node *) root->jointree);
 
120
 
 
121
        /*
 
122
         * Examine the targetlist and qualifications, adding entries to
 
123
         * baserel targetlists for all referenced Vars.  Restrict and join
 
124
         * clauses are added to appropriate lists belonging to the mentioned
 
125
         * relations.  We also build lists of equijoined keys for pathkey
 
126
         * construction.
 
127
         *
 
128
         * Note: all subplan nodes will have "flat" (var-only) tlists. This
 
129
         * implies that all expression evaluations are done at the root of the
 
130
         * plan tree.  Once upon a time there was code to try to push
 
131
         * expensive function calls down to lower plan nodes, but that's dead
 
132
         * code and has been for a long time...
 
133
         */
 
134
        build_base_rel_tlists(root, tlist);
 
135
 
 
136
        (void) distribute_quals_to_rels(root, (Node *) root->jointree);
 
137
 
 
138
        /*
 
139
         * Use the completed lists of equijoined keys to deduce any implied
 
140
         * but unstated equalities (for example, A=B and B=C imply A=C).
 
141
         */
 
142
        generate_implied_equalities(root);
 
143
 
 
144
        /*
 
145
         * We should now have all the pathkey equivalence sets built, so it's
 
146
         * now possible to convert the requested query_pathkeys to canonical
 
147
         * form.
 
148
         */
 
149
        root->query_pathkeys = canonicalize_pathkeys(root, root->query_pathkeys);
 
150
 
 
151
        /*
 
152
         * Ready to do the primary planning.
 
153
         */
 
154
        final_rel = make_one_rel(root);
 
155
 
 
156
        if (!final_rel || !final_rel->cheapest_total_path)
 
157
                elog(ERROR, "failed to construct the join relation");
 
158
 
 
159
        /*
 
160
         * Now that we have an estimate of the final rel's size, we can
 
161
         * convert a tuple_fraction specified as an absolute count (ie, a
 
162
         * LIMIT option) into a fraction of the total tuples.
 
163
         */
 
164
        if (tuple_fraction >= 1.0)
 
165
                tuple_fraction /= final_rel->rows;
 
166
 
 
167
        /*
 
168
         * Pick out the cheapest-total path and the cheapest presorted path
 
169
         * for the requested pathkeys (if there is one).  We should take the
 
170
         * tuple fraction into account when selecting the cheapest presorted
 
171
         * path, but not when selecting the cheapest-total path, since if we
 
172
         * have to sort then we'll have to fetch all the tuples.  (But there's
 
173
         * a special case: if query_pathkeys is NIL, meaning order doesn't
 
174
         * matter, then the "cheapest presorted" path will be the cheapest
 
175
         * overall for the tuple fraction.)
 
176
         *
 
177
         * The cheapest-total path is also the one to use if grouping_planner
 
178
         * decides to use hashed aggregation, so we return it separately even
 
179
         * if this routine thinks the presorted path is the winner.
 
180
         */
 
181
        cheapestpath = final_rel->cheapest_total_path;
 
182
 
 
183
        sortedpath =
 
184
                get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
 
185
                                                                                                  root->query_pathkeys,
 
186
                                                                                                  tuple_fraction);
 
187
 
 
188
        /* Don't return same path in both guises; just wastes effort */
 
189
        if (sortedpath == cheapestpath)
 
190
                sortedpath = NULL;
 
191
 
 
192
        /*
 
193
         * Forget about the presorted path if it would be cheaper to sort the
 
194
         * cheapest-total path.  Here we need consider only the behavior at
 
195
         * the tuple fraction point.
 
196
         */
 
197
        if (sortedpath)
 
198
        {
 
199
                Path            sort_path;      /* dummy for result of cost_sort */
 
200
 
 
201
                if (root->query_pathkeys == NIL ||
 
202
                        pathkeys_contained_in(root->query_pathkeys,
 
203
                                                                  cheapestpath->pathkeys))
 
204
                {
 
205
                        /* No sort needed for cheapest path */
 
206
                        sort_path.startup_cost = cheapestpath->startup_cost;
 
207
                        sort_path.total_cost = cheapestpath->total_cost;
 
208
                }
 
209
                else
 
210
                {
 
211
                        /* Figure cost for sorting */
 
212
                        cost_sort(&sort_path, root, root->query_pathkeys,
 
213
                                          cheapestpath->total_cost,
 
214
                                          final_rel->rows, final_rel->width);
 
215
                }
 
216
 
 
217
                if (compare_fractional_path_costs(sortedpath, &sort_path,
 
218
                                                                                  tuple_fraction) > 0)
 
219
                {
 
220
                        /* Presorted path is a loser */
 
221
                        sortedpath = NULL;
 
222
                }
 
223
        }
 
224
 
 
225
        /*
 
226
         * If we have constant quals, add a toplevel Result step to process
 
227
         * them.
 
228
         */
 
229
        if (constant_quals)
 
230
        {
 
231
                cheapestpath = (Path *) create_result_path(final_rel,
 
232
                                                                                                   cheapestpath,
 
233
                                                                                                   constant_quals);
 
234
                if (sortedpath)
 
235
                        sortedpath = (Path *) create_result_path(final_rel,
 
236
                                                                                                         sortedpath,
 
237
                                                                                                         constant_quals);
 
238
        }
 
239
 
 
240
        *cheapest_path = cheapestpath;
 
241
        *sorted_path = sortedpath;
 
242
}