LCOV - code coverage report
Current view: top level - src/backend/optimizer/geqo - geqo_main.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 40 45 88.9 %
Date: 2019-11-21 14:06:36 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13