PostgreSQL Source Code git master
Functions | Variables
geqo_main.c File Reference
#include "postgres.h"
#include <math.h>
#include "optimizer/geqo.h"
#include "optimizer/geqo_misc.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"
#include "optimizer/geqo_selection.h"
Include dependency graph for geqo_main.c:

Go to the source code of this file.

Functions

static int gimme_pool_size (int nr_rel)
 
static int gimme_number_generations (int pool_size)
 
RelOptInfo * geqo (PlannerInfo *root, int number_of_rels, List *initial_rels)
 

Variables

int Geqo_effort
 
int Geqo_pool_size
 
int Geqo_generations
 
double Geqo_selection_bias
 
double Geqo_seed
 
int Geqo_planner_extension_id = -1
 

Function Documentation

◆ geqo()

RelOptInfo * geqo ( PlannerInfo *  root,
int  number_of_rels,
List *  initial_rels 
)

Definition at line 74 of file geqo_main.c.

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 */
93 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
103 if (Geqo_planner_extension_id < 0)
104 Geqo_planner_extension_id = GetPlannerExtensionId("geqo");
105
106/* set up private information */
107 SetPlannerInfoExtensionState(root, Geqo_planner_extension_id, &private);
108 private.initial_rels = initial_rels;
109
110/* inform core planner that we may replan */
111 root->assumeReplanning = true;
112
113/* initialize private number generator */
114 geqo_set_seed(root, Geqo_seed);
115
116/* set GA parameters */
117 pool_size = gimme_pool_size(number_of_rels);
118 number_generations = gimme_number_generations(pool_size);
119#ifdef GEQO_DEBUG
120 status_interval = 10;
121#endif
122
123/* allocate genetic pool memory */
124 pool = alloc_pool(root, pool_size, number_of_rels);
125
126/* random initialization of the pool */
127 random_init_pool(root, pool);
128
129/* sort the pool according to cheapest path as fitness */
130 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 momma = alloc_chromo(root, pool->string_length);
143 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 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
191 for (generation = 0; generation < number_generations; generation++)
192 {
193 /* SELECTION: using linear bias function */
194 geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
195
196#if defined (ERX)
197 /* EDGE RECOMBINATION CROSSOVER */
198 gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
199
200 kid = momma;
201
202 /* are there any edge failures ? */
203 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 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 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 */
278 best_tour = (Gene *) pool->data[0].string;
279
280 best_rel = gimme_tree(root, best_tour, pool->string_length);
281
282 if (best_rel == NULL)
283 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 */
291 free_chromo(root, momma);
292 free_chromo(root, daddy);
293
294#if defined (ERX)
295 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 free_pool(root, pool);
313
314 /* ... clear root pointer to our private storage */
315 SetPlannerInfoExtensionState(root, Geqo_planner_extension_id, NULL);
316
317 return best_rel;
318}
LOG
#define LOG
Definition: elog.h:31
DEBUG2
#define DEBUG2
Definition: elog.h:29
DEBUG1
#define DEBUG1
Definition: elog.h:30
ERROR
#define ERROR
Definition: elog.h:39
elog
#define elog(elevel,...)
Definition: elog.h:226
SetPlannerInfoExtensionState
void SetPlannerInfoExtensionState(PlannerInfo *root, int extension_id, void *opaque)
Definition: extendplan.c:115
GetPlannerExtensionId
int GetPlannerExtensionId(const char *extension_name)
Definition: extendplan.c:41
alloc_edge_table
Edge * alloc_edge_table(PlannerInfo *root, int num_gene)
Definition: geqo_erx.c:56
gimme_edge_table
float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
Definition: geqo_erx.c:95
free_edge_table
void free_edge_table(PlannerInfo *root, Edge *edge_table)
Definition: geqo_erx.c:76
gimme_tour
int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
Definition: geqo_erx.c:196
geqo_eval
Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:57
gimme_tree
RelOptInfo * gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:163
Gene
int Gene
Definition: geqo_gene.h:30
Geqo_seed
double Geqo_seed
Definition: geqo_main.c:48
Geqo_planner_extension_id
int Geqo_planner_extension_id
Definition: geqo_main.c:51
gimme_number_generations
static int gimme_number_generations(int pool_size)
Definition: geqo_main.c:360
gimme_pool_size
static int gimme_pool_size(int nr_rel)
Definition: geqo_main.c:328
Geqo_selection_bias
double Geqo_selection_bias
Definition: geqo_main.c:47
geqo_mutation
void geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
alloc_pool
Pool * alloc_pool(PlannerInfo *root, int pool_size, int string_length)
Definition: geqo_pool.c:42
sort_pool
void sort_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:135
free_chromo
void free_chromo(PlannerInfo *root, Chromosome *chromo)
Definition: geqo_pool.c:176
free_pool
void free_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:69
random_init_pool
void random_init_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:91
spread_chromo
void spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
Definition: geqo_pool.c:187
alloc_chromo
Chromosome * alloc_chromo(PlannerInfo *root, int string_length)
Definition: geqo_pool.c:162
geqo_set_seed
void geqo_set_seed(PlannerInfo *root, double seed)
Definition: geqo_random.c:19
free_city_table
void free_city_table(PlannerInfo *root, City *city_table)
pmx
void pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
alloc_city_table
City * alloc_city_table(PlannerInfo *root, int num_gene)
ox1
void ox1(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
cx
int cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
ox2
void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
px
void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
geqo_selection
void geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
Definition: geqo_selection.c:54
generate_unaccent_rules.stdout
stdout
Definition: generate_unaccent_rules.py:35
root
tree ctl root
Definition: radixtree.h:1857
Chromosome::worth
Cost worth
Definition: geqo_gene.h:35
Chromosome::string
Gene * string
Definition: geqo_gene.h:34
Pool
Definition: geqo_gene.h:39
Pool::string_length
int string_length
Definition: geqo_gene.h:42
Pool::data
Chromosome * data
Definition: geqo_gene.h:40

References alloc_chromo(), alloc_city_table(), alloc_edge_table(), alloc_pool(), cx(), Pool::data, DEBUG1, DEBUG2, elog, ERROR, free_chromo(), free_city_table(), free_edge_table(), free_pool(), geqo_eval(), geqo_mutation(), Geqo_planner_extension_id, Geqo_seed, geqo_selection(), Geqo_selection_bias, geqo_set_seed(), GetPlannerExtensionId(), gimme_edge_table(), gimme_number_generations(), gimme_pool_size(), gimme_tour(), gimme_tree(), LOG, ox1(), ox2(), pmx(), px(), random_init_pool(), root, SetPlannerInfoExtensionState(), sort_pool(), spread_chromo(), generate_unaccent_rules::stdout, Chromosome::string, Pool::string_length, and Chromosome::worth.

Referenced by make_rel_from_joinlist().

◆ gimme_number_generations()

static int gimme_number_generations ( int  pool_size)
static

Definition at line 360 of file geqo_main.c.

361{
362 if (Geqo_generations > 0)
363 return Geqo_generations;
364
365 return pool_size;
366}
Geqo_generations
int Geqo_generations
Definition: geqo_main.c:46

References Geqo_generations.

Referenced by geqo().

◆ gimme_pool_size()

static int gimme_pool_size ( int  nr_rel)
static

Definition at line 328 of file geqo_main.c.

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 */
335 if (Geqo_pool_size >= 2)
336 return Geqo_pool_size;
337
338 size = pow(2.0, nr_rel + 1.0);
339
340 maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
341 if (size > maxsize)
342 return maxsize;
343
344 minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
345 if (size < minsize)
346 return minsize;
347
348 return (int) ceil(size);
349}
Geqo_pool_size
int Geqo_pool_size
Definition: geqo_main.c:45
Geqo_effort
int Geqo_effort
Definition: geqo_main.c:44

References Geqo_effort, and Geqo_pool_size.

Referenced by geqo().

Variable Documentation

◆ Geqo_effort

int Geqo_effort

Definition at line 44 of file geqo_main.c.

Referenced by gimme_pool_size().

◆ Geqo_generations

int Geqo_generations

Definition at line 46 of file geqo_main.c.

Referenced by gimme_number_generations().

◆ Geqo_planner_extension_id

int Geqo_planner_extension_id = -1

Definition at line 51 of file geqo_main.c.

Referenced by geqo(), and GetGeqoPrivateData().

◆ Geqo_pool_size

int Geqo_pool_size

Definition at line 45 of file geqo_main.c.

Referenced by gimme_pool_size().

◆ Geqo_seed

double Geqo_seed

Definition at line 48 of file geqo_main.c.

Referenced by geqo().

◆ Geqo_selection_bias

double Geqo_selection_bias

Definition at line 47 of file geqo_main.c.

Referenced by geqo().