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-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 *
7450 tgl@sss.pgh.pa.us 74 :CBC 21 : 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 */
10277 bruce@momjian.us 93 : 21 : 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 : :
69 rhaas@postgresql.org 103 [ + + ]:GNC 21 : if (Geqo_planner_extension_id < 0)
104 : 6 : Geqo_planner_extension_id = GetPlannerExtensionId("geqo");
105 : :
106 : : /* set up private information */
107 : 21 : SetPlannerInfoExtensionState(root, Geqo_planner_extension_id, &private);
5948 tgl@sss.pgh.pa.us 108 :CBC 21 : private.initial_rels = initial_rels;
109 : :
110 : : /* inform core planner that we may replan */
69 rhaas@postgresql.org 111 :GNC 21 : root->assumeReplanning = true;
112 : :
113 : : /* initialize private number generator */
5948 tgl@sss.pgh.pa.us 114 :CBC 21 : geqo_set_seed(root, Geqo_seed);
115 : :
116 : : /* set GA parameters */
9281 peter_e@gmx.net 117 : 21 : pool_size = gimme_pool_size(number_of_rels);
7951 tgl@sss.pgh.pa.us 118 : 21 : number_generations = gimme_number_generations(pool_size);
119 : : #ifdef GEQO_DEBUG
120 : : status_interval = 10;
121 : : #endif
122 : :
123 : : /* allocate genetic pool memory */
5948 124 : 21 : pool = alloc_pool(root, pool_size, number_of_rels);
125 : :
126 : : /* random initialization of the pool */
127 : 21 : random_init_pool(root, pool);
128 : :
129 : : /* sort the pool according to cheapest path as fitness */
130 : 21 : 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 : 21 : momma = alloc_chromo(root, pool->string_length);
143 : 21 : 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 : 21 : 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 : :
10278 bruce@momjian.us 191 [ + + ]: 1113 : for (generation = 0; generation < number_generations; generation++)
192 : : {
193 : : /* SELECTION: using linear bias function */
5948 tgl@sss.pgh.pa.us 194 : 1092 : geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
195 : :
196 : : #if defined (ERX)
197 : : /* EDGE RECOMBINATION CROSSOVER */
5314 peter_e@gmx.net 198 : 1092 : gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
199 : :
10278 bruce@momjian.us 200 : 1092 : kid = momma;
201 : :
202 : : /* are there any edge failures ? */
5948 tgl@sss.pgh.pa.us 203 : 1092 : 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 : 1092 : 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 : 1092 : 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 : : */
10278 bruce@momjian.us 278 : 21 : best_tour = (Gene *) pool->data[0].string;
279 : :
5948 tgl@sss.pgh.pa.us 280 : 21 : best_rel = gimme_tree(root, best_tour, pool->string_length);
281 : :
3913 282 [ - + ]: 21 : if (best_rel == NULL)
3913 tgl@sss.pgh.pa.us 283 [ # # ]:UBC 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 */
5948 tgl@sss.pgh.pa.us 291 :CBC 21 : free_chromo(root, momma);
292 : 21 : free_chromo(root, daddy);
293 : :
294 : : #if defined (ERX)
295 : 21 : 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 : 21 : free_pool(root, pool);
313 : :
314 : : /* ... clear root pointer to our private storage */
69 rhaas@postgresql.org 315 :GNC 21 : SetPlannerInfoExtensionState(root, Geqo_planner_extension_id, NULL);
316 : :
9919 bruce@momjian.us 317 :CBC 21 : 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
9281 peter_e@gmx.net 328 : 21 : 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 */
7949 tgl@sss.pgh.pa.us 335 [ - + ]: 21 : if (Geqo_pool_size >= 2)
8501 bruce@momjian.us 336 :UBC 0 : return Geqo_pool_size;
337 : :
9281 peter_e@gmx.net 338 :CBC 21 : size = pow(2.0, nr_rel + 1.0);
339 : :
7730 bruce@momjian.us 340 : 21 : maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
7949 tgl@sss.pgh.pa.us 341 [ - + ]: 21 : if (size > maxsize)
7949 tgl@sss.pgh.pa.us 342 :UBC 0 : return maxsize;
343 : :
7730 bruce@momjian.us 344 :CBC 21 : minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
7949 tgl@sss.pgh.pa.us 345 [ + + ]: 21 : if (size < minsize)
7949 tgl@sss.pgh.pa.us 346 :GBC 18 : return minsize;
347 : :
7949 tgl@sss.pgh.pa.us 348 :CBC 3 : 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
7951 360 : 21 : gimme_number_generations(int pool_size)
361 : : {
362 [ - + ]: 21 : if (Geqo_generations > 0)
8986 bruce@momjian.us 363 :UBC 0 : return Geqo_generations;
364 : :
7949 tgl@sss.pgh.pa.us 365 :CBC 21 : return pool_size;
366 : : }
|
