← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/backend/optimizer/geqo/geqo_eval.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

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-2011, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 * src/backend/optimizer/geqo/geqo_eval.c
 
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/joininfo.h"
 
30
#include "optimizer/pathnode.h"
 
31
#include "optimizer/paths.h"
 
32
#include "utils/memutils.h"
 
33
 
 
34
 
 
35
/* A "clump" of already-joined relations within gimme_tree */
 
36
typedef struct
 
37
{
 
38
        RelOptInfo *joinrel;            /* joinrel for the set of relations */
 
39
        int                     size;                   /* number of input relations in clump */
 
40
} Clump;
 
41
 
 
42
static List *merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump,
 
43
                        bool force);
 
44
static bool desirable_join(PlannerInfo *root,
 
45
                           RelOptInfo *outer_rel, RelOptInfo *inner_rel);
 
46
 
 
47
 
 
48
/*
 
49
 * geqo_eval
 
50
 *
 
51
 * Returns cost of a query tree as an individual of the population.
 
52
 */
 
53
Cost
 
54
geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
 
55
{
 
56
        MemoryContext mycontext;
 
57
        MemoryContext oldcxt;
 
58
        RelOptInfo *joinrel;
 
59
        Cost            fitness;
 
60
        int                     savelength;
 
61
        struct HTAB *savehash;
 
62
 
 
63
        /*
 
64
         * Create a private memory context that will hold all temp storage
 
65
         * allocated inside gimme_tree().
 
66
         *
 
67
         * Since geqo_eval() will be called many times, we can't afford to let all
 
68
         * that memory go unreclaimed until end of statement.  Note we make the
 
69
         * temp context a child of the planner's normal context, so that it will
 
70
         * be freed even if we abort via ereport(ERROR).
 
71
         */
 
72
        mycontext = AllocSetContextCreate(CurrentMemoryContext,
 
73
                                                                          "GEQO",
 
74
                                                                          ALLOCSET_DEFAULT_MINSIZE,
 
75
                                                                          ALLOCSET_DEFAULT_INITSIZE,
 
76
                                                                          ALLOCSET_DEFAULT_MAXSIZE);
 
77
        oldcxt = MemoryContextSwitchTo(mycontext);
 
78
 
 
79
        /*
 
80
         * gimme_tree will add entries to root->join_rel_list, which may or may
 
81
         * not already contain some entries.  The newly added entries will be
 
82
         * recycled by the MemoryContextDelete below, so we must ensure that the
 
83
         * list is restored to its former state before exiting.  We can do this by
 
84
         * truncating the list to its original length.  NOTE this assumes that any
 
85
         * added entries are appended at the end!
 
86
         *
 
87
         * We also must take care not to mess up the outer join_rel_hash, if there
 
88
         * is one.      We can do this by just temporarily setting the link to NULL.
 
89
         * (If we are dealing with enough join rels, which we very likely are, a
 
90
         * new hash table will get built and used locally.)
 
91
         *
 
92
         * join_rel_level[] shouldn't be in use, so just Assert it isn't.
 
93
         */
 
94
        savelength = list_length(root->join_rel_list);
 
95
        savehash = root->join_rel_hash;
 
96
        Assert(root->join_rel_level == NULL);
 
97
 
 
98
        root->join_rel_hash = NULL;
 
99
 
 
100
        /* construct the best path for the given combination of relations */
 
101
        joinrel = gimme_tree(root, tour, num_gene);
 
102
 
 
103
        /*
 
104
         * compute fitness
 
105
         *
 
106
         * XXX geqo does not currently support optimization for partial result
 
107
         * retrieval --- how to fix?
 
108
         */
 
109
        fitness = joinrel->cheapest_total_path->total_cost;
 
110
 
 
111
        /*
 
112
         * Restore join_rel_list to its former state, and put back original
 
113
         * hashtable if any.
 
114
         */
 
115
        root->join_rel_list = list_truncate(root->join_rel_list,
 
116
                                                                                savelength);
 
117
        root->join_rel_hash = savehash;
 
118
 
 
119
        /* release all the memory acquired within gimme_tree */
 
120
        MemoryContextSwitchTo(oldcxt);
 
121
        MemoryContextDelete(mycontext);
 
122
 
 
123
        return fitness;
 
124
}
 
