PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
geqo.h File Reference
#include "common/pg_prng.h"
#include "nodes/pathnodes.h"
#include "optimizer/geqo_gene.h"
Include dependency graph for geqo.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  GeqoPrivateData
 

Macros

#define ERX
 
#define DEFAULT_GEQO_EFFORT   5
 
#define MIN_GEQO_EFFORT   1
 
#define MAX_GEQO_EFFORT   10
 
#define DEFAULT_GEQO_SELECTION_BIAS   2.0
 
#define MIN_GEQO_SELECTION_BIAS   1.5
 
#define MAX_GEQO_SELECTION_BIAS   2.0
 

Functions

RelOptInfogeqo (PlannerInfo *root, int number_of_rels, List *initial_rels)
 
Cost geqo_eval (PlannerInfo *root, Gene *tour, int num_gene)
 
RelOptInfogimme_tree (PlannerInfo *root, Gene *tour, int num_gene)
 

Variables

PGDLLIMPORT int Geqo_effort
 
PGDLLIMPORT int Geqo_pool_size
 
PGDLLIMPORT int Geqo_generations
 
PGDLLIMPORT double Geqo_selection_bias
 
PGDLLIMPORT double Geqo_seed
 

Macro Definition Documentation

◆ DEFAULT_GEQO_EFFORT

#define DEFAULT_GEQO_EFFORT   5

Definition at line 55 of file geqo.h.

◆ DEFAULT_GEQO_SELECTION_BIAS

#define DEFAULT_GEQO_SELECTION_BIAS   2.0

Definition at line 65 of file geqo.h.

◆ ERX

#define ERX

Definition at line 44 of file geqo.h.

◆ MAX_GEQO_EFFORT

#define MAX_GEQO_EFFORT   10

Definition at line 57 of file geqo.h.

◆ MAX_GEQO_SELECTION_BIAS

#define MAX_GEQO_SELECTION_BIAS   2.0

Definition at line 67 of file geqo.h.

◆ MIN_GEQO_EFFORT

#define MIN_GEQO_EFFORT   1

Definition at line 56 of file geqo.h.

◆ MIN_GEQO_SELECTION_BIAS

#define MIN_GEQO_SELECTION_BIAS   1.5

Definition at line 66 of file geqo.h.

Function Documentation

◆ geqo()

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

Definition at line 72 of file geqo_main.c.

