← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/optimizer/geqo/geqo_eval.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/geqo/geqo_eval.c
 
1
/*------------------------------------------------------------------------
 
2
 *
 
3
 * geqo_eval.c
 
4
 *        Routines to evaluate query trees
 
5
 *
 
6
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 * $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_eval.c,v 1.73 2004-12-31 21:59:58 pgsql Exp $
 
10
 *
 
11
 *-------------------------------------------------------------------------
 
12
 */
 
13
 
 
14
/* contributed by:
 
15
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 
16
   *  Martin Utesch                              * Institute of Automatic Control          *
 
17
   =                                                     = University of Mining and Technology =
 
18
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                               *
 
19
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 
20
 */
 
21
 
 
22
#include "postgres.h"
 
23
 
 
24
#include <float.h>
 
25
#include <limits.h>
 
26
#include <math.h>
 
27
 
 
28
#include "optimizer/geqo.h"
 
29
#include "optimizer/pathnode.h"
 
30
#include "optimizer/paths.h"
 
31
#include "utils/memutils.h"
 
32
 
 
33
 
 
34
static bool desirable_join(Query *root,
 
35
                           RelOptInfo *outer_rel, RelOptInfo *inner_rel);
 
36
 
 
37
 
 
38
/*
 
39
 * geqo_eval
 
40
 *
 
41
 * Returns cost of a query tree as an individual of the population.
 
42
 */
 
43
Cost
 
44
geqo_eval(Gene *tour, int num_gene, GeqoEvalData *evaldata)
 
45
{
 
46
        MemoryContext mycontext;
 
47
        MemoryContext oldcxt;
 
48
        RelOptInfo *joinrel;
 
49
        Cost            fitness;
 
50
        List       *savelist;
 
51
 
 
52
        /*
 
53
         * Because gimme_tree considers both left- and right-sided trees,
 
54
         * there is no difference between a tour (a,b,c,d,...) and a tour
 
55
         * (b,a,c,d,...) --- the same join orders will be considered. To avoid
 
56
         * redundant cost calculations, we simply reject tours where tour[0] >
 
57
         * tour[1], assigning them an artificially bad fitness.
 
58
         *
 
59
         * init_tour() is aware of this rule and so we should never reject a tour
 
60
         * during the initial filling of the pool.      It seems difficult to
 
61
         * persuade the recombination logic never to break the rule, however.
 
62
         */
 
63
        if (num_gene >= 2 && tour[0] > tour[1])
 
64
                return DBL_MAX;
 
65
 
 
66
        /*
 
67
         * Create a private memory context that will hold all temp storage
 
68
         * allocated inside gimme_tree().
 
69
         *
 
70
         * Since geqo_eval() will be called many times, we can't afford to let
 
71
         * all that memory go unreclaimed until end of statement.  Note we
 
72
         * make the temp context a child of the planner's normal context, so
 
73
         * that it will be freed even if we abort via ereport(ERROR).
 
74
         */
 
75
        mycontext = AllocSetContextCreate(CurrentMemoryContext,
 
76
                                                                          "GEQO",
 
77
                                                                          ALLOCSET_DEFAULT_MINSIZE,
 
78
                                                                          ALLOCSET_DEFAULT_INITSIZE,
 
79
                                                                          ALLOCSET_DEFAULT_MAXSIZE);
 
80
        oldcxt = MemoryContextSwitchTo(mycontext);
 
81
 
 
82
        /*
 
83
         * gimme_tree will add entries to root->join_rel_list, which may or may
 
84
         * not already contain some entries.  The newly added entries will be
 
85
         * recycled by the MemoryContextDelete below, so we must ensure that
 
86
         * the list is restored to its former state before exiting.  With the
 
87
         * new List implementation, the easiest way is to make a duplicate list
 
88
         * that gimme_tree can modify.
 
89
         */
 
90
        savelist = evaldata->root->join_rel_list;
 
91
 
 
92
        evaldata->root->join_rel_list = list_copy(savelist);
 
93
 
 
94
        /* construct the best path for the given combination of relations */
 
95
        joinrel = gimme_tree(tour, num_gene, evaldata);
 
96
 
 
97
        /*
 
98
         * compute fitness
 
99
         *
 
100
         * XXX geqo does not currently support optimization for partial result
 
101
         * retrieval --- how to fix?
 
102
         */
 
103
        if (joinrel)
 
104
                fitness = joinrel->cheapest_total_path->total_cost;
 
105
        else
 
106
                fitness = DBL_MAX;
 
107
 
 
108
        /* restore join_rel_list */
 
109
        evaldata->root->join_rel_list = savelist;
 
110
 
 
111
        /* release all the memory acquired within gimme_tree */
 
112
        MemoryContextSwitchTo(oldcxt);
 
113
        MemoryContextDelete(mycontext);
 
114
 
 
115
        return fitness;
 
116
}
 