125
 
 
126
/*
 
127
 * gimme_tree
 
128
 *        Form planner estimates for a join tree constructed in the specified
 
129
 *        order.
 
130
 *
 
131
 *       'tour' is the proposed join order, of length 'num_gene'
 
132
 *
 
133
 * Returns a new join relation whose cheapest path is the best plan for
 
134
 * this join order.
 
135
 *
 
136
 * The original implementation of this routine always joined in the specified
 
137
 * order, and so could only build left-sided plans (and right-sided and
 
138
 * mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
 
139
 * It could never produce a "bushy" plan.  This had a couple of big problems,
 
140
 * of which the worst was that there are situations involving join order
 
141
 * restrictions where the only valid plans are bushy.
 
142
 *
 
143
 * The present implementation takes the given tour as a guideline, but
 
144
 * postpones joins that are illegal or seem unsuitable according to some
 
145
 * heuristic rules.  This allows correct bushy plans to be generated at need,
 
146
 * and as a nice side-effect it seems to materially improve the quality of the
 
147
 * generated plans.
 
148
 */
 
149
RelOptInfo *
 
150
gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
 
151
{
 
152
        GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
 
153
        List       *clumps;
 
154
        int                     rel_count;
 
155
 
 
156
        /*
 
157
         * Sometimes, a relation can't yet be joined to others due to heuristics
 
158
         * or actual semantic restrictions.  We maintain a list of "clumps" of
 
159
         * successfully joined relations, with larger clumps at the front. Each
 
160
         * new relation from the tour is added to the first clump it can be joined
 
161
         * to; if there is none then it becomes a new clump of its own. When we
 
162
         * enlarge an existing clump we check to see if it can now be merged with
 
163
         * any other clumps.  After the tour is all scanned, we forget about the
 
164
         * heuristics and try to forcibly join any remaining clumps.  Some forced
 
165
         * joins might still fail due to semantics, but we should always be able
 
166
         * to find some join order that works.
 
167
         */
 
168
        clumps = NIL;
 
169
 
 
170
        for (rel_count = 0; rel_count < num_gene; rel_count++)
 
171
        {
 
172
                int                     cur_rel_index;
 
173
                RelOptInfo *cur_rel;
 
174
                Clump      *cur_clump;
 
175
 
 
176
                /* Get the next input relation */
 
177
                cur_rel_index = (int) tour[rel_count];
 
178
                cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
 
179
                                                                                  cur_rel_index - 1);
 
180
 
 
181
                /* Make it into a single-rel clump */
 
182
                cur_clump = (Clump *) palloc(sizeof(Clump));
 
183
                cur_clump->joinrel = cur_rel;
 
184
                cur_clump->size = 1;
 
185
 
 
186
                /* Merge it into the clumps list, using only desirable joins */
 
187
                clumps = merge_clump(root, clumps, cur_clump, false);
 
188
        }
 
189
 
 
190
        if (list_length(clumps) > 1)
 
191
        {
 
192
                /* Force-join the remaining clumps in some legal order */
 
193
                List       *fclumps;
 
194
                ListCell   *lc;
 
195
 
 
196
                fclumps = NIL;
 
197
                foreach(lc, clumps)
 
198
                {
 
199
                        Clump      *clump = (Clump *) lfirst(lc);
 
200
 
 
201
                        fclumps = merge_clump(root, fclumps, clump, true);
 
202
                }
 
203
                clumps = fclumps;
 
204
        }
 
205
 
 
206
        /* Did we succeed in forming a single join relation? */
 
207
        if (list_length(clumps) != 1)
 
208
                elog(ERROR, "failed to join all relations together");
 
209
 
 
210
        return ((Clump *) linitial(clumps))->joinrel;
 
211
}
 
