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

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