1 /*------------------------------------------------------------------------
4 * solution of the query optimization problem
5 * by means of a Genetic Algorithm (GA)
7 * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
8 * Portions Copyright (c) 1994, Regents of the University of California
10 * $Id: geqo_main.c,v 1.24 2000/09/19 18:42:33 tgl Exp $
12 *-------------------------------------------------------------------------
16 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
17 * Martin Utesch * Institute of Automatic Control *
18 = = University of Mining and Technology =
19 * utesch@aut.tu-freiberg.de * Freiberg, Germany *
20 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
23 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
30 #include "optimizer/geqo.h"
31 #include "optimizer/geqo_misc.h"
32 #include "optimizer/geqo_pool.h"
33 #include "optimizer/geqo_selection.h"
37 * Configuration options
42 double Geqo_selection_bias;
46 static int gimme_pool_size(int nr_rel);
47 static int gimme_number_generations(int pool_size, int effort);
50 /* define edge recombination crossover [ERX] per default */
51 #if !defined(ERX) && \
63 * solution of the query optimization problem
64 * similar to a constrained Traveling Salesman Problem (TSP)
68 geqo(Query *root, int number_of_rels, List *initial_rels)
82 Edge *edge_table; /* list of edges */
83 int edge_failures = 0;
87 #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
88 City *city_table; /* list of cities */
97 /* set GA parameters */
98 pool_size = gimme_pool_size(number_of_rels);
99 number_generations = gimme_number_generations(pool_size, Geqo_effort);
100 status_interval = 10;
102 /* seed random number generator */
103 /* XXX why is this done every time around? */
104 if (Geqo_random_seed >= 0)
105 srandom((unsigned int) Geqo_random_seed);
107 srandom((unsigned int) time(NULL));
109 /* allocate genetic pool memory */
110 pool = alloc_pool(pool_size, number_of_rels);
112 /* random initialization of the pool */
113 random_init_pool(root, initial_rels, pool, 0, pool->size);
115 /* sort the pool according to cheapest path as fitness */
116 sort_pool(pool); /* we have to do it only one time, since
117 * all kids replace the worst individuals
118 * in future (-> geqo_pool.c:spread_chromo
121 /* allocate chromosome momma and daddy memory */
122 momma = alloc_chromo(pool->string_length);
123 daddy = alloc_chromo(pool->string_length);
126 elog(DEBUG, "geqo_main: using edge recombination crossover [ERX]");
127 /* allocate edge table memory */
128 edge_table = alloc_edge_table(pool->string_length);
130 elog(DEBUG, "geqo_main: using partially matched crossover [PMX]");
131 /* allocate chromosome kid memory */
132 kid = alloc_chromo(pool->string_length);
134 elog(DEBUG, "geqo_main: using cycle crossover [CX]");
135 /* allocate city table memory */
136 kid = alloc_chromo(pool->string_length);
137 city_table = alloc_city_table(pool->string_length);
139 elog(DEBUG, "geqo_main: using position crossover [PX]");
140 /* allocate city table memory */
141 kid = alloc_chromo(pool->string_length);
142 city_table = alloc_city_table(pool->string_length);
144 elog(DEBUG, "geqo_main: using order crossover [OX1]");
145 /* allocate city table memory */
146 kid = alloc_chromo(pool->string_length);
147 city_table = alloc_city_table(pool->string_length);
149 elog(DEBUG, "geqo_main: using order crossover [OX2]");
150 /* allocate city table memory */
151 kid = alloc_chromo(pool->string_length);
152 city_table = alloc_city_table(pool->string_length);
156 /* my pain main part: */
157 /* iterative optimization */
159 for (generation = 0; generation < number_generations; generation++)
163 geqo_selection(momma, daddy, pool, Geqo_selection_bias);/* using linear bias
169 /* EDGE RECOMBINATION CROSSOVER */
170 difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);
172 /* let the kid grow in momma's womb (storage) for nine months ;-) */
173 /* sleep(23328000) -- har har har */
176 /* are there any edge failures ? */
177 edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
179 /* PARTIALLY MATCHED CROSSOVER */
180 pmx(momma->string, daddy->string, kid->string, pool->string_length);
182 /* CYCLE CROSSOVER */
183 cycle_diffs = cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
184 /* mutate the child */
185 if (cycle_diffs == 0)
188 geqo_mutation(kid->string, pool->string_length);
191 /* POSITION CROSSOVER */
192 px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
194 /* ORDER CROSSOVER */
195 ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
197 /* ORDER CROSSOVER */
198 ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
202 /* EVALUATE FITNESS */
203 kid->worth = geqo_eval(root, initial_rels,
204 kid->string, pool->string_length);
206 /* push the kid into the wilderness of life according to its worth */
207 spread_chromo(kid, pool);
211 if (status_interval && !(generation % status_interval))
212 print_gen(stdout, pool, generation);
215 } /* end of iterative optimization */
218 #if defined(ERX) && defined(GEQO_DEBUG)
219 if (edge_failures != 0)
220 fprintf(stdout, "\nFailures: %d Avg: %d\n", edge_failures, (int) generation / edge_failures);
223 fprintf(stdout, "No edge failures detected.\n");
227 #if defined(CX) && defined(GEQO_DEBUG)
229 fprintf(stdout, "\nMutations: %d Generations: %d\n", mutations, generation);
232 fprintf(stdout, "No mutations processed.\n");
237 fprintf(stdout, "\n");
238 print_pool(stdout, pool, 0, pool_size - 1);
242 /* got the cheapest query tree processed by geqo;
243 first element of the population indicates the best query tree */
245 best_tour = (Gene *) pool->data[0].string;
247 /* root->join_rel_list will be modified during this ! */
248 best_rel = (RelOptInfo *) gimme_tree(root, initial_rels,
249 best_tour, pool->string_length,
252 /* DBG: show the query plan
253 print_plan(best_plan, root);
256 /* ... free memory stuff */
261 free_edge_table(edge_table);
266 free_city_table(city_table);
269 free_city_table(city_table);
272 free_city_table(city_table);
275 free_city_table(city_table);
286 * Return either configured pool size or
287 * a good default based on query size (no. of relations)
289 * also constrain between 128 and 1024
292 gimme_pool_size(int nr_rel)
296 if (Geqo_pool_size != 0)
298 if (Geqo_pool_size < MIN_GEQO_POOL_SIZE)
299 return MIN_GEQO_POOL_SIZE;
300 else if (Geqo_pool_size > MAX_GEQO_POOL_SIZE)
301 return MAX_GEQO_POOL_SIZE;
303 return Geqo_pool_size;
306 size = pow(2.0, nr_rel + 1.0);
308 if (size < MIN_GEQO_POOL_SIZE)
309 return MIN_GEQO_POOL_SIZE;
310 else if (size > MAX_GEQO_POOL_SIZE)
311 return MAX_GEQO_POOL_SIZE;
313 return (int) ceil(size);
319 * Return either configured number of generations or
320 * some reasonable default calculated on the fly.
321 * = Effort * Log2(PoolSize)
324 gimme_number_generations(int pool_size, int effort)
326 if (Geqo_generations <= 0)
327 return effort * (int) ceil(log((double) pool_size) / log(2.0));
329 return Geqo_generations;