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 *
7777 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 */
10604 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 : :
396 rhaas@postgresql.org 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);
6275 tgl@sss.pgh.pa.us 109 : 35 : private.initial_rels = initial_rels;
110 : :
111 : : /* inform core planner that we may replan */
396 rhaas@postgresql.org 112 : 35 : root->assumeReplanning = true;
113 : :
114 : : /* initialize private number generator */
6275 tgl@sss.pgh.pa.us 115 : 35 : geqo_set_seed(root, Geqo_seed);
116 : :
117 : : /* set GA parameters */
9608 peter_e@gmx.net 118 : 35 : pool_size = gimme_pool_size(number_of_rels);
8278 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 */
6275 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<%d>, worst %.2f<%d>",
137 : : pool_size,
138 : : pool->data[0].worth.cost,
139 : : pool->data[0].worth.disabled_nodes,
140 : : pool->data[pool_size - 1].worth.cost,
141 : : pool->data[pool_size - 1].worth.disabled_nodes);
142 : : #endif
143 : :
144 : : /* allocate chromosome momma and daddy memory */
145 : 35 : momma = alloc_chromo(root, pool->string_length);
146 : 35 : daddy = alloc_chromo(root, pool->string_length);
147 : :
148 : : #if defined (ERX)
149 : : #ifdef GEQO_DEBUG
150 : : elog(DEBUG2, "using edge recombination crossover [ERX]");
151 : : #endif
152 : : /* allocate edge table memory */
153 : 35 : edge_table = alloc_edge_table(root, pool->string_length);
154 : : #elif defined(PMX)
155 : : #ifdef GEQO_DEBUG
156 : : elog(DEBUG2, "using partially matched crossover [PMX]");
157 : : #endif
158 : : /* allocate chromosome kid memory */
159 : : kid = alloc_chromo(root, pool->string_length);
160 : : #elif defined(CX)
161 : : #ifdef GEQO_DEBUG
162 : : elog(DEBUG2, "using cycle crossover [CX]");
163 : : #endif
164 : : /* allocate city table memory */
165 : : kid = alloc_chromo(root, pool->string_length);
166 : : city_table = alloc_city_table(root, pool->string_length);
167 : : #elif defined(PX)
168 : : #ifdef GEQO_DEBUG
169 : : elog(DEBUG2, "using position crossover [PX]");
170 : : #endif
171 : : /* allocate city table memory */
172 : : kid = alloc_chromo(root, pool->string_length);
173 : : city_table = alloc_city_table(root, pool->string_length);
174 : : #elif defined(OX1)
175 : : #ifdef GEQO_DEBUG
176 : : elog(DEBUG2, "using order crossover [OX1]");
177 : : #endif
178 : : /* allocate city table memory */
179 : : kid = alloc_chromo(root, pool->string_length);
180 : : city_table = alloc_city_table(root, pool->string_length);
181 : : #elif defined(OX2)
182 : : #ifdef GEQO_DEBUG
183 : : elog(DEBUG2, "using order crossover [OX2]");
184 : : #endif
185 : : /* allocate city table memory */
186 : : kid = alloc_chromo(root, pool->string_length);
187 : : city_table = alloc_city_table(root, pool->string_length);
188 : : #endif
189 : :
190 : :
191 : : /* my pain main part: */
192 : : /* iterative optimization */
193 : :
10605 bruce@momjian.us 194 [ + + ]: 1855 : for (generation = 0; generation < number_generations; generation++)
195 : : {
196 : : /* SELECTION: using linear bias function */
6275 tgl@sss.pgh.pa.us 197 : 1820 : geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
198 : :
199 : : #if defined (ERX)
200 : : /* EDGE RECOMBINATION CROSSOVER */
5641 peter_e@gmx.net 201 : 1820 : gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
202 : :
10605 bruce@momjian.us 203 : 1820 : kid = momma;
204 : :
205 : : /* are there any edge failures ? */
6275 tgl@sss.pgh.pa.us 206 : 1820 : edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
207 : : #elif defined(PMX)
208 : : /* PARTIALLY MATCHED CROSSOVER */
209 : : pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
210 : : #elif defined(CX)
211 : : /* CYCLE CROSSOVER */
212 : : cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
213 : : /* mutate the child */
214 : : if (cycle_diffs == 0)
215 : : {
216 : : mutations++;
217 : : geqo_mutation(root, kid->string, pool->string_length);
218 : : }
219 : : #elif defined(PX)
220 : : /* POSITION CROSSOVER */
221 : : px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
222 : : #elif defined(OX1)
223 : : /* ORDER CROSSOVER */
224 : : ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
225 : : #elif defined(OX2)
226 : : /* ORDER CROSSOVER */
227 : : ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
228 : : #endif
229 : :
230 : :
231 : : /* EVALUATE FITNESS */
232 : 1820 : kid->worth = geqo_eval(root, kid->string, pool->string_length);
233 : :
234 : : /* push the kid into the wilderness of life according to its worth */
235 : 1820 : spread_chromo(root, kid, pool);
236 : :
237 : :
238 : : #ifdef GEQO_DEBUG
239 : : if (status_interval && !(generation % status_interval))
240 : : print_gen(stdout, pool, generation);
241 : : #endif
242 : :
243 : : }
244 : :
245 : :
246 : : #if defined(ERX)
247 : : #if defined(GEQO_DEBUG)
248 : : if (edge_failures != 0)
249 : : elog(LOG, "[GEQO] failures: %d, average: %d",
250 : : edge_failures, (int) number_generations / edge_failures);
251 : : else
252 : : elog(LOG, "[GEQO] no edge failures detected");
253 : : #else
254 : : /* suppress variable-set-but-not-used warnings from some compilers */
255 : : (void) edge_failures;
256 : : #endif
257 : : #endif
258 : :
259 : : #if defined(CX) && defined(GEQO_DEBUG)
260 : : if (mutations != 0)
261 : : elog(LOG, "[GEQO] mutations: %d, generations: %d",
262 : : mutations, number_generations);
263 : : else
264 : : elog(LOG, "[GEQO] no mutations processed");
265 : : #endif
266 : :
267 : : #ifdef GEQO_DEBUG
268 : : print_pool(stdout, pool, 0, pool_size - 1);
269 : : #endif
270 : :
271 : : #ifdef GEQO_DEBUG
272 : : elog(DEBUG1, "GEQO best is %.2f<%d> after %d generations",
273 : : pool->data[0].worth.cost, pool->data[0].worth.disabled_nodes,
274 : : number_generations);
275 : : #endif
276 : :
277 : :
278 : : /*
279 : : * got the cheapest query tree processed by geqo; first element of the
280 : : * population indicates the best query tree
281 : : */
10605 bruce@momjian.us 282 : 35 : best_tour = (Gene *) pool->data[0].string;
283 : :
6275 tgl@sss.pgh.pa.us 284 : 35 : best_rel = gimme_tree(root, best_tour, pool->string_length);
285 : :
4240 286 [ - + ]: 35 : if (best_rel == NULL)
4240 tgl@sss.pgh.pa.us 287 [ # # ]:UBC 0 : elog(ERROR, "geqo failed to make a valid plan");
288 : :
289 : : /* DBG: show the query plan */
290 : : #ifdef NOT_USED
291 : : print_plan(best_plan, root);
292 : : #endif
293 : :
294 : : /* ... free memory stuff */
6275 tgl@sss.pgh.pa.us 295 :CBC 35 : free_chromo(root, momma);
296 : 35 : free_chromo(root, daddy);
297 : :
298 : : #if defined (ERX)
299 : 35 : free_edge_table(root, edge_table);
300 : : #elif defined(PMX)
301 : : free_chromo(root, kid);
302 : : #elif defined(CX)
303 : : free_chromo(root, kid);
304 : : free_city_table(root, city_table);
305 : : #elif defined(PX)
306 : : free_chromo(root, kid);
307 : : free_city_table(root, city_table);
308 : : #elif defined(OX1)
309 : : free_chromo(root, kid);
310 : : free_city_table(root, city_table);
311 : : #elif defined(OX2)
312 : : free_chromo(root, kid);
313 : : free_city_table(root, city_table);
314 : : #endif
315 : :
316 : 35 : free_pool(root, pool);
317 : :
318 : : /* ... clear root pointer to our private storage */
396 rhaas@postgresql.org 319 : 35 : SetPlannerInfoExtensionState(root, Geqo_planner_extension_id, NULL);
320 : :
10246 bruce@momjian.us 321 : 35 : return best_rel;
322 : : }
323 : :
324 : :
325 : : /*
326 : : * Return either configured pool size or a good default
327 : : *
328 : : * The default is based on query size (no. of relations) = 2^(QS+1),
329 : : * but constrained to a range based on the effort value.
330 : : */
331 : : static int
9608 peter_e@gmx.net 332 : 35 : gimme_pool_size(int nr_rel)
333 : : {
334 : : double size;
335 : : int minsize;
336 : : int maxsize;
337 : :
338 : : /* Legal pool size *must* be at least 2, so ignore attempt to select 1 */
8276 tgl@sss.pgh.pa.us 339 [ - + ]: 35 : if (Geqo_pool_size >= 2)
8828 bruce@momjian.us 340 :UBC 0 : return Geqo_pool_size;
341 : :
9608 peter_e@gmx.net 342 :CBC 35 : size = pow(2.0, nr_rel + 1.0);
343 : :
8057 bruce@momjian.us 344 : 35 : maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
8276 tgl@sss.pgh.pa.us 345 [ - + ]: 35 : if (size > maxsize)
8276 tgl@sss.pgh.pa.us 346 :UBC 0 : return maxsize;
347 : :
8057 bruce@momjian.us 348 :CBC 35 : minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
8276 tgl@sss.pgh.pa.us 349 [ + + ]: 35 : if (size < minsize)
350 : 30 : return minsize;
351 : :
352 : 5 : return (int) ceil(size);
353 : : }
354 : :
355 : :
356 : : /*
357 : : * Return either configured number of generations or a good default
358 : : *
359 : : * The default is the same as the pool size, which allows us to be
360 : : * sure that less-fit individuals get pushed out of the breeding
361 : : * population before the run finishes.
362 : : */
363 : : static int
8278 364 : 35 : gimme_number_generations(int pool_size)
365 : : {
366 [ - + ]: 35 : if (Geqo_generations > 0)
9313 bruce@momjian.us 367 :UBC 0 : return Geqo_generations;
368 : :
8276 tgl@sss.pgh.pa.us 369 :CBC 35 : return pool_size;
370 : : }
|
