src/backend/optimizer/geqo/geqo_pool.c

   1 /*------------------------------------------------------------------------
   2  *
   3  * geqo_pool.c
   4  *        Genetic Algorithm (GA) pool stuff
   5  *
   6  * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * src/backend/optimizer/geqo/geqo_pool.c
  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 <float.h>
  27 #include <limits.h>
  28 #include <math.h>
  29
  30 #include "optimizer/geqo_copy.h"
  31 #include "optimizer/geqo_pool.h"
  32 #include "optimizer/geqo_recombination.h"
  33
  34
  35 static int      compare(const void *arg1, const void *arg2);
  36
  37 /*
  38  * alloc_pool
  39  *              allocates memory for GA pool
  40  */
  41 Pool *
  42 alloc_pool(PlannerInfo *root, int pool_size, int string_length)
  43 {
  44         Pool       *new_pool;
  45         Chromosome *chromo;
  46         int                     i;
  47
  48         /* pool */
  49         new_pool = (Pool *) palloc(sizeof(Pool));
  50         new_pool->size = (int) pool_size;
  51         new_pool->string_length = (int) string_length;
  52
  53         /* all chromosome */
  54         new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
  55
  56         /* all gene */
  57         chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
  58         for (i = 0; i < pool_size; i++)
  59                 chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
  60
  61         return new_pool;
  62 }
  63
  64 /*
  65  * free_pool
  66  *              deallocates memory for GA pool
  67  */
  68 void
  69 free_pool(PlannerInfo *root, Pool *pool)
  70 {
  71         Chromosome *chromo;
  72         int                     i;
  73
  74         /* all gene */
  75         chromo = (Chromosome *) pool->data; /* vector of all chromos */
  76         for (i = 0; i < pool->size; i++)
  77                 pfree(chromo[i].string);
  78
  79         /* all chromosome */
  80         pfree(pool->data);
  81
  82         /* pool */
  83         pfree(pool);
  84 }
  85
  86 /*
  87  * random_init_pool
  88  *              initialize genetic pool
  89  */
  90 void
  91 random_init_pool(PlannerInfo *root, Pool *pool)
  92 {
  93         Chromosome *chromo = (Chromosome *) pool->data;
  94         int                     i;
  95         int                     bad = 0;
  96
  97         /*
  98          * We immediately discard any invalid individuals (those that geqo_eval
  99          * returns DBL_MAX for), thereby not wasting pool space on them.
 100          *
 101          * If we fail to make any valid individuals after 10000 tries, give up;
 102          * this probably means something is broken, and we shouldn't just let
 103          * ourselves get stuck in an infinite loop.
 104          */
 105         i = 0;
 106         while (i < pool->size)
 107         {
 108                 init_tour(root, chromo[i].string, pool->string_length);
 109                 pool->data[i].worth = geqo_eval(root, chromo[i].string,
 110                                                                                 pool->string_length);
 111                 if (pool->data[i].worth < DBL_MAX)
 112                         i++;
 113                 else
 114                 {
 115                         bad++;
 116                         if (i == 0 && bad >= 10000)
 117                                 elog(ERROR, "geqo failed to make a valid plan");
 118                 }
 119         }
 120
 121 #ifdef GEQO_DEBUG
 122         if (bad > 0)
 123                 elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
 124                          bad, pool->size);
 125 #endif
 126 }
 127
 128 /*
 129  * sort_pool
 130  *       sorts input pool according to worth, from smallest to largest
 131  *
 132  *       maybe you have to change compare() for different ordering ...
 133  */
 134 void
 135 sort_pool(PlannerInfo *root, Pool *pool)
 136 {
 137         qsort(pool->data, pool->size, sizeof(Chromosome), compare);
 138 }
 139
 140 /*
 141  * compare
 142  *       qsort comparison function for sort_pool
 143  */
 144 static int
 145 compare(const void *arg1, const void *arg2)
 146 {
 147         const Chromosome *chromo1 = (const Chromosome *) arg1;
 148         const Chromosome *chromo2 = (const Chromosome *) arg2;
 149
 150         if (chromo1->worth == chromo2->worth)
 151                 return 0;
 152         else if (chromo1->worth > chromo2->worth)
 153                 return 1;
 154         else
 155                 return -1;
 156 }
 157
 158 /* alloc_chromo
 159  *        allocates a chromosome and string space
 160  */
 161 Chromosome *
 162 alloc_chromo(PlannerInfo *root, int string_length)
 163 {
 164         Chromosome *chromo;
 165
 166         chromo = (Chromosome *) palloc(sizeof(Chromosome));
 167         chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
 168
 169         return chromo;
 170 }
 171
 172 /* free_chromo
 173  *        deallocates a chromosome and string space
 174  */
 175 void
 176 free_chromo(PlannerInfo *root, Chromosome *chromo)
 177 {
 178         pfree(chromo->string);
 179         pfree(chromo);
 180 }
 181
 182 /* spread_chromo
 183  *       inserts a new chromosome into the pool, displacing worst gene in pool
 184  *       assumes best->worst = smallest->largest
 185  */
 186 void
 187 spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
 188 {
 189         int                     top,
 190                                 mid,
 191                                 bot;
 192         int                     i,
 193                                 index;
 194         Chromosome      swap_chromo,
 195                                 tmp_chromo;
 196
 197         /* new chromo is so bad we can't use it */
 198         if (chromo->worth > pool->data[pool->size - 1].worth)
 199                 return;
 200
 201         /* do a binary search to find the index of the new chromo */
 202
 203         top = 0;
 204         mid = pool->size / 2;
 205         bot = pool->size - 1;
 206         index = -1;
 207
 208         while (index == -1)
 209         {
 210                 /* these 4 cases find a new location */
 211
 212                 if (chromo->worth <= pool->data[top].worth)
 213                         index = top;
 214                 else if (chromo->worth == pool->data[mid].worth)
 215                         index = mid;
 216                 else if (chromo->worth == pool->data[bot].worth)
 217                         index = bot;
 218                 else if (bot - top <= 1)
 219                         index = bot;
 220
 221
 222                 /*
 223                  * these 2 cases move the search indices since a new location has not
 224                  * yet been found.
 225                  */
 226
 227                 else if (chromo->worth < pool->data[mid].worth)
 228                 {
 229                         bot = mid;
 230                         mid = top + ((bot - top) / 2);
 231                 }
 232                 else
 233                 {                                               /* (chromo->worth > pool->data[mid].worth) */
 234                         top = mid;
 235                         mid = top + ((bot - top) / 2);
 236                 }
 237         }                                                       /* ... while */
 238
 239         /* now we have index for chromo */
 240
 241         /*
 242          * move every gene from index on down one position to make room for chromo
 243          */
 244
 245         /*
 246          * copy new gene into pool storage; always replace worst gene in pool
 247          */
 248
 249         geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
 250
 251         swap_chromo.string = pool->data[pool->size - 1].string;
 252         swap_chromo.worth = pool->data[pool->size - 1].worth;
 253
 254         for (i = index; i < pool->size; i++)
 255         {
 256                 tmp_chromo.string = pool->data[i].string;
 257                 tmp_chromo.worth = pool->data[i].worth;
 258
 259                 pool->data[i].string = swap_chromo.string;
 260                 pool->data[i].worth = swap_chromo.worth;
 261
 262                 swap_chromo.string = tmp_chromo.string;
 263                 swap_chromo.worth = tmp_chromo.worth;
 264         }
 265 }