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