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-2006, 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.52 2006/03/05 15:58:28 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 <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 all
 110                                                                  * kids replace the worst individuals in
 111                                                                  * future (-> geqo_pool.c:spread_chromo ) */
 112
 113 #ifdef GEQO_DEBUG
 114         elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
 115                  pool_size,
 116                  pool->data[0].worth,
 117                  pool->data[pool_size - 1].worth);
 118 #endif
 119
 120 /* allocate chromosome momma and daddy memory */
 121         momma = alloc_chromo(pool->string_length);
 122         daddy = alloc_chromo(pool->string_length);
 123
 124 #if defined (ERX)
 125 #ifdef GEQO_DEBUG
 126         elog(DEBUG2, "using edge recombination crossover [ERX]");
 127 #endif
 128 /* allocate edge table memory */
 129         edge_table = alloc_edge_table(pool->string_length);
 130 #elif defined(PMX)
 131 #ifdef GEQO_DEBUG
 132         elog(DEBUG2, "using partially matched crossover [PMX]");
 133 #endif
 134 /* allocate chromosome kid memory */
 135         kid = alloc_chromo(pool->string_length);
 136 #elif defined(CX)
 137 #ifdef GEQO_DEBUG
 138         elog(DEBUG2, "using cycle crossover [CX]");
 139 #endif
 140 /* allocate city table memory */
 141         kid = alloc_chromo(pool->string_length);
 142         city_table = alloc_city_table(pool->string_length);
 143 #elif defined(PX)
 144 #ifdef GEQO_DEBUG
 145         elog(DEBUG2, "using position crossover [PX]");
 146 #endif
 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 #ifdef GEQO_DEBUG
 152         elog(DEBUG2, "using order crossover [OX1]");
 153 #endif
 154 /* allocate city table memory */
 155         kid = alloc_chromo(pool->string_length);
 156         city_table = alloc_city_table(pool->string_length);
 157 #elif defined(OX2)
 158 #ifdef GEQO_DEBUG
 159         elog(DEBUG2, "using order crossover [OX2]");
 160 #endif
 161 /* allocate city table memory */
 162         kid = alloc_chromo(pool->string_length);
 163         city_table = alloc_city_table(pool->string_length);
 164 #endif
 165
 166
 167 /* my pain main part: */
 168 /* iterative optimization */
 169
 170         for (generation = 0; generation < number_generations; generation++)
 171         {
 172                 /* SELECTION: using linear bias function */
 173                 geqo_selection(momma, daddy, pool, Geqo_selection_bias);
 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                 kid = momma;
 180
 181                 /* are there any edge failures ? */
 182                 edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
 183 #elif defined(PMX)
 184                 /* PARTIALLY MATCHED CROSSOVER */
 185                 pmx(momma->string, daddy->string, kid->string, pool->string_length);
 186 #elif defined(CX)
 187                 /* CYCLE CROSSOVER */
 188                 cycle_diffs = cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 189                 /* mutate the child */
 190                 if (cycle_diffs == 0)
 191                 {
 192                         mutations++;
 193                         geqo_mutation(kid->string, pool->string_length);
 194                 }
 195 #elif defined(PX)
 196                 /* POSITION CROSSOVER */
 197                 px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 198 #elif defined(OX1)
 199                 /* ORDER CROSSOVER */
 200                 ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 201 #elif defined(OX2)
 202                 /* ORDER CROSSOVER */
 203                 ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 204 #endif
 205
 206
 207                 /* EVALUATE FITNESS */
 208                 kid->worth = geqo_eval(kid->string, pool->string_length, &evaldata);
 209
 210                 /* push the kid into the wilderness of life according to its worth */
 211                 spread_chromo(kid, pool);
 212
 213
 214 #ifdef GEQO_DEBUG
 215                 if (status_interval && !(generation % status_interval))
 216                         print_gen(stdout, pool, generation);
 217 #endif
 218
 219         }
 220
 221
 222 #if defined(ERX) && defined(GEQO_DEBUG)
 223         if (edge_failures != 0)
 224                 elog(LOG, "[GEQO] failures: %d, average: %d",
 225                          edge_failures, (int) number_generations / edge_failures);
 226         else
 227                 elog(LOG, "[GEQO] no edge failures detected");
 228 #endif
 229
 230 #if defined(CX) && defined(GEQO_DEBUG)
 231         if (mutations != 0)
 232                 elog(LOG, "[GEQO] mutations: %d, generations: %d",
 233                          mutations, number_generations);
 234         else
 235                 elog(LOG, "[GEQO] no mutations processed");
 236 #endif
 237
 238 #ifdef GEQO_DEBUG
 239         print_pool(stdout, pool, 0, pool_size - 1);
 240 #endif
 241
 242 #ifdef GEQO_DEBUG
 243         elog(DEBUG1, "GEQO best is %.2f after %d generations",
 244                  pool->data[0].worth, number_generations);
 245 #endif
 246
 247
 248         /*
 249          * got the cheapest query tree processed by geqo; first element of the
 250          * population indicates the best query tree
 251          */
 252         best_tour = (Gene *) pool->data[0].string;
 253
 254         best_rel = gimme_tree(best_tour, pool->string_length, &evaldata);
 255
 256         if (best_rel == NULL)
 257                 elog(ERROR, "failed to make a valid plan");
 258
 259         /* DBG: show the query plan */
 260 #ifdef NOT_USED
 261         print_plan(best_plan, root);
 262 #endif
 263
 264         /* ... free memory stuff */
 265         free_chromo(momma);
 266         free_chromo(daddy);
 267
 268 #if defined (ERX)
 269         free_edge_table(edge_table);
 270 #elif defined(PMX)
 271         free_chromo(kid);
 272 #elif defined(CX)
 273         free_chromo(kid);
 274         free_city_table(city_table);
 275 #elif defined(PX)
 276         free_chromo(kid);
 277         free_city_table(city_table);
 278 #elif defined(OX1)
 279         free_chromo(kid);
 280         free_city_table(city_table);
 281 #elif defined(OX2)
 282         free_chromo(kid);
 283         free_city_table(city_table);
 284 #endif
 285
 286         free_pool(pool);
 287
 288         return best_rel;
 289 }
 290
 291
 292 /*
 293  * Return either configured pool size or a good default
 294  *
 295  * The default is based on query size (no. of relations) = 2^(QS+1),
 296  * but constrained to a range based on the effort value.
 297  */
 298 static int
 299 gimme_pool_size(int nr_rel)
 300 {
 301         double          size;
 302         int                     minsize;
 303         int                     maxsize;
 304
 305         /* Legal pool size *must* be at least 2, so ignore attempt to select 1 */
 306         if (Geqo_pool_size >= 2)
 307                 return Geqo_pool_size;
 308
 309         size = pow(2.0, nr_rel + 1.0);
 310
 311         maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
 312         if (size > maxsize)
 313                 return maxsize;
 314
 315         minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
 316         if (size < minsize)
 317                 return minsize;
 318
 319         return (int) ceil(size);
 320 }
 321
 322
 323 /*
 324  * Return either configured number of generations or a good default
 325  *
 326  * The default is the same as the pool size, which allows us to be
 327  * sure that less-fit individuals get pushed out of the breeding
 328  * population before the run finishes.
 329  */
 330 static int
 331 gimme_number_generations(int pool_size)
 332 {
 333         if (Geqo_generations > 0)
 334                 return Geqo_generations;
 335
 336         return pool_size;
 337 }