granicus.if.org Git - postgresql/blob - src/backend/optimizer/geqo/geqo_main.c

   1 /*------------------------------------------------------------------------
   2  *
   3  * geqo_main.c
   4  *        solution of the query optimization problem
   5  *        by means of a Genetic Algorithm (GA)
   6  *
   7  * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * $Id: geqo_main.c,v 1.27 2001/03/22 03:59:33 momjian Exp $
  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 <time.h>
  28 #include <math.h>
  29
  30 #include "optimizer/geqo.h"
  31 #include "optimizer/geqo_misc.h"
  32 #include "optimizer/geqo_pool.h"
  33 #include "optimizer/geqo_selection.h"
  34
  35
  36 /*
  37  * Configuration options
  38  */
  39 int                     Geqo_pool_size;
  40 int                     Geqo_effort;
  41 int                     Geqo_generations;
  42 double          Geqo_selection_bias;
  43 int                     Geqo_random_seed;
  44
  45
  46 static int      gimme_pool_size(int nr_rel);
  47 static int      gimme_number_generations(int pool_size, int effort);
  48
  49
  50 /* define edge recombination crossover [ERX] per default */
  51 #if !defined(ERX) && \
  52         !defined(PMX) && \
  53         !defined(CX)  && \
  54         !defined(PX)  && \
  55         !defined(OX1) && \
  56         !defined(OX2)
  57 #define ERX
  58 #endif
  59
  60
  61 /*
  62  * geqo
  63  *        solution of the query optimization problem
  64  *        similar to a constrained Traveling Salesman Problem (TSP)
  65  */
  66
  67 RelOptInfo *
  68 geqo(Query *root, int number_of_rels, List *initial_rels)
  69 {
  70         int                     generation;
  71         Chromosome *momma;
  72         Chromosome *daddy;
  73         Chromosome *kid;
  74         Pool       *pool;
  75         int                     pool_size,
  76                                 number_generations,
  77                                 status_interval;
  78         Gene       *best_tour;
  79         RelOptInfo *best_rel;
  80
  81 #if defined(ERX)
  82         Edge       *edge_table;         /* list of edges */
  83         int                     edge_failures = 0;
  84         float           difference;
  85
  86 #endif
  87 #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
  88         City       *city_table;         /* list of cities */
  89
  90 #endif
  91 #if defined(CX)
  92         int                     cycle_diffs = 0;
  93         int                     mutations = 0;
  94
  95 #endif
  96
  97 /* set GA parameters */
  98         pool_size = gimme_pool_size(number_of_rels);
  99         number_generations = gimme_number_generations(pool_size, Geqo_effort);
 100         status_interval = 10;
 101
 102 /* seed random number generator */
 103 /* XXX why is this done every time around? */
 104         if (Geqo_random_seed >= 0)
 105                 srandom((unsigned int) Geqo_random_seed);
 106         else
 107                 srandom((unsigned int) time(NULL));
 108
 109 /* allocate genetic pool memory */
 110         pool = alloc_pool(pool_size, number_of_rels);
 111
 112 /* random initialization of the pool */
 113         random_init_pool(root, initial_rels, pool, 0, pool->size);
 114
 115 /* sort the pool according to cheapest path as fitness */
 116         sort_pool(pool);                        /* we have to do it only one time, since
 117                                                                  * all kids replace the worst individuals
 118                                                                  * in future (-> geqo_pool.c:spread_chromo
 119                                                                  * ) */
 120
 121 /* allocate chromosome momma and daddy memory */
 122         momma = alloc_chromo(pool->string_length);
 123         daddy = alloc_chromo(pool->string_length);
 124
 125 #if defined (ERX)
 126         elog(DEBUG, "geqo_main: using edge recombination crossover [ERX]");
 127 /* allocate edge table memory */
 128         edge_table = alloc_edge_table(pool->string_length);
 129 #elif defined(PMX)
 130         elog(DEBUG, "geqo_main: using partially matched crossover [PMX]");
 131 /* allocate chromosome kid memory */
 132         kid = alloc_chromo(pool->string_length);
 133 #elif defined(CX)
 134         elog(DEBUG, "geqo_main: using cycle crossover [CX]");
 135 /* allocate city table memory */
 136         kid = alloc_chromo(pool->string_length);
 137         city_table = alloc_city_table(pool->string_length);
 138 #elif defined(PX)
 139         elog(DEBUG, "geqo_main: using position crossover [PX]");
 140 /* allocate city table memory */
 141         kid = alloc_chromo(pool->string_length);
 142         city_table = alloc_city_table(pool->string_length);
 143 #elif defined(OX1)
 144         elog(DEBUG, "geqo_main: using order crossover [OX1]");
 145 /* allocate city table memory */
 146         kid = alloc_chromo(pool->string_length);
 147         city_table = alloc_city_table(pool->string_length);
 148 #elif defined(OX2)
 149         elog(DEBUG, "geqo_main: using order crossover [OX2]");
 150 /* allocate city table memory */
 151         kid = alloc_chromo(pool->string_length);
 152         city_table = alloc_city_table(pool->string_length);
 153 #endif
 154
 155
 156 /* my pain main part: */
 157 /* iterative optimization */
 158
 159         for (generation = 0; generation < number_generations; generation++)
 160         {
 161
 162                 /* SELECTION */
 163                 geqo_selection(momma, daddy, pool, Geqo_selection_bias);                /* using linear bias
 164                                                                                                                                                  * function */
 165
 166
 167
 168 #if defined (ERX)
 169                 /* EDGE RECOMBINATION CROSSOVER */
 170                 difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);
 171
 172                 /* let the kid grow in momma's womb (storage) for nine months ;-) */
 173                 /* sleep(23328000) -- har har har */
 174                 kid = momma;
 175
 176                 /* are there any edge failures ? */
 177                 edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
 178 #elif defined(PMX)
 179                 /* PARTIALLY MATCHED CROSSOVER */
 180                 pmx(momma->string, daddy->string, kid->string, pool->string_length);
 181 #elif defined(CX)
 182                 /* CYCLE CROSSOVER */
 183                 cycle_diffs = cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 184                 /* mutate the child */
 185                 if (cycle_diffs == 0)
 186                 {
 187                         mutations++;
 188                         geqo_mutation(kid->string, pool->string_length);
 189                 }
 190 #elif defined(PX)
 191                 /* POSITION CROSSOVER */
 192                 px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 193 #elif defined(OX1)
 194                 /* ORDER CROSSOVER */
 195                 ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 196 #elif defined(OX2)
 197                 /* ORDER CROSSOVER */
 198                 ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 199 #endif
 200
 201
 202                 /* EVALUATE FITNESS */
 203                 kid->worth = geqo_eval(root, initial_rels,
 204                                                            kid->string, pool->string_length);
 205
 206                 /* push the kid into the wilderness of life according to its worth */
 207                 spread_chromo(kid, pool);
 208
 209
 210 #ifdef GEQO_DEBUG
 211                 if (status_interval && !(generation % status_interval))
 212                         print_gen(stdout, pool, generation);
 213 #endif
 214
 215         }                                                       /* end of iterative optimization */
 216
 217
 218 #if defined(ERX) && defined(GEQO_DEBUG)
 219         if (edge_failures != 0)
 220                 fprintf(stdout, "\nFailures: %d  Avg: %d\n", edge_failures, (int) generation / edge_failures);
 221
 222         else
 223                 fprintf(stdout, "No edge failures detected.\n");
 224 #endif
 225
 226
 227 #if defined(CX) && defined(GEQO_DEBUG)
 228         if (mutations != 0)
 229                 fprintf(stdout, "\nMutations: %d  Generations: %d\n", mutations, generation);
 230
 231         else
 232                 fprintf(stdout, "No mutations processed.\n");
 233 #endif
 234
 235
 236 #ifdef GEQO_DEBUG
 237         fprintf(stdout, "\n");
 238         print_pool(stdout, pool, 0, pool_size - 1);
 239 #endif
 240
 241
 242 /* got the cheapest query tree processed by geqo;
 243    first element of the population indicates the best query tree */
 244
 245         best_tour = (Gene *) pool->data[0].string;
 246
 247 /* root->join_rel_list will be modified during this ! */
 248         best_rel = gimme_tree(root, initial_rels,
 249                                                   best_tour, pool->string_length,
 250                                                   0, NULL);
 251
 252 /* DBG: show the query plan
 253 print_plan(best_plan, root);
 254    DBG */
 255
 256 /* ... free memory stuff */
 257         free_chromo(momma);
 258         free_chromo(daddy);
 259
 260 #if defined (ERX)
 261         free_edge_table(edge_table);
 262 #elif defined(PMX)
 263         free_chromo(kid);
 264 #elif defined(CX)
 265         free_chromo(kid);
 266         free_city_table(city_table);
 267 #elif defined(PX)
 268         free_chromo(kid);
 269         free_city_table(city_table);
 270 #elif defined(OX1)
 271         free_chromo(kid);
 272         free_city_table(city_table);
 273 #elif defined(OX2)
 274         free_chromo(kid);
 275         free_city_table(city_table);
 276 #endif
 277
 278         free_pool(pool);
 279
 280         return best_rel;
 281 }
 282
 283
 284
 285 /*
 286  * Return either configured pool size or
 287  * a good default based on query size (no. of relations)
 288  * = 2^(QS+1)
 289  * also constrain between 128 and 1024
 290  */
 291 static int
 292 gimme_pool_size(int nr_rel)
 293 {
 294         double          size;
 295
 296         if (Geqo_pool_size != 0)
 297         {
 298                 if (Geqo_pool_size < MIN_GEQO_POOL_SIZE)
 299                         return MIN_GEQO_POOL_SIZE;
 300                 else if (Geqo_pool_size > MAX_GEQO_POOL_SIZE)
 301                         return MAX_GEQO_POOL_SIZE;
 302                 else
 303                         return Geqo_pool_size;
 304         }
 305
 306         size = pow(2.0, nr_rel + 1.0);
 307
 308         if (size < MIN_GEQO_POOL_SIZE)
 309                 return MIN_GEQO_POOL_SIZE;
 310         else if (size > MAX_GEQO_POOL_SIZE)
 311                 return MAX_GEQO_POOL_SIZE;
 312         else
 313                 return (int) ceil(size);
 314 }
 315
 316
 317
 318 /*
 319  * Return either configured number of generations or
 320  * some reasonable default calculated on the fly.
 321  * = Effort * Log2(PoolSize)
 322  */
 323 static int
 324 gimme_number_generations(int pool_size, int effort)
 325 {
 326         if (Geqo_generations <= 0)
 327                 return effort * (int) ceil(log((double) pool_size) / log(2.0));
 328         else
 329                 return Geqo_generations;
 330 }