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