PostgreSQL Source Code  git master
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 67 of file geqo_main.c.

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)
231 #if defined(GEQO_DEBUG)
232  if (edge_failures != 0)
233  elog(LOG, "[GEQO] failures: %d, average: %d",
234  edge_failures, (int) number_generations / edge_failures);
235  else
236  elog(LOG, "[GEQO] no edge failures detected");
237 #else
238  /* suppress variable-set-but-not-used warnings from some compilers */
239  (void) edge_failures;
240 #endif
241 #endif
242 
243 #if defined(CX) && defined(GEQO_DEBUG)
244  if (mutations != 0)
245  elog(LOG, "[GEQO] mutations: %d, generations: %d",
246  mutations, number_generations);
247  else
248  elog(LOG, "[GEQO] no mutations processed");
249 #endif
250 
251 #ifdef GEQO_DEBUG
252  print_pool(stdout, pool, 0, pool_size - 1);
253 #endif
254 
255 #ifdef GEQO_DEBUG
256  elog(DEBUG1, "GEQO best is %.2f after %d generations",
257  pool->data[0].worth, number_generations);
258 #endif
259 
260 
261  /*
262  * got the cheapest query tree processed by geqo; first element of the
263  * population indicates the best query tree
264  */
265  best_tour = (Gene *) pool->data[0].string;
266 
267  best_rel = gimme_tree(root, best_tour, pool->string_length);
268 
269  if (best_rel == NULL)
270  elog(ERROR, "geqo failed to make a valid plan");
271 
272  /* DBG: show the query plan */
273 #ifdef NOT_USED
274  print_plan(best_plan, root);
275 #endif
276 
277  /* ... free memory stuff */
278  free_chromo(root, momma);
279  free_chromo(root, daddy);
280 
281 #if defined (ERX)
282  free_edge_table(root, edge_table);
283 #elif defined(PMX)
284  free_chromo(root, kid);
285 #elif defined(CX)
286  free_chromo(root, kid);
287  free_city_table(root, city_table);
288 #elif defined(PX)
289  free_chromo(root, kid);
290  free_city_table(root, city_table);
291 #elif defined(OX1)
292  free_chromo(root, kid);
293  free_city_table(root, city_table);
294 #elif defined(OX2)
295  free_chromo(root, kid);
296  free_city_table(root, city_table);
297 #endif
298 
299  free_pool(root, pool);
300 
301  /* ... clear root pointer to our private storage */
302  root->join_search_private = NULL;
303 
304  return best_rel;
305 }
#define LOG
Definition: elog.h:31
#define DEBUG2
Definition: elog.h:29
#define DEBUG1
Definition: elog.h:30
#define ERROR
Definition: elog.h:39
float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
Definition: geqo_erx.c:93
void free_edge_table(PlannerInfo *root, Edge *edge_table)
Definition: geqo_erx.c:74
int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
Definition: geqo_erx.c:194
Edge * alloc_edge_table(PlannerInfo *root, int num_gene)
Definition: geqo_erx.c:54
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:43
static int gimme_number_generations(int pool_size)
Definition: geqo_main.c:347
static int gimme_pool_size(int nr_rel)
Definition: geqo_main.c:315
double Geqo_selection_bias
Definition: geqo_main.c:42
void geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
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
Chromosome * alloc_chromo(PlannerInfo *root, int string_length)
Definition: geqo_pool.c:162
void spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
Definition: geqo_pool.c:187
Pool * alloc_pool(PlannerInfo *root, int pool_size, int string_length)
Definition: geqo_pool.c:42
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)
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)
City * alloc_city_table(PlannerInfo *root, int num_gene)
void geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
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(), 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  */
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 }
Assert(fmt[strlen(fmt) - 1] !='\n')
List * list_truncate(List *list, int new_size)
Definition: list.c:630
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:403
#define AllocSetContextCreate
Definition: memutils.h:126
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:150
double Cost
Definition: nodes.h:262
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
static int list_length(const List *l)
Definition: pg_list.h:152
Definition: dynahash.c:220
Cost total_cost
Definition: pathnodes.h:1630
List * join_rel_list
Definition: pathnodes.h:277
struct Path * cheapest_total_path
Definition: pathnodes.h:887

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), RelOptInfo::cheapest_total_path, CurrentMemoryContext, gimme_tree(), PlannerInfo::join_rel_list, list_length(), list_truncate(), MemoryContextDelete(), MemoryContextSwitchTo(), 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
void * palloc(Size size)
Definition: mcxt.c:1226
#define lfirst(lc)
Definition: pg_list.h:172
#define NIL
Definition: pg_list.h:68
#define linitial(l)
Definition: pg_list.h:178
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
int size
Definition: geqo_eval.c:39
RelOptInfo * joinrel
Definition: geqo_eval.c:38
Definition: pg_list.h:54

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

Referenced by geqo(), and geqo_eval().

Variable Documentation

◆ Geqo_effort

PGDLLIMPORT int Geqo_effort
extern

Definition at line 39 of file geqo_main.c.

Referenced by gimme_pool_size().

◆ Geqo_generations

PGDLLIMPORT int Geqo_generations
extern

Definition at line 41 of file geqo_main.c.

Referenced by gimme_number_generations().

◆ Geqo_pool_size

PGDLLIMPORT int Geqo_pool_size
extern

Definition at line 40 of file geqo_main.c.

Referenced by gimme_pool_size().

◆ Geqo_seed

PGDLLIMPORT double Geqo_seed
extern

Definition at line 43 of file geqo_main.c.

Referenced by geqo().

◆ Geqo_selection_bias

PGDLLIMPORT double Geqo_selection_bias
extern

Definition at line 42 of file geqo_main.c.

Referenced by geqo().