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