PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_pool.c File Reference
#include "postgres.h"
#include <float.h>
#include <limits.h>
#include <math.h>
#include "optimizer/geqo_copy.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_recombination.h"
Include dependency graph for geqo_pool.c:

Go to the source code of this file.

Functions

static int compare (const void *arg1, const void *arg2)
 
Poolalloc_pool (PlannerInfo *root, int pool_size, int string_length)
 
void free_pool (PlannerInfo *root, Pool *pool)
 
void random_init_pool (PlannerInfo *root, Pool *pool)
 
void sort_pool (PlannerInfo *root, Pool *pool)
 
Chromosomealloc_chromo (PlannerInfo *root, int string_length)
 
void free_chromo (PlannerInfo *root, Chromosome *chromo)
 
void spread_chromo (PlannerInfo *root, Chromosome *chromo, Pool *pool)
 

Function Documentation

Chromosome* alloc_chromo ( PlannerInfo root,
int  string_length 
)

Definition at line 162 of file geqo_pool.c.

References palloc(), and Chromosome::string.

Referenced by geqo().

163 {
164  Chromosome *chromo;
165 
166  chromo = (Chromosome *) palloc(sizeof(Chromosome));
167  chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
168 
169  return chromo;
170 }
int Gene
Definition: geqo_gene.h:30
void * palloc(Size size)
Definition: mcxt.c:849
Gene * string
Definition: geqo_gene.h:34
Pool* alloc_pool ( PlannerInfo root,
int  pool_size,
int  string_length 
)

Definition at line 42 of file geqo_pool.c.

References Pool::data, i, palloc(), Pool::size, and Pool::string_length.

Referenced by geqo().

43 {
44  Pool *new_pool;
45  Chromosome *chromo;
46  int i;
47 
48  /* pool */
49  new_pool = (Pool *) palloc(sizeof(Pool));
50  new_pool->size = (int) pool_size;
51  new_pool->string_length = (int) string_length;
52 
53  /* all chromosome */
54  new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
55 
56  /* all gene */
57  chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
58  for (i = 0; i < pool_size; i++)
59  chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
60 
61  return new_pool;
62 }
int Gene
Definition: geqo_gene.h:30
int size
Definition: geqo_gene.h:41
int string_length
Definition: geqo_gene.h:42
Definition: geqo_gene.h:38
Chromosome * data
Definition: geqo_gene.h:40
void * palloc(Size size)
Definition: mcxt.c:849
int i
static int compare ( const void *  arg1,
const void *  arg2 
)
static

Definition at line 145 of file geqo_pool.c.

References Chromosome::worth.

Referenced by _bt_compare_array_elements(), _bt_load(), _bt_sort_array_elements(), ApplySortAbbrevFullComparator(), ApplySortComparator(), binaryheap_allocate(), compare_scalars(), comparetup_cluster(), comparetup_datum(), comparetup_heap(), comparetup_index_btree(), heap_compare_slots(), multi_sort_compare(), pairingheap_allocate(), and sort_pool().

146 {
147  const Chromosome *chromo1 = (const Chromosome *) arg1;
148  const Chromosome *chromo2 = (const Chromosome *) arg2;
149 
150  if (chromo1->worth == chromo2->worth)
151  return 0;
152  else if (chromo1->worth > chromo2->worth)
153  return 1;
154  else
155  return -1;
156 }
Cost worth
Definition: geqo_gene.h:35
void free_chromo ( PlannerInfo root,
Chromosome chromo 
)

Definition at line 176 of file geqo_pool.c.

References pfree(), and Chromosome::string.

Referenced by geqo().

177 {
178  pfree(chromo->string);
179  pfree(chromo);
180 }
void pfree(void *pointer)
Definition: mcxt.c:950
Gene * string
Definition: geqo_gene.h:34
void free_pool ( PlannerInfo root,
Pool pool 
)

Definition at line 69 of file geqo_pool.c.

References Pool::data, i, pfree(), and Pool::size.

Referenced by geqo().

70 {
71  Chromosome *chromo;
72  int i;
73 
74  /* all gene */
75  chromo = (Chromosome *) pool->data; /* vector of all chromos */
76  for (i = 0; i < pool->size; i++)
77  pfree(chromo[i].string);
78 
79  /* all chromosome */
80  pfree(pool->data);
81 
82  /* pool */
83  pfree(pool);
84 }
int size
Definition: geqo_gene.h:41
void pfree(void *pointer)
Definition: mcxt.c:950
Chromosome * data
Definition: geqo_gene.h:40
int i
void random_init_pool ( PlannerInfo root,
Pool pool 
)

Definition at line 91 of file geqo_pool.c.

References Pool::data, DEBUG1, elog, ERROR, geqo_eval(), i, init_tour(), Pool::size, Pool::string_length, and Chromosome::worth.