73{
74 GeqoPrivateData private;
75 int generation;
76 Chromosome *momma;
77 Chromosome *daddy;
78 Chromosome *kid;
79 Pool *pool;
80 int pool_size,
81 number_generations;
82
83#ifdef GEQO_DEBUG
84 int status_interval;
85#endif
86 Gene *best_tour;
87 RelOptInfo *best_rel;
88
89#if defined(ERX)
90 Edge *edge_table; /* list of edges */
91 int edge_failures = 0;
92#endif
93#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
94 City *city_table; /* list of cities */
95#endif
96#if defined(CX)
97 int cycle_diffs = 0;
98 int mutations = 0;
99#endif
100
101/* set up private information */
102 root->join_search_private = &private;
103 private.initial_rels = initial_rels;
104
105/* initialize private number generator */
107
108/* set GA parameters */
109 pool_size = gimme_pool_size(number_of_rels);
110 number_generations = gimme_number_generations(pool_size);
111#ifdef GEQO_DEBUG
112 status_interval = 10;
113#endif
114
115/* allocate genetic pool memory */
116 pool = alloc_pool(root, pool_size, number_of_rels);
117
118/* random initialization of the pool */
119 random_init_pool(root, pool);
120
121/* sort the pool according to cheapest path as fitness */
122 sort_pool(root, pool); /* we have to do it only one time, since all
123 * kids replace the worst individuals in
124 * future (-> geqo_pool.c:spread_chromo ) */
125
126#ifdef GEQO_DEBUG
127 elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
128 pool_size,
129 pool->data[0].worth,
130 pool->data[pool_size - 1].worth);
131#endif
132
133/* allocate chromosome momma and daddy memory */
134 momma = alloc_chromo(root, pool->string_length);
135 daddy = alloc_chromo(root, pool->string_length);
136
137#if defined (ERX)
138#ifdef GEQO_DEBUG
139 elog(DEBUG2, "using edge recombination crossover [ERX]");
140#endif
141/* allocate edge table memory */
142 edge_table = alloc_edge_table(root, pool->string_length);
143#elif defined(PMX)
144#ifdef GEQO_DEBUG
145 elog(DEBUG2, "using partially matched crossover [PMX]");
146#endif
147/* allocate chromosome kid memory */
148 kid = alloc_chromo(root, pool->string_length);
149#elif defined(CX)
150#ifdef GEQO_DEBUG
151 elog(DEBUG2, "using cycle crossover [CX]");
152#endif
153/* allocate city table memory */
154 kid = alloc_chromo(root, pool->string_length);
155 city_table = alloc_city_table(root, pool->string_length);
156#elif defined(PX)
157#ifdef GEQO_DEBUG
158 elog(DEBUG2, "using position crossover [PX]");
159#endif
160/* allocate city table memory */
161 kid = alloc_chromo(root, pool->string_length);
162 city_table = alloc_city_table(root, pool->string_length);
163#elif defined(OX1)
164#ifdef GEQO_DEBUG
165 elog(DEBUG2, "using order crossover [OX1]");
166#endif
167/* allocate city table memory */
168 kid = alloc_chromo(root, pool->string_length);
169 city_table = alloc_city_table(root, pool->string_length);
170#elif defined(OX2)
171#ifdef GEQO_DEBUG
172 elog(DEBUG2, "using order crossover [OX2]");
173#endif
174/* allocate city table memory */
175 kid = alloc_chromo(root, pool->string_length);
176 city_table = alloc_city_table(root, pool->string_length);
177#endif
178
179
180/* my pain main part: */
181/* iterative optimization */
182
183 for (generation = 0; generation < number_generations; generation++)
184 {
185 /* SELECTION: using linear bias function */
186 geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
187
188#if defined (ERX)
189 /* EDGE RECOMBINATION CROSSOVER */
190 gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
191
192 kid = momma;
193
194 /* are there any edge failures ? */
195 edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
196#elif defined(PMX)
197 /* PARTIALLY MATCHED CROSSOVER */
198 pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
199#elif defined(CX)
200 /* CYCLE CROSSOVER */
201 cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
202 /* mutate the child */
203 if (cycle_diffs == 0)
204 {
205 mutations++;
207 }
208#elif defined(PX)
209 /* POSITION CROSSOVER */
210 px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
211#elif defined(OX1)
212 /* ORDER CROSSOVER */
213 ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
214#elif defined(OX2)
215 /* ORDER CROSSOVER */
216 ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
217#endif
218
219
220 /* EVALUATE FITNESS */
221 kid->worth = geqo_eval(root, kid->string, pool->string_length);
222
223 /* push the kid into the wilderness of life according to its worth */
224 spread_chromo(root, kid, pool);
225
226
227#ifdef GEQO_DEBUG
228 if (status_interval && !(generation % status_interval))
229 print_gen(stdout, pool, generation);
230#endif
231
232 }
233
234
235#if defined(ERX)
236#if defined(GEQO_DEBUG)
237 if (edge_failures != 0)
238 elog(LOG, "[GEQO] failures: %d, average: %d",
239 edge_failures, (int) number_generations / edge_failures);
240 else
241 elog(LOG, "[GEQO] no edge failures detected");
242#else
243 /* suppress variable-set-but-not-used warnings from some compilers */
244 (void) edge_failures;
245#endif
246#endif
247
248#if defined(CX) && defined(GEQO_DEBUG)
249 if (mutations != 0)
250 elog(LOG, "[GEQO] mutations: %d, generations: %d",
251 mutations, number_generations);
252 else
253 elog(LOG, "[GEQO] no mutations processed");
254#endif
255
256#ifdef GEQO_DEBUG
257 print_pool(stdout, pool, 0, pool_size - 1);
258#endif
259
260#ifdef GEQO_DEBUG
261 elog(DEBUG1, "GEQO best is %.2f after %d generations",
262 pool->data[0].worth, number_generations);
263#endif
264
265
266 /*
267 * got the cheapest query tree processed by geqo; first element of the
268 * population indicates the best query tree
269 */
270 best_tour = (Gene *) pool->data[0].string;
271
272 best_rel = gimme_tree(root, best_tour, pool->string_length);
273
274 if (best_rel == NULL)
275 elog(ERROR, "geqo failed to make a valid plan");
276
277 /* DBG: show the query plan */
278#ifdef NOT_USED
279 print_plan(best_plan, root);
280#endif
281
282 /* ... free memory stuff */
283 free_chromo(root, momma);
284 free_chromo(root, daddy);
285
286#if defined (ERX)
287 free_edge_table(root, edge_table);
288#elif defined(PMX)
289 free_chromo(root, kid);
290#elif defined(CX)
291 free_chromo(root, kid);
292 free_city_table(root, city_table);
293#elif defined(PX)
294 free_chromo(root, kid);
295 free_city_table(root, city_table);
296#elif defined(OX1)
297 free_chromo(root, kid);
298 free_city_table(root, city_table);
299#elif defined(OX2)
300 free_chromo(root, kid);
301 free_city_table(root, city_table);
302#endif
303
304 free_pool(root, pool);
305
306 /* ... clear root pointer to our private storage */
307 root->join_search_private = NULL;
308
309 return best_rel;
310}
#define LOG
Definition: elog.h:31
#define DEBUG2
Definition: elog.h:29
#define DEBUG1
Definition: elog.h:30
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
Edge * alloc_edge_table(PlannerInfo *root, int num_gene)
Definition: geqo_erx.c:56
float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
Definition: geqo_erx.c:95
void free_edge_table(PlannerInfo *root, Edge *edge_table)
Definition: geqo_erx.c:76
int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
Definition: geqo_erx.c:196
Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:57
RelOptInfo * gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:163
int Gene
Definition: geqo_gene.h:30
double Geqo_seed
Definition: geqo_main.c:48
static int gimme_number_generations(int pool_size)
Definition: geqo_main.c:352
static int gimme_pool_size(int nr_rel)
Definition: geqo_main.c:320
double Geqo_selection_bias
Definition: geqo_main.c:47
void geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
Pool * alloc_pool(PlannerInfo *root, int pool_size, int string_length)
Definition: geqo_pool.c:42
void sort_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:135
void free_chromo(PlannerInfo *root, Chromosome *chromo)
Definition: geqo_pool.c:176
void free_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:69
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
Chromosome * alloc_chromo(PlannerInfo *root, int string_length)
Definition: geqo_pool.c:162
void geqo_set_seed(PlannerInfo *root, double seed)
Definition: geqo_random.c:20
void free_city_table(PlannerInfo *root, City *city_table)
void pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
City * alloc_city_table(PlannerInfo *root, int num_gene)
void ox1(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
int cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
void geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
tree ctl root
Definition: radixtree.h:1857
Cost worth
Definition: geqo_gene.h:35
Gene * string
Definition: geqo_gene.h:34
Definition: geqo_gene.h:39
int string_length
Definition: geqo_gene.h:42
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_seed, geqo_selection(), Geqo_selection_bias, geqo_set_seed(), gimme_edge_table(), gimme_number_generations(), gimme_pool_size(), gimme_tour(), gimme_tree(), LOG, ox1(), ox2(), pmx(), px(), random_init_pool(), root, sort_pool(), spread_chromo(), generate_unaccent_rules::stdout, Chromosome::string, Pool::string_length, and Chromosome::worth.

Referenced by make_rel_from_joinlist().

◆ geqo_eval()

Cost geqo_eval ( PlannerInfo root,
Gene tour,
int  num_gene 
)

Definition at line 57 of file geqo_eval.c.

58{
59 MemoryContext mycontext;
60 MemoryContext oldcxt;
61 RelOptInfo *joinrel;
62 Cost fitness;
63 int savelength;
64 struct HTAB *savehash;
65
66 /*
67 * Create a private memory context that will hold all temp storage
68 * allocated inside gimme_tree().
69 *
70 * Since geqo_eval() will be called many times, we can't afford to let all
71 * that memory go unreclaimed until end of statement. Note we make the
72 * temp context a child of the planner's normal context, so that it will
73 * be freed even if we abort via ereport(ERROR).
74 */
76 "GEQO",
78 oldcxt = MemoryContextSwitchTo(mycontext);
79
80 /*
81 * gimme_tree will add entries to root->join_rel_list, which may or may
82 * not already contain some entries. The newly added entries will be
83 * recycled by the MemoryContextDelete below, so we must ensure that the
84 * list is restored to its former state before exiting. We can do this by
85 * truncating the list to its original length. NOTE this assumes that any
86 * added entries are appended at the end!
87 *
88 * We also must take care not to mess up the outer join_rel_hash, if there
89 * is one. We can do this by just temporarily setting the link to NULL.
90 * (If we are dealing with enough join rels, which we very likely are, a
91 * new hash table will get built and used locally.)
92 *
93 * join_rel_level[] shouldn't be in use, so just Assert it isn't.
94 */
95 savelength = list_length(root->join_rel_list);
96 savehash = root->join_rel_hash;
97 Assert(root->join_rel_level == NULL);
98
99 root->join_rel_hash = NULL;
100
101 /* construct the best path for the given combination of relations */
102 joinrel = gimme_tree(root, tour, num_gene);
103
104 /*
105 * compute fitness, if we found a valid join
106 *
107 * XXX geqo does not currently support optimization for partial result
108 * retrieval, nor do we take any cognizance of possible use of
109 * parameterized paths --- how to fix?
110 */
111 if (joinrel)
112 {
113 Path *best_path = joinrel->cheapest_total_path;
114
115 fitness = best_path->total_cost;
116 }
117 else
118 fitness = DBL_MAX;
119
120 /*
121 * Restore join_rel_list to its former state, and put back original
122 * hashtable if any.
123 */
124 root->join_rel_list = list_truncate(root->join_rel_list,
125 savelength);
126 root->join_rel_hash = savehash;
127
128 /* release all the memory acquired within gimme_tree */
129 MemoryContextSwitchTo(oldcxt);
130 MemoryContextDelete(mycontext);
131
132 return fitness;
133}
#define Assert(condition)
Definition: c.h:812
List * list_truncate(List *list, int new_size)
Definition: list.c:631
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:454
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
double Cost
Definition: nodes.h:251
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
static int list_length(const List *l)
Definition: pg_list.h:152
Definition: dynahash.c:220
Cost total_cost
Definition: pathnodes.h:1674
struct Path * cheapest_total_path
Definition: pathnodes.h:902

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert, RelOptInfo::cheapest_total_path, CurrentMemoryContext, gimme_tree(), list_length(), list_truncate(), MemoryContextDelete(), MemoryContextSwitchTo(), root, and Path::total_cost.

Referenced by geqo(), and random_init_pool().

◆ gimme_tree()

RelOptInfo * gimme_tree ( PlannerInfo root,
Gene tour,
int  num_gene 
)

Definition at line 163 of file geqo_eval.c.

164{
165 GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
166 List *clumps;
167 int rel_count;
168
169 /*
170 * Sometimes, a relation can't yet be joined to others due to heuristics
171 * or actual semantic restrictions. We maintain a list of "clumps" of
172 * successfully joined relations, with larger clumps at the front. Each
173 * new relation from the tour is added to the first clump it can be joined
174 * to; if there is none then it becomes a new clump of its own. When we
175 * enlarge an existing clump we check to see if it can now be merged with
176 * any other clumps. After the tour is all scanned, we forget about the
177 * heuristics and try to forcibly join any remaining clumps. If we are
178 * unable to merge all the clumps into one, fail.
179 */
180 clumps = NIL;
181
182 for (rel_count = 0; rel_count < num_gene; rel_count++)
183 {
184 int cur_rel_index;
185 RelOptInfo *cur_rel;
186 Clump *cur_clump;
187
188 /* Get the next input relation */
189 cur_rel_index = (int) tour[rel_count];
190 cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
191 cur_rel_index - 1);
192
193 /* Make it into a single-rel clump */
194 cur_clump = (Clump *) palloc(sizeof(Clump));
195 cur_clump->joinrel = cur_rel;
196 cur_clump->size = 1;
197
198 /* Merge it into the clumps list, using only desirable joins */
199 clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
200 }
201
202 if (list_length(clumps) > 1)
203 {
204 /* Force-join the remaining clumps in some legal order */
205 List *fclumps;
206 ListCell *lc;
207
208 fclumps = NIL;
209 foreach(lc, clumps)
210 {
211 Clump *clump = (Clump *) lfirst(lc);
212
213 fclumps = merge_clump(root, fclumps, clump, num_gene, true);
214 }
215 clumps = fclumps;
216 }
217
218 /* Did we succeed in forming a single join relation? */
219 if (list_length(clumps) != 1)
220 return NULL;
221
222 return ((Clump *) linitial(clumps))->joinrel;
223}
static List * merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, bool force)
Definition: geqo_eval.c:238
for(;;)
void * palloc(Size size)
Definition: mcxt.c:1317
#define lfirst(lc)
Definition: pg_list.h:172
#define NIL
Definition: pg_list.h:68
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
#define linitial(l)
Definition: pg_list.h:178
int size
Definition: geqo_eval.c:39
RelOptInfo * joinrel
Definition: geqo_eval.c:38
Definition: pg_list.h:54

References for(), Clump::joinrel, lfirst, linitial, list_length(), list_nth(), merge_clump(), NIL, palloc(), root, and Clump::size.

Referenced by geqo(), and geqo_eval().

Variable Documentation

◆ Geqo_effort

PGDLLIMPORT int Geqo_effort
extern

Definition at line 44 of file geqo_main.c.

Referenced by gimme_pool_size().

◆ Geqo_generations

PGDLLIMPORT int Geqo_generations
extern

Definition at line 46 of file geqo_main.c.

Referenced by gimme_number_generations().

◆ Geqo_pool_size

PGDLLIMPORT int Geqo_pool_size
extern

Definition at line 45 of file geqo_main.c.

Referenced by gimme_pool_size().

◆ Geqo_seed

PGDLLIMPORT double Geqo_seed
extern

Definition at line 48 of file geqo_main.c.

Referenced by geqo().

◆ Geqo_selection_bias

PGDLLIMPORT double Geqo_selection_bias
extern

Definition at line 47 of file geqo_main.c.

Referenced by geqo().