Line data Source code
1 : /*------------------------------------------------------------------------
2 : *
3 : * geqo_main.c
4 : * solution to the query optimization problem
5 : * by means of a Genetic Algorithm (GA)
6 : *
7 : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 : * Portions Copyright (c) 1994, Regents of the University of California
9 : *
10 : * src/backend/optimizer/geqo/geqo_main.c
11 : *
12 : *-------------------------------------------------------------------------
13 : */
14 :
15 : /* contributed by:
16 : =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
17 : * Martin Utesch * Institute of Automatic Control *
18 : = = University of Mining and Technology =
19 : * utesch@aut.tu-freiberg.de * Freiberg, Germany *
20 : =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
21 : */
22 :
23 : /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
24 :
25 : #include "postgres.h"
26 :
27 : #include <math.h>
28 :
29 : #include "optimizer/geqo.h"
30 :
31 : #include "optimizer/geqo_misc.h"
32 : #if defined(CX)
33 : #include "optimizer/geqo_mutation.h"
34 : #endif
35 : #include "optimizer/geqo_pool.h"
36 : #include "optimizer/geqo_random.h"
37 : #include "optimizer/geqo_recombination.h"
38 : #include "optimizer/geqo_selection.h"
39 :
40 :
41 : /*
42 : * Configuration options
43 : */
44 : int Geqo_effort;
45 : int Geqo_pool_size;
46 : int Geqo_generations;
47 : double Geqo_selection_bias;
48 : double Geqo_seed;
49 :
50 :
51 : static int gimme_pool_size(int nr_rel);
52 : static int gimme_number_generations(int pool_size);
53 :
54 : /* complain if no recombination mechanism is #define'd */
55 : #if !defined(ERX) && \
56 : !defined(PMX) && \
57 : !defined(CX) && \
58 : !defined(PX) && \
59 : !defined(OX1) && \
60 : !defined(OX2)
61 : #error "must choose one GEQO recombination mechanism in geqo.h"
62 : #endif
63 :
64 :
65 : /*
66 : * geqo
67 : * solution of the query optimization problem
68 : * similar to a constrained Traveling Salesman Problem (TSP)
69 : */
70 :
71 : RelOptInfo *
72 6 : geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
73 : {
74 : GeqoPrivateData private;
75 : int generation;
76 : Chromosome *momma;
77 : Chromosome *daddy;
78 : Chromosome *kid;
79 : Pool *pool;
80 : int pool_size,
81 : number_generations;
82 :
83 : #ifdef GEQO_DEBUG
84 : int status_interval;
85 : #endif
86 : Gene *best_tour;
87 : RelOptInfo *best_rel;
88 :
89 : #if defined(ERX)
90 : Edge *edge_table; /* list of edges */
91 6 : int edge_failures = 0;
92 : #endif
93 : #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
94 : City *city_table; /* list of cities */
95 : #endif
96 : #if defined(CX)
97 : int cycle_diffs = 0;
98 : int mutations = 0;
99 : #endif
100 :
101 : /* set up private information */
102 6 : root->join_search_private = (void *) &private;
103 6 : private.initial_rels = initial_rels;
104 :
105 : /* initialize private number generator */
106 6 : geqo_set_seed(root, Geqo_seed);
107 :
108 : /* set GA parameters */
109 6 : pool_size = gimme_pool_size(number_of_rels);
110 6 : number_generations = gimme_number_generations(pool_size);
111 : #ifdef GEQO_DEBUG
112 : status_interval = 10;
113 : #endif
114 :
115 : /* allocate genetic pool memory */
116 6 : pool = alloc_pool(root, pool_size, number_of_rels);
117 :
118 : /* random initialization of the pool */
119 6 : random_init_pool(root, pool);
120 :
121 : /* sort the pool according to cheapest path as fitness */
122 6 : sort_pool(root, pool); /* we have to do it only one time, since all
123 : * kids replace the worst individuals in
124 : * future (-> geqo_pool.c:spread_chromo ) */
125 :
126 : #ifdef GEQO_DEBUG
127 : elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
128 : pool_size,
129 : pool->data[0].worth,
130 : pool->data[pool_size - 1].worth);
131 : #endif
132 :
133 : /* allocate chromosome momma and daddy memory */
134 6 : momma = alloc_chromo(root, pool->string_length);
135 6 : daddy = alloc_chromo(root, pool->string_length);
136 :
137 : #if defined (ERX)
138 : #ifdef GEQO_DEBUG
139 : elog(DEBUG2, "using edge recombination crossover [ERX]");
140 : #endif
141 : /* allocate edge table memory */
142 6 : edge_table = alloc_edge_table(root, pool->string_length);
143 : #elif defined(PMX)
144 : #ifdef GEQO_DEBUG
145 : elog(DEBUG2, "using partially matched crossover [PMX]");
146 : #endif
147 : /* allocate chromosome kid memory */
148 : kid = alloc_chromo(root, pool->string_length);
149 : #elif defined(CX)
150 : #ifdef GEQO_DEBUG
151 : elog(DEBUG2, "using cycle crossover [CX]");
152 : #endif
153 : /* allocate city table memory */
154 : kid = alloc_chromo(root, pool->string_length);
155 : city_table = alloc_city_table(root, pool->string_length);
156 : #elif defined(PX)
157 : #ifdef GEQO_DEBUG
158 : elog(DEBUG2, "using position crossover [PX]");
159 : #endif
160 : /* allocate city table memory */
161 : kid = alloc_chromo(root, pool->string_length);
162 : city_table = alloc_city_table(root, pool->string_length);
163 : #elif defined(OX1)
164 : #ifdef GEQO_DEBUG
165 : elog(DEBUG2, "using order crossover [OX1]");
166 : #endif
167 : /* allocate city table memory */
168 : kid = alloc_chromo(root, pool->string_length);
169 : city_table = alloc_city_table(root, pool->string_length);
170 : #elif defined(OX2)
171 : #ifdef GEQO_DEBUG
172 : elog(DEBUG2, "using order crossover [OX2]");
173 : #endif
174 : /* allocate city table memory */
175 : kid = alloc_chromo(root, pool->string_length);
176 : city_table = alloc_city_table(root, pool->string_length);
177 : #endif
178 :
179 :
180 : /* my pain main part: */
181 : /* iterative optimization */
182 :
183 390 : for (generation = 0; generation < number_generations; generation++)
184 : {
185 : /* SELECTION: using linear bias function */
186 384 : geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
187 :
188 : #if defined (ERX)
189 : /* EDGE RECOMBINATION CROSSOVER */
190 384 : gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
191 :
192 384 : kid = momma;
193 :
194 : /* are there any edge failures ? */
195 384 : edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
196 : #elif defined(PMX)
197 : /* PARTIALLY MATCHED CROSSOVER */
198 : pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
199 : #elif defined(CX)
200 : /* CYCLE CROSSOVER */
201 : cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
202 : /* mutate the child */
203 : if (cycle_diffs == 0)
204 : {
205 : mutations++;
206 : geqo_mutation(root, kid->string, pool->string_length);
207 : }
208 : #elif defined(PX)
209 : /* POSITION CROSSOVER */
210 : px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
211 : #elif defined(OX1)
212 : /* ORDER CROSSOVER */
213 : ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
214 : #elif defined(OX2)
215 : /* ORDER CROSSOVER */
216 : ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
217 : #endif
218 :
219 :
220 : /* EVALUATE FITNESS */
221 384 : kid->worth = geqo_eval(root, kid->string, pool->string_length);
222 :
223 : /* push the kid into the wilderness of life according to its worth */
224 384 : spread_chromo(root, kid, pool);
225 :
226 :
227 : #ifdef GEQO_DEBUG
228 : if (status_interval && !(generation % status_interval))
229 : print_gen(stdout, pool, generation);
230 : #endif
231 :
232 : }
233 :
234 :
235 : #if defined(ERX)
236 : #if defined(GEQO_DEBUG)
237 : if (edge_failures != 0)
238 : elog(LOG, "[GEQO] failures: %d, average: %d",
239 : edge_failures, (int) number_generations / edge_failures);
240 : else
241 : elog(LOG, "[GEQO] no edge failures detected");
242 : #else
243 : /* suppress variable-set-but-not-used warnings from some compilers */
244 : (void) edge_failures;
245 : #endif
246 : #endif
247 :
248 : #if defined(CX) && defined(GEQO_DEBUG)
249 : if (mutations != 0)
250 : elog(LOG, "[GEQO] mutations: %d, generations: %d",
251 : mutations, number_generations);
252 : else
253 : elog(LOG, "[GEQO] no mutations processed");
254 : #endif
255 :
256 : #ifdef GEQO_DEBUG
257 : print_pool(stdout, pool, 0, pool_size - 1);
258 : #endif
259 :
260 : #ifdef GEQO_DEBUG
261 : elog(DEBUG1, "GEQO best is %.2f after %d generations",
262 : pool->data[0].worth, number_generations);
263 : #endif
264 :
265 :
266 : /*
267 : * got the cheapest query tree processed by geqo; first element of the
268 : * population indicates the best query tree
269 : */
270 6 : best_tour = (Gene *) pool->data[0].string;
271 :
272 6 : best_rel = gimme_tree(root, best_tour, pool->string_length);
273 :
274 6 : if (best_rel == NULL)
275 0 : elog(ERROR, "geqo failed to make a valid plan");
276 :
277 : /* DBG: show the query plan */
278 : #ifdef NOT_USED
279 : print_plan(best_plan, root);
280 : #endif
281 :
282 : /* ... free memory stuff */
283 6 : free_chromo(root, momma);
284 6 : free_chromo(root, daddy);
285 :
286 : #if defined (ERX)
287 6 : free_edge_table(root, edge_table);
288 : #elif defined(PMX)
289 : free_chromo(root, kid);
290 : #elif defined(CX)
291 : free_chromo(root, kid);
292 : free_city_table(root, city_table);
293 : #elif defined(PX)
294 : free_chromo(root, kid);
295 : free_city_table(root, city_table);
296 : #elif defined(OX1)
297 : free_chromo(root, kid);
298 : free_city_table(root, city_table);
299 : #elif defined(OX2)
300 : free_chromo(root, kid);
301 : free_city_table(root, city_table);
302 : #endif
303 :
304 6 : free_pool(root, pool);
305 :
306 : /* ... clear root pointer to our private storage */
307 6 : root->join_search_private = NULL;
308 :
309 6 : return best_rel;
310 : }
311 :
312 :
313 : /*
314 : * Return either configured pool size or a good default
315 : *
316 : * The default is based on query size (no. of relations) = 2^(QS+1),
317 : * but constrained to a range based on the effort value.
318 : */
319 : static int
320 6 : gimme_pool_size(int nr_rel)
321 : {
322 : double size;
323 : int minsize;
324 : int maxsize;
325 :
326 : /* Legal pool size *must* be at least 2, so ignore attempt to select 1 */
327 6 : if (Geqo_pool_size >= 2)
328 0 : return Geqo_pool_size;
329 :
330 6 : size = pow(2.0, nr_rel + 1.0);
331 :
332 6 : maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
333 6 : if (size > maxsize)
334 0 : return maxsize;
335 :
336 6 : minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
337 6 : if (size < minsize)
338 0 : return minsize;
339 :
340 6 : return (int) ceil(size);
341 : }
342 :
343 :
344 : /*
345 : * Return either configured number of generations or a good default
346 : *
347 : * The default is the same as the pool size, which allows us to be
348 : * sure that less-fit individuals get pushed out of the breeding
349 : * population before the run finishes.
350 : */
351 : static int
352 6 : gimme_number_generations(int pool_size)
353 : {
354 6 : if (Geqo_generations > 0)
355 0 : return Geqo_generations;
356 :
357 6 : return pool_size;
358 : }
|
