Age Owner Branch data 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-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 *
7664 tgl@sss.pgh.pa.us 75 :CBC 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 */
10491 bruce@momjian.us 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 : :
283 rhaas@postgresql.org 104 [ + + ]:GNC 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);
6162 tgl@sss.pgh.pa.us 109 :CBC 35 : private.initial_rels = initial_rels;
110 : :
111 : : /* inform core planner that we may replan */
283 rhaas@postgresql.org 112 :GNC 35 : root->assumeReplanning = true;
113 : :
114 : : /* initialize private number generator */
6162 tgl@sss.pgh.pa.us 115 :CBC 35 : geqo_set_seed(root, Geqo_seed);
116 : :
117 : : /* set GA parameters */
9495 peter_e@gmx.net 118 : 35 : pool_size = gimme_pool_size(number_of_rels);
8165 tgl@sss.pgh.pa.us 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 */
6162 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 : :
10492 bruce@momjian.us 192 [ + + ]: 1855 : for (generation = 0; generation < number_generations; generation++)
193 : : {
194 : : /* SELECTION: using linear bias function */
6162 tgl@sss.pgh.pa.us 195 : 1820 : geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
196 : :
197 : : #if defined (ERX)
198 : : /* EDGE RECOMBINATION CROSSOVER */
5528 peter_e@gmx.net 199 : 1820 : gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
200 : :
10492 bruce@momjian.us 201 : 1820 : kid = momma;
202 : :
203 : : /* are there any edge failures ? */
6162 tgl@sss.pgh.pa.us 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 : : */
10492 bruce@momjian.us 279 : 35 : best_tour = (Gene *) pool->data[0].string;
280 : :
6162 tgl@sss.pgh.pa.us 281 : 35 : best_rel = gimme_tree(root, best_tour, pool->string_length);
282 : :
4127 283 [ - + ]: 35 : if (best_rel == NULL)
4127 tgl@sss.pgh.pa.us 284 [ # # ]:UBC 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 */
6162 tgl@sss.pgh.pa.us 292 :CBC 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 */
283 rhaas@postgresql.org 316 :GNC 35 : SetPlannerInfoExtensionState(root, Geqo_planner_extension_id, NULL);
317 : :
10133 bruce@momjian.us 318 :CBC 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
9495 peter_e@gmx.net 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 */
8163 tgl@sss.pgh.pa.us 336 [ - + ]: 35 : if (Geqo_pool_size >= 2)
8715 bruce@momjian.us 337 :UBC 0 : return Geqo_pool_size;
338 : :
9495 peter_e@gmx.net 339 :CBC 35 : size = pow(2.0, nr_rel + 1.0);
340 : :
7944 bruce@momjian.us 341 : 35 : maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
8163 tgl@sss.pgh.pa.us 342 [ - + ]: 35 : if (size > maxsize)
8163 tgl@sss.pgh.pa.us 343 :UBC 0 : return maxsize;
344 : :
7944 bruce@momjian.us 345 :CBC 35 : minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
8163 tgl@sss.pgh.pa.us 346 [ + + ]: 35 : if (size < minsize)
8163 tgl@sss.pgh.pa.us 347 :GBC 30 : return minsize;
348 : :
8163 tgl@sss.pgh.pa.us 349 :CBC 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
8165 361 : 35 : gimme_number_generations(int pool_size)
362 : : {
363 [ - + ]: 35 : if (Geqo_generations > 0)
9200 bruce@momjian.us 364 :UBC 0 : return Geqo_generations;
365 : :
8163 tgl@sss.pgh.pa.us 366 :CBC 35 : return pool_size;
367 : : }
|
