1 /*------------------------------------------------------------------------
4 * solution of the query optimization problem
5 * by means of a Genetic Algorithm (GA)
7 * Copyright (c) 1994, Regents of the University of California
9 * $Id: geqo_main.c,v 1.11 1998/09/01 04:29:18 momjian Exp $
11 *-------------------------------------------------------------------------
15 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
16 * Martin Utesch * Institute of Automatic Control *
17 = = University of Mining and Technology =
18 * utesch@aut.tu-freiberg.de * Freiberg, Germany *
19 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
22 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
26 #include "nodes/pg_list.h"
27 #include "nodes/relation.h"
28 #include "nodes/plannodes.h"
29 #include "nodes/primnodes.h"
31 #include "utils/palloc.h"
32 #include "utils/elog.h"
34 #include "optimizer/internal.h"
35 #include "optimizer/paths.h"
36 #include "optimizer/pathnode.h"
37 #include "optimizer/clauses.h"
38 #include "optimizer/cost.h"
40 #include "optimizer/geqo_gene.h"
41 #include "optimizer/geqo.h"
42 #include "optimizer/geqo_pool.h"
43 #include "optimizer/geqo_selection.h"
44 #include "optimizer/geqo_recombination.h"
45 #include "optimizer/geqo_mutation.h"
46 #include "optimizer/geqo_misc.h"
49 /* define edge recombination crossover [ERX] per default */
50 #if !defined(ERX) && \
62 * solution of the query optimization problem
63 * similar to a constrained Traveling Salesman Problem (TSP)
75 Edge *edge_table; /* list of edges */
76 int edge_failures = 0;
81 #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
82 City *city_table; /* list of cities */
101 RelOptInfo *best_rel;
103 /* Plan *best_plan; */
107 number_of_rels = length(root->base_rel_list);
109 /* set GA parameters */
110 geqo_params(number_of_rels);/* out of "$PGDATA/pg_geqo" file */
111 pool_size = PoolSize;
112 number_generations = Generations;
113 status_interval = 10;
115 /* seed random number generator */
118 /* allocate genetic pool memory */
119 pool = alloc_pool(pool_size, number_of_rels);
121 /* random initialization of the pool */
122 random_init_pool(root, pool, 0, pool->size);
124 /* sort the pool according to cheapest path as fitness */
125 sort_pool(pool); /* we have to do it only one time, since
126 * all kids replace the worst individuals
127 * in future (-> geqo_pool.c:spread_chromo
130 /* allocate chromosome momma and daddy memory */
131 momma = alloc_chromo(pool->string_length);
132 daddy = alloc_chromo(pool->string_length);
135 elog(DEBUG, "geqo_main: using edge recombination crossover [ERX]");
136 /* allocate edge table memory */
137 edge_table = alloc_edge_table(pool->string_length);
139 elog(DEBUG, "geqo_main: using partially matched crossover [PMX]");
140 /* allocate chromosome kid memory */
141 kid = alloc_chromo(pool->string_length);
143 elog(DEBUG, "geqo_main: using cycle crossover [CX]");
144 /* allocate city table memory */
145 kid = alloc_chromo(pool->string_length);
146 city_table = alloc_city_table(pool->string_length);
148 elog(DEBUG, "geqo_main: using position crossover [PX]");
149 /* allocate city table memory */
150 kid = alloc_chromo(pool->string_length);
151 city_table = alloc_city_table(pool->string_length);
153 elog(DEBUG, "geqo_main: using order crossover [OX1]");
154 /* allocate city table memory */
155 kid = alloc_chromo(pool->string_length);
156 city_table = alloc_city_table(pool->string_length);
158 elog(DEBUG, "geqo_main: using order crossover [OX2]");
159 /* allocate city table memory */
160 kid = alloc_chromo(pool->string_length);
161 city_table = alloc_city_table(pool->string_length);
165 /* my pain main part: */
166 /* iterative optimization */
168 for (generation = 0; generation < number_generations; generation++)
172 geqo_selection(momma, daddy, pool, SelectionBias); /* using linear bias
178 /* EDGE RECOMBINATION CROSSOVER */
179 difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);
181 /* let the kid grow in momma's womb (storage) for nine months ;-) */
182 /* sleep(23328000) -- har har har */
185 /* are there any edge failures ? */
186 edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
188 /* PARTIALLY MATCHED CROSSOVER */
189 pmx(momma->string, daddy->string, kid->string, pool->string_length);
191 /* CYCLE CROSSOVER */
193 cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
194 /* mutate the child */
195 if (cycle_diffs == 0)
198 geqo_mutation(kid->string, pool->string_length);
201 /* POSITION CROSSOVER */
202 px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
204 /* ORDER CROSSOVER */
205 ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
207 /* ORDER CROSSOVER */
208 ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
212 /* EVALUATE FITNESS */
213 kid->worth = geqo_eval(root, kid->string, pool->string_length);
215 /* push the kid into the wilderness of life according to its worth */
216 spread_chromo(kid, pool);
220 if (status_interval && !(generation % status_interval))
221 print_gen(stdout, pool, generation);
224 } /* end of iterative optimization */
227 #if defined(ERX) && defined(GEQO_DEBUG)
228 if (edge_failures != 0)
229 fprintf(stdout, "\nFailures: %d Avg: %d\n", edge_failures, (int) generation / edge_failures);
232 fprintf(stdout, "No edge failures detected.\n");
236 #if defined(CX) && defined(GEQO_DEBUG)
238 fprintf(stdout, "\nMutations: %d Generations: %d\n", mutations, generation);
241 fprintf(stdout, "No mutations processed.\n");
246 fprintf(stdout, "\n");
247 print_pool(stdout, pool, 0, pool_size - 1);
251 /* got the cheapest query tree processed by geqo;
252 first element of the population indicates the best query tree */
254 best_tour = (Gene *) pool->data[0].string;
256 /* root->join_relation_list_ will be modified during this ! */
257 best_rel = (RelOptInfo *) gimme_tree(root, best_tour, 0, pool->string_length, NULL);
259 /* DBG: show the query plan
260 print_plan(best_plan, root);
263 /* ... free memory stuff */
268 free_edge_table(edge_table);
273 free_city_table(city_table);
276 free_city_table(city_table);
279 free_city_table(city_table);
282 free_city_table(city_table);