117
 
 
118
/*
 
119
 * gimme_tree
 
120
 *        Form planner estimates for a join tree constructed in the specified
 
121
 *        order.
 
122
 *
 
123
 *       'tour' is the proposed join order, of length 'num_gene'
 
124
 *       'evaldata' contains the context we need
 
125
 *
 
126
 * Returns a new join relation whose cheapest path is the best plan for
 
127
 * this join order.  NB: will return NULL if join order is invalid.
 
128
 *
 
129
 * The original implementation of this routine always joined in the specified
 
130
 * order, and so could only build left-sided plans (and right-sided and
 
131
 * mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
 
132
 * It could never produce a "bushy" plan.  This had a couple of big problems,
 
133
 * of which the worst was that as of 7.4, there are situations involving IN
 
134
 * subqueries where the only valid plans are bushy.
 
135
 *
 
136
 * The present implementation takes the given tour as a guideline, but
 
137
 * postpones joins that seem unsuitable according to some heuristic rules.
 
138
 * This allows correct bushy plans to be generated at need, and as a nice
 
139
 * side-effect it seems to materially improve the quality of the generated
 
140
 * plans.
 
141
 */
 
142
RelOptInfo *
 
143
gimme_tree(Gene *tour, int num_gene, GeqoEvalData *evaldata)
 
