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