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  * Copyright (c) 1994, Regents of the University of California
   8  *
   9  * $Id: geqo_main.c,v 1.7 1998/02/26 04:32:22 momjian Exp $
  10  *
  11  *-------------------------------------------------------------------------
  12  */
  13
  14 /* contributed by:
  15    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  16    *  Martin Utesch                              * Institute of Automatic Control          *
  17    =                                                     = University of Mining and Technology =
  18    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                               *
  19    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  20  */
  21
  22 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
  23
  24 #include "postgres.h"
  25
  26 #include "nodes/pg_list.h"
  27 #include "nodes/relation.h"
  28 #include "nodes/plannodes.h"
  29 #include "nodes/primnodes.h"
  30
  31 #include "utils/palloc.h"
  32 #include "utils/elog.h"
  33
  34 #include "optimizer/internal.h"
  35 #include "optimizer/paths.h"
  36 #include "optimizer/pathnode.h"
  37 #include "optimizer/clauses.h"
  38 #include "optimizer/cost.h"
  39
  40 #include "optimizer/geqo_gene.h"
  41 #include "optimizer/geqo.h"
  42 #include "optimizer/geqo_pool.h"
  43 #include "optimizer/geqo_selection.h"
  44 #include "optimizer/geqo_recombination.h"
  45 #include "optimizer/geqo_mutation.h"
  46 #include "optimizer/geqo_misc.h"
  47
  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 Rel *
  67 geqo(Query *root)
  68 {
  69         int                     generation;
  70         Chromosome *momma;
  71         Chromosome *daddy;
  72         Chromosome *kid;
  73
  74 #if defined(ERX)
  75         Edge       *edge_table;         /* list of edges */
  76         int                     edge_failures = 0;
  77         float           difference;
  78
  79 #endif
  80
  81 #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
  82         City       *city_table;         /* list of cities */
  83
  84 #endif
  85
  86 #if defined(CX)
  87         int                     cycle_diffs = 0;
  88         int                     mutations = 0;
  89
  90 #endif
  91
  92
  93         int                     number_of_rels;
  94
  95         Pool       *pool;
  96         int                     pool_size,
  97                                 number_generations,
  98                                 status_interval;
  99
 100         Gene       *best_tour;
 101         Rel                *best_rel;
 102
 103 /*      Plan *best_plan; */
 104
 105
 106 /* set tour size */
 107         number_of_rels = length(root->base_relation_list_);
 108
 109 /* set GA parameters */
 110         geqo_params(number_of_rels);/* out of "$PGDATA/pg_geqo" file */
 111         pool_size = PoolSize;
 112         number_generations = Generations;
 113         status_interval = 10;
 114
 115 /* seed random number generator */
 116         srandom(RandomSeed);
 117
 118 /* allocate genetic pool memory */
 119         pool = alloc_pool(pool_size, number_of_rels);
 120
 121 /* random initialization of the pool */
 122         random_init_pool(root, pool, 0, pool->size);
 123
 124 /* sort the pool according to cheapest path as fitness */
 125         sort_pool(pool);                        /* we have to do it only one time, since
 126                                                                  * all kids replace the worst individuals
 127                                                                  * in future (-> geqo_pool.c:spread_chromo
 128                                                                  * ) */
 129
 130 /* allocate chromosome momma and daddy memory */
 131         momma = alloc_chromo(pool->string_length);
 132         daddy = alloc_chromo(pool->string_length);
 133
 134 #if defined (ERX)
 135         elog(DEBUG, "geqo_main: using edge recombination crossover [ERX]");
 136 /* allocate edge table memory */
 137         edge_table = alloc_edge_table(pool->string_length);
 138 #elif defined(PMX)
 139         elog(DEBUG, "geqo_main: using partially matched crossover [PMX]");
 140 /* allocate chromosome kid memory */
 141         kid = alloc_chromo(pool->string_length);
 142 #elif defined(CX)
 143         elog(DEBUG, "geqo_main: using cycle crossover [CX]");
 144 /* allocate city table memory */
 145         kid = alloc_chromo(pool->string_length);
 146         city_table = alloc_city_table(pool->string_length);
 147 #elif defined(PX)
 148         elog(DEBUG, "geqo_main: using position crossover [PX]");
 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         elog(DEBUG, "geqo_main: using order crossover [OX1]");
 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         elog(DEBUG, "geqo_main: using order crossover [OX2]");
 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
 171                 /* SELECTION */
 172                 geqo_selection(momma, daddy, pool, SelectionBias);              /* using linear bias
 173                                                                                                                                  * function */
 174
 175
 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                 /* let the kid grow in momma's womb (storage) for nine months ;-) */
 182                 /* sleep(23328000) -- har har har */
 183                 kid = momma;
 184
 185                 /* are there any edge failures ? */
 186                 edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
 187 #elif defined(PMX)
 188                 /* PARTIALLY MATCHED CROSSOVER */
 189                 pmx(momma->string, daddy->string, kid->string, pool->string_length);
 190 #elif defined(CX)
 191                 /* CYCLE CROSSOVER */
 192                 cycle_diffs =
 193                         cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 194                 /* mutate the child */
 195                 if (cycle_diffs == 0)
 196                 {
 197                         mutations++;
 198                         geqo_mutation(kid->string, pool->string_length);
 199                 }
 200 #elif defined(PX)
 201                 /* POSITION CROSSOVER */
 202                 px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 203 #elif defined(OX1)
 204                 /* ORDER CROSSOVER */
 205                 ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 206 #elif defined(OX2)
 207                 /* ORDER CROSSOVER */
 208                 ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
 209 #endif
 210
 211
 212                 /* EVALUATE FITNESS */
 213                 kid->worth = geqo_eval(root, kid->string, pool->string_length);
 214
 215                 /* push the kid into the wilderness of life according to its worth */
 216                 spread_chromo(kid, pool);
 217
 218
 219 #ifdef GEQO_DEBUG
 220                 if (status_interval && !(generation % status_interval))
 221                         print_gen(stdout, pool, generation);
 222 #endif
 223
 224         }                                                       /* end of iterative optimization */
 225
 226
 227 #if defined(ERX) && defined(GEQO_DEBUG)
 228         if (edge_failures != 0)
 229                 fprintf(stdout, "\nFailures: %d  Avg: %d\n", edge_failures, (int) generation / edge_failures);
 230
 231         else
 232                 fprintf(stdout, "No edge failures detected.\n");
 233 #endif
 234
 235
 236 #if defined(CX) && defined(GEQO_DEBUG)
 237         if (mutations != 0)
 238                 fprintf(stdout, "\nMutations: %d  Generations: %d\n", mutations, generation);
 239
 240         else
 241                 fprintf(stdout, "No mutations processed.\n");
 242 #endif
 243
 244
 245 #ifdef GEQO_DEBUG
 246         fprintf(stdout, "\n");
 247         print_pool(stdout, pool, 0, pool_size - 1);
 248 #endif
 249
 250
 251 /* got the cheapest query tree processed by geqo;
 252    first element of the population indicates the best query tree */
 253
 254         best_tour = (Gene *) pool->data[0].string;
 255
 256 /* root->join_relation_list_ will be modified during this ! */
 257         best_rel = (Rel *) gimme_tree(root, best_tour, 0, pool->string_length, NULL);
 258
 259 /* DBG: show the query plan
 260 print_plan(best_plan, root);
 261    DBG */
 262
 263 /* ... free memory stuff */
 264         free_chromo(momma);
 265         free_chromo(daddy);
 266
 267 #if defined (ERX)
 268         free_edge_table(edge_table);
 269 #elif defined(PMX)
 270         free_chromo(kid);
 271 #elif defined(CX)
 272         free_chromo(kid);
 273         free_city_table(city_table);
 274 #elif defined(PX)
 275         free_chromo(kid);
 276         free_city_table(city_table);
 277 #elif defined(OX1)
 278         free_chromo(kid);
 279         free_city_table(city_table);
 280 #elif defined(OX2)
 281         free_chromo(kid);
 282         free_city_table(city_table);
 283 #endif
 284
 285         free_pool(pool);
 286
 287         return (best_rel);
 288 }