144
{
 
145
        RelOptInfo **stack;
 
146
        int                     stack_depth;
 
147
        RelOptInfo *joinrel;
 
148
        int                     rel_count;
 
149
 
 
150
        /*
 
151
         * Create a stack to hold not-yet-joined relations.
 
152
         */
 
153
        stack = (RelOptInfo **) palloc(num_gene * sizeof(RelOptInfo *));
 
154
        stack_depth = 0;
 
155
 
 
156
        /*
 
157
         * Push each relation onto the stack in the specified order.  After
 
158
         * pushing each relation, see whether the top two stack entries are
 
159
         * joinable according to the desirable_join() heuristics.  If so, join
 
160
         * them into one stack entry, and try again to combine with the next
 
161
         * stack entry down (if any).  When the stack top is no longer
 
162
         * joinable, continue to the next input relation.  After we have
 
163
         * pushed the last input relation, the heuristics are disabled and we
 
164
         * force joining all the remaining stack entries.
 
165
         *
 
166
         * If desirable_join() always returns true, this produces a straight
 
167
         * left-to-right join just like the old code.  Otherwise we may
 
168
         * produce a bushy plan or a left/right-sided plan that really
 
169
         * corresponds to some tour other than the one given.  To the extent
 
170
         * that the heuristics are helpful, however, this will be a better
 
171
         * plan than the raw tour.
 
172
         *
 
173
         * Also, when a join attempt fails (because of IN-clause constraints), we
 
174
         * may be able to recover and produce a workable plan, where the old
 
175
         * code just had to give up.  This case acts the same as a false
 
176
         * result from desirable_join().
 
177
         */
 
178
        for (rel_count = 0; rel_count < num_gene; rel_count++)
 
179
        {
 
180
                int                     cur_rel_index;
 
181
 
 
182
                /* Get the next input relation and push it */
 
183
                cur_rel_index = (int) tour[rel_count];
 
184
                stack[stack_depth] = (RelOptInfo *) list_nth(evaldata->initial_rels,
 
185
                                                                                                         cur_rel_index - 1);
 
186
                stack_depth++;
 
187
 
 
188
                /*
 
189
                 * While it's feasible, pop the top two stack entries and replace
 
190
                 * with their join.
 
191
                 */
 
192
                while (stack_depth >= 2)
 
193
                {
 
194
                        RelOptInfo *outer_rel = stack[stack_depth - 2];
 
195
                        RelOptInfo *inner_rel = stack[stack_depth - 1];
 
196
 
 
197
                        /*
 
198
                         * Don't pop if heuristics say not to join now.  However, once
 
199
                         * we have exhausted the input, the heuristics can't prevent
 
200
                         * popping.
 
201
                         */
 
202
                        if (rel_count < num_gene - 1 &&
 
203
                                !desirable_join(evaldata->root, outer_rel, inner_rel))
 
204
                                break;
 
205
 
 
206
                        /*
 
207
                         * Construct a RelOptInfo representing the join of these two
 
208
                         * input relations.  These are always inner joins. Note that
 
209
                         * we expect the joinrel not to exist in root->join_rel_list
 
210
                         * yet, and so the paths constructed for it will only include
 
211
                         * the ones we want.
 
212
                         */
 
213
                        joinrel = make_join_rel(evaldata->root, outer_rel, inner_rel,
 
214
                                                                        JOIN_INNER);
 
215
 
 
216
                        /* Can't pop stack here if join order is not valid */
 
217
                        if (!joinrel)
 
218
                                break;
 
219
 
 
220
                        /* Find and save the cheapest paths for this rel */
 
221
                        set_cheapest(joinrel);
 
222
 
 
223
                        /* Pop the stack and replace the inputs with their join */
 
224
                        stack_depth--;
 
225
                        stack[stack_depth - 1] = joinrel;
 
226
                }
 
227
        }
 
228
 
 
229
        /* Did we succeed in forming a single join relation? */
 
230
        if (stack_depth == 1)
 
231
                joinrel = stack[0];
 
232
        else
 
233
                joinrel = NULL;
 
234
 
 
235
        pfree(stack);
 
236
 
 
237
        return joinrel;
 
238
}
 
239
 
 
240
/*
 
241
 * Heuristics for gimme_tree: do we want to join these two relations?
 
242
 */
 
243
static bool
 
244
desirable_join(Query *root,
 
245
                           RelOptInfo *outer_rel, RelOptInfo *inner_rel)
 
246
{
 
247
        ListCell   *l;
 
248
 
 
249
        /*
 
250
         * Join if there is an applicable join clause.
 
251
         */
 
252
        foreach(l, outer_rel->joininfo)
 
253
        {
 
254
                JoinInfo   *joininfo = (JoinInfo *) lfirst(l);
 
255
 
 
256
                if (bms_is_subset(joininfo->unjoined_relids, inner_rel->relids))
 
257
                        return true;
 
258
        }
 
259
 
 
260
        /*
 
261
         * Join if the rels are members of the same IN sub-select.      This is
 
262
         * needed to improve the odds that we will find a valid solution in a
 
263
         * case where an IN sub-select has a clauseless join.
 
264
         */
 
265
        foreach(l, root->in_info_list)
 
266
        {
 
267
                InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 
268
 
 
269
                if (bms_is_subset(outer_rel->relids, ininfo->righthand) &&
 
270
                        bms_is_subset(inner_rel->relids, ininfo->righthand))
 
271
                        return true;
 
272
        }
 
273
 
 
274
        /* Otherwise postpone the join till later. */
 
275
        return false;
 
276
}