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