212
 
 
213
/*
 
214
 * Merge a "clump" into the list of existing clumps for gimme_tree.
 
215
 *
 
216
 * We try to merge the clump into some existing clump, and repeat if
 
217
 * successful.  When no more merging is possible, insert the clump
 
218
 * into the list, preserving the list ordering rule (namely, that
 
219
 * clumps of larger size appear earlier).
 
220
 *
 
221
 * If force is true, merge anywhere a join is legal, even if it causes
 
222
 * a cartesian join to be performed.  When force is false, do only
 
223
 * "desirable" joins.
 
224
 */
 
225
static List *
 
226
merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, bool force)
 
227
{
 
228
        ListCell   *prev;
 
229
        ListCell   *lc;
 
230
 
 
231
        /* Look for a clump that new_clump can join to */
 
232
        prev = NULL;
 
233
        foreach(lc, clumps)
 
234
        {
 
235
                Clump      *old_clump = (Clump *) lfirst(lc);
 
236
 
 
237
                if (force ||
 
238
                        desirable_join(root, old_clump->joinrel, new_clump->joinrel))
 
239
                {
 
240
                        RelOptInfo *joinrel;
 
241
 
 
242
                        /*
 
243
                         * Construct a RelOptInfo representing the join of these two input
 
244
                         * relations.  Note that we expect the joinrel not to exist in
 
245
                         * root->join_rel_list yet, and so the paths constructed for it
 
246
                         * will only include the ones we want.
 
247
                         */
 
248
                        joinrel = make_join_rel(root,
 
249
                                                                        old_clump->joinrel,
 
250
                                                                        new_clump->joinrel);
 
251
 
 
252
                        /* Keep searching if join order is not valid */
 
253
                        if (joinrel)
 
254
                        {
 
255
                                /* Find and save the cheapest paths for this joinrel */
 
256
                                set_cheapest(joinrel);
 
257
 
 
258
                                /* Absorb new clump into old */
 
259
                                old_clump->joinrel = joinrel;
 
260
                                old_clump->size += new_clump->size;
 
261
                                pfree(new_clump);
 
262
 
 
263
                                /* Remove old_clump from list */
 
264
                                clumps = list_delete_cell(clumps, lc, prev);
 
265
 
 
266
                                /*
 
267
                                 * Recursively try to merge the enlarged old_clump with
 
268
                                 * others.      When no further merge is possible, we'll reinsert
 
269
                                 * it into the list.
 
270
                                 */
 
271
                                return merge_clump(root, clumps, old_clump, force);
 
272
                        }
 
273
                }
 
274
                prev = lc;
 
275
        }
 
276
 
 
277
        /*
 
278
         * No merging is possible, so add new_clump as an independent clump, in
 
279
         * proper order according to size.      We can be fast for the common case
 
280
         * where it has size 1 --- it should always go at the end.
 
281
         */
 
282
        if (clumps == NIL || new_clump->size == 1)
 
283
                return lappend(clumps, new_clump);
 
284
 
 
285
        /* Check if it belongs at the front */
 
286
        lc = list_head(clumps);
 
287
        if (new_clump->size > ((Clump *) lfirst(lc))->size)
 
288
                return lcons(new_clump, clumps);
 
289
 
 
290
        /* Else search for the place to insert it */
 
291
        for (;;)
 
292
        {
 
293
                ListCell   *nxt = lnext(lc);
 
294
 
 
295
                if (nxt == NULL || new_clump->size > ((Clump *) lfirst(nxt))->size)
 
296
                        break;                          /* it belongs after 'lc', before 'nxt' */
 
297
                lc = nxt;
 
298
        }
 
299
        lappend_cell(clumps, lc, new_clump);
 
300
 
 
301
        return clumps;
 
302
}
 
303
 
 
304
/*
 
305
 * Heuristics for gimme_tree: do we want to join these two relations?
 
306
 */
 
307
static bool
 
308
desirable_join(PlannerInfo *root,
 
309
                           RelOptInfo *outer_rel, RelOptInfo *inner_rel)
 
310
{
 
311
        /*
 
312
         * Join if there is an applicable join clause, or if there is a join order
 
313
         * restriction forcing these rels to be joined.
 
314
         */
 
315
        if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
 
316
                have_join_order_restriction(root, outer_rel, inner_rel))
 
317
                return true;
 
318
 
 
319
        /* Otherwise postpone the join till later. */
 
320
        return false;
 
321
}