Referenced by geqo().

92 {
93  Chromosome *chromo = (Chromosome *) pool->data;
94  int i;
95  int bad = 0;
96 
97  /*
98  * We immediately discard any invalid individuals (those that geqo_eval
99  * returns DBL_MAX for), thereby not wasting pool space on them.
100  *
101  * If we fail to make any valid individuals after 10000 tries, give up;
102  * this probably means something is broken, and we shouldn't just let
103  * ourselves get stuck in an infinite loop.
104  */
105  i = 0;
106  while (i < pool->size)
107  {
108  init_tour(root, chromo[i].string, pool->string_length);
109  pool->data[i].worth = geqo_eval(root, chromo[i].string,
110  pool->string_length);
111  if (pool->data[i].worth < DBL_MAX)
112  i++;
113  else
114  {
115  bad++;
116  if (i == 0 && bad >= 10000)
117  elog(ERROR, "geqo failed to make a valid plan");
118  }
119  }
120 
121 #ifdef GEQO_DEBUG
122  if (bad > 0)
123  elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
124  bad, pool->size);
125 #endif
126 }
#define DEBUG1
Definition: elog.h:25
Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:57
void init_tour(PlannerInfo *root, Gene *tour, int num_gene)
Cost worth
Definition: geqo_gene.h:35
int size
Definition: geqo_gene.h:41
int string_length
Definition: geqo_gene.h:42
#define ERROR
Definition: elog.h:43
Chromosome * data
Definition: geqo_gene.h:40
int i
#define elog
Definition: elog.h:219
void sort_pool ( PlannerInfo root,
Pool pool 
)

Definition at line 135 of file geqo_pool.c.

References compare(), Pool::data, qsort, and Pool::size.

Referenced by geqo().

136 {
137  qsort(pool->data, pool->size, sizeof(Chromosome), compare);
138 }
int size
Definition: geqo_gene.h:41
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
Chromosome * data
Definition: geqo_gene.h:40
#define qsort(a, b, c, d)
Definition: port.h:443
void spread_chromo ( PlannerInfo root,
Chromosome chromo,
Pool pool 
)

Definition at line 187 of file geqo_pool.c.

References Pool::data, geqo_copy(), i, Pool::size, Chromosome::string, Pool::string_length, and Chromosome::worth.

Referenced by geqo().

188 {
189  int top,
190  mid,
191  bot;
192  int i,
193  index;
194  Chromosome swap_chromo,
195  tmp_chromo;
196 
197  /* new chromo is so bad we can't use it */
198  if (chromo->worth > pool->data[pool->size - 1].worth)
199  return;
200 
201  /* do a binary search to find the index of the new chromo */
202 
203  top = 0;
204  mid = pool->size / 2;
205  bot = pool->size - 1;
206  index = -1;
207 
208  while (index == -1)
209  {
210  /* these 4 cases find a new location */
211 
212  if (chromo->worth <= pool->data[top].worth)
213  index = top;
214  else if (chromo->worth == pool->data[mid].worth)
215  index = mid;
216  else if (chromo->worth == pool->data[bot].worth)
217  index = bot;
218  else if (bot - top <= 1)
219  index = bot;
220 
221 
222  /*
223  * these 2 cases move the search indices since a new location has not
224  * yet been found.
225  */
226 
227  else if (chromo->worth < pool->data[mid].worth)
228  {
229  bot = mid;
230  mid = top + ((bot - top) / 2);
231  }
232  else
233  { /* (chromo->worth > pool->data[mid].worth) */
234  top = mid;
235  mid = top + ((bot - top) / 2);
236  }
237  } /* ... while */
238 
239  /* now we have index for chromo */
240 
241  /*
242  * move every gene from index on down one position to make room for chromo
243  */
244 
245  /*
246  * copy new gene into pool storage; always replace worst gene in pool
247  */
248 
249  geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
250 
251  swap_chromo.string = pool->data[pool->size - 1].string;
252  swap_chromo.worth = pool->data[pool->size - 1].worth;
253 
254  for (i = index; i < pool->size; i++)
255  {
256  tmp_chromo.string = pool->data[i].string;
257  tmp_chromo.worth = pool->data[i].worth;
258 
259  pool->data[i].string = swap_chromo.string;
260  pool->data[i].worth = swap_chromo.worth;
261 
262  swap_chromo.string = tmp_chromo.string;
263  swap_chromo.worth = tmp_chromo.worth;
264  }
265 }
Cost worth
Definition: geqo_gene.h:35
int size
Definition: geqo_gene.h:41
Definition: type.h:89
int string_length
Definition: geqo_gene.h:42
void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length)
Definition: geqo_copy.c:45
Chromosome * data
Definition: geqo_gene.h:40
int i
Gene * string
Definition: geqo_gene.h:34