PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_main.c
Go to the documentation of this file.
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-2017, 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_misc.h"
31 #include "optimizer/geqo_pool.h"
32 #include "optimizer/geqo_random.h"
34 
35 
36 /*
37  * Configuration options
38  */
43 double Geqo_seed;
44 
45 
46 static int gimme_pool_size(int nr_rel);
47 static int gimme_number_generations(int pool_size);
48 
49 /* define edge recombination crossover [ERX] per default */
50 #if !defined(ERX) && \
51  !defined(PMX) && \
52  !defined(CX) && \
53  !defined(PX) && \
54  !defined(OX1) && \
55  !defined(OX2)
56 #define ERX
57 #endif
58 
59 
60 /*
61  * geqo
62  * solution of the query optimization problem
63  * similar to a constrained Traveling Salesman Problem (TSP)
64  */
65 
66 RelOptInfo *
67 geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
68 {
69  GeqoPrivateData private;
70  int generation;
71  Chromosome *momma;
72  Chromosome *daddy;
73  Chromosome *kid;
74  Pool *pool;
75  int pool_size,
76  number_generations;
77 
78 #ifdef GEQO_DEBUG
79  int status_interval;
80 #endif
81  Gene *best_tour;
82  RelOptInfo *best_rel;
83 
84 #if defined(ERX)
85  Edge *edge_table; /* list of edges */
86  int edge_failures = 0;
87 #endif
88 #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
89  City *city_table; /* list of cities */
90 #endif
91 #if defined(CX)
92  int cycle_diffs = 0;
93  int mutations = 0;
94 #endif
95 
96 /* set up private information */
97  root->join_search_private = (void *) &private;
98  private.initial_rels = initial_rels;
99 
100 /* initialize private number generator */
101  geqo_set_seed(root, Geqo_seed);
102 
103 /* set GA parameters */
104  pool_size = gimme_pool_size(number_of_rels);
105  number_generations = gimme_number_generations(pool_size);
106 #ifdef GEQO_DEBUG
107  status_interval = 10;
108 #endif
109 
110 /* allocate genetic pool memory */
111  pool = alloc_pool(root, pool_size, number_of_rels);
112 
113 /* random initialization of the pool */
114  random_init_pool(root, pool);
115 
116 /* sort the pool according to cheapest path as fitness */
117  sort_pool(root, pool); /* we have to do it only one time, since all
118  * kids replace the worst individuals in
119  * future (-> geqo_pool.c:spread_chromo ) */
120 
121 #ifdef GEQO_DEBUG
122  elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
123  pool_size,
124  pool->data[0].worth,
125  pool->data[pool_size - 1].worth);
126 #endif
127 
128 /* allocate chromosome momma and daddy memory */
129  momma = alloc_chromo(root, pool->string_length);
130  daddy = alloc_chromo(root, pool->string_length);
131 
132 #if defined (ERX)
133 #ifdef GEQO_DEBUG
134  elog(DEBUG2, "using edge recombination crossover [ERX]");
135 #endif
136 /* allocate edge table memory */
137  edge_table = alloc_edge_table(root, pool->string_length);
138 #elif defined(PMX)
139 #ifdef GEQO_DEBUG
140  elog(DEBUG2, "using partially matched crossover [PMX]");
141 #endif
142 /* allocate chromosome kid memory */
143  kid = alloc_chromo(root, pool->string_length);
144 #elif defined(CX)
145 #ifdef GEQO_DEBUG
146  elog(DEBUG2, "using cycle crossover [CX]");
147 #endif
148 /* allocate city table memory */
149  kid = alloc_chromo(root, pool->string_length);
150  city_table = alloc_city_table(root, pool->string_length);
151 #elif defined(PX)
152 #ifdef GEQO_DEBUG
153  elog(DEBUG2, "using position crossover [PX]");
154 #endif
155 /* allocate city table memory */
156  kid = alloc_chromo(root, pool->string_length);
157  city_table = alloc_city_table(root, pool->string_length);
158 #elif defined(OX1)
159 #ifdef GEQO_DEBUG
160  elog(DEBUG2, "using order crossover [OX1]");
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(OX2)
166 #ifdef GEQO_DEBUG
167  elog(DEBUG2, "using order crossover [OX2]");
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 #endif
173 
174 
175 /* my pain main part: */
176 /* iterative optimization */
177 
178  for (generation = 0; generation < number_generations; generation++)
179  {
180  /* SELECTION: using linear bias function */
181  geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
182 
183 #if defined (ERX)
184  /* EDGE RECOMBINATION CROSSOVER */
185  gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
186 
187  kid = momma;
188 
189  /* are there any edge failures ? */
190  edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
191 #elif defined(PMX)
192  /* PARTIALLY MATCHED CROSSOVER */
193  pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
194 #elif defined(CX)
195  /* CYCLE CROSSOVER */
196  cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
197  /* mutate the child */
198  if (cycle_diffs == 0)
199  {
200  mutations++;
201  geqo_mutation(root, kid->string, pool->string_length);
202  }
203 #elif defined(PX)
204  /* POSITION CROSSOVER */
205  px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
206 #elif defined(OX1)
207  /* ORDER CROSSOVER */
208  ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
209 #elif defined(OX2)
210  /* ORDER CROSSOVER */
211  ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
212 #endif
213 
214 
215  /* EVALUATE FITNESS */
216  kid->worth = geqo_eval(root, kid->string, pool->string_length);
217 
218  /* push the kid into the wilderness of life according to its worth */
219  spread_chromo(root, kid, pool);
220 
221 
222 #ifdef GEQO_DEBUG
223  if (status_interval && !(generation % status_interval))
224  print_gen(stdout, pool, generation);
225 #endif
226 
227  }
228 
229 
230 #if defined(ERX) && defined(GEQO_DEBUG)
231  if (edge_failures != 0)
232  elog(LOG, "[GEQO] failures: %d, average: %d",
233  edge_failures, (int) number_generations / edge_failures);
234  else
235  elog(LOG, "[GEQO] no edge failures detected");
236 #endif
237 
238 #if defined(CX) && defined(GEQO_DEBUG)
239  if (mutations != 0)
240  elog(LOG, "[GEQO] mutations: %d, generations: %d",
241  mutations, number_generations);
242  else
243  elog(LOG, "[GEQO] no mutations processed");
244 #endif
245 
246 #ifdef GEQO_DEBUG
247  print_pool(stdout, pool, 0, pool_size - 1);
248 #endif
249 
250 #ifdef GEQO_DEBUG
251  elog(DEBUG1, "GEQO best is %.2f after %d generations",
252  pool->data[0].worth, number_generations);
253 #endif
254 
255 
256  /*
257  * got the cheapest query tree processed by geqo; first element of the
258  * population indicates the best query tree
259  */
260  best_tour = (Gene *) pool->data[0].string;
261 
262  best_rel = gimme_tree(root, best_tour, pool->string_length);
263 
264  if (best_rel == NULL)
265  elog(ERROR, "geqo failed to make a valid plan");
266 
267  /* DBG: show the query plan */
268 #ifdef NOT_USED
269  print_plan(best_plan, root);
270 #endif
271 
272  /* ... free memory stuff */
273  free_chromo(root, momma);
274  free_chromo(root, daddy);
275 
276 #if defined (ERX)
277  free_edge_table(root, edge_table);
278 #elif defined(PMX)
279  free_chromo(root, kid);
280 #elif defined(CX)
281  free_chromo(root, kid);
282  free_city_table(root, city_table);
283 #elif defined(PX)
284  free_chromo(root, kid);
285  free_city_table(root, city_table);
286 #elif defined(OX1)
287  free_chromo(root, kid);
288  free_city_table(root, city_table);
289 #elif defined(OX2)
290  free_chromo(root, kid);
291  free_city_table(root, city_table);
292 #endif
293 
294  free_pool(root, pool);
295 
296  /* ... clear root pointer to our private storage */
297  root->join_search_private = NULL;
298 
299  return best_rel;
300 }
301 
302 
303 /*
304  * Return either configured pool size or a good default
305  *
306  * The default is based on query size (no. of relations) = 2^(QS+1),
307  * but constrained to a range based on the effort value.
308  */
309 static int
310 gimme_pool_size(int nr_rel)
311 {
312  double size;
313  int minsize;
314  int maxsize;
315 
316  /* Legal pool size *must* be at least 2, so ignore attempt to select 1 */
317  if (Geqo_pool_size >= 2)
318  return Geqo_pool_size;
319 
320  size = pow(2.0, nr_rel + 1.0);
321 
322  maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
323  if (size > maxsize)
324  return maxsize;
325 
326  minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
327  if (size < minsize)
328  return minsize;
329 
330  return (int) ceil(size);
331 }
332 
333 
334 /*
335  * Return either configured number of generations or a good default
336  *
337  * The default is the same as the pool size, which allows us to be
338  * sure that less-fit individuals get pushed out of the breeding
339  * population before the run finishes.
340  */
341 static int
343 {
344  if (Geqo_generations > 0)
345  return Geqo_generations;
346 
347  return pool_size;
348 }
void free_chromo(PlannerInfo *root, Chromosome *chromo)
Definition: geqo_pool.c:176
double Geqo_selection_bias
Definition: geqo_main.c:42
#define DEBUG1
Definition: elog.h:25
Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:57
int cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
Definition: geqo_cx.c:47
Cost worth
Definition: geqo_gene.h:35
int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
Definition: geqo_erx.c:193
void * join_search_private
Definition: relation.h:315
void ox1(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
Definition: geqo_ox1.c:46
float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
Definition: geqo_erx.c:92
static int gimme_pool_size(int nr_rel)
Definition: geqo_main.c:310
RelOptInfo * gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:163
int Gene
Definition: geqo_gene.h:30
void pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
Definition: geqo_pmx.c:46
void random_init_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:91
void spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
Definition: geqo_pool.c:187
#define LOG
Definition: elog.h:26
Chromosome * alloc_chromo(PlannerInfo *root, int string_length)
Definition: geqo_pool.c:162
int string_length
Definition: geqo_gene.h:42
#define ERROR
Definition: elog.h:43
void sort_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:135
#define DEBUG2
Definition: elog.h:24
int Geqo_pool_size
Definition: geqo_main.c:40
static int gimme_number_generations(int pool_size)
Definition: geqo_main.c:342
void free_edge_table(PlannerInfo *root, Edge *edge_table)
Definition: geqo_erx.c:73
void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
Definition: geqo_px.c:46
void ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
Definition: geqo_ox2.c:46
Pool * alloc_pool(PlannerInfo *root, int pool_size, int string_length)
Definition: geqo_pool.c:42
Definition: geqo_gene.h:38
RelOptInfo * geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
Definition: geqo_main.c:67
void geqo_set_seed(PlannerInfo *root, double seed)
Definition: geqo_random.c:20
int Geqo_generations
Definition: geqo_main.c:41
#define NULL
Definition: c.h:229
Chromosome * data
Definition: geqo_gene.h:40
Edge * alloc_edge_table(PlannerInfo *root, int num_gene)
Definition: geqo_erx.c:53
void free_city_table(PlannerInfo *root, City *city_table)
void free_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:69
double Geqo_seed
Definition: geqo_main.c:43
Gene * string
Definition: geqo_gene.h:34
City * alloc_city_table(PlannerInfo *root, int num_gene)
int Geqo_effort
Definition: geqo_main.c:39
#define elog
Definition: elog.h:219
void geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_mutation.c:39
Definition: pg_list.h:45
void geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)