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