Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * geqo_selection.c
       4             :  *    linear selection scheme for the genetic query optimizer
       5             :  *
       6             :  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  * src/backend/optimizer/geqo/geqo_selection.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             : /* this is adopted from D. Whitley's Genitor algorithm */
      23             : 
      24             : /*************************************************************/
      25             : /*                                                           */
      26             : /*  Copyright (c) 1990                                       */
      27             : /*  Darrell L. Whitley                                       */
      28             : /*  Computer Science Department                              */
      29             : /*  Colorado State University                                */
      30             : /*                                                           */
      31             : /*  Permission is hereby granted to copy all or any part of  */
      32             : /*  this program for free distribution.   The author's name  */
      33             : /*  and this copyright notice must be included in any copy.  */
      34             : /*                                                           */
      35             : /*************************************************************/
      36             : 
      37             : #include "postgres.h"
      38             : 
      39             : #include <math.h>
      40             : 
      41             : #include "optimizer/geqo_copy.h"
      42             : #include "optimizer/geqo_random.h"
      43             : #include "optimizer/geqo_selection.h"
      44             : 
      45             : static int  linear_rand(PlannerInfo *root, int max, double bias);
      46             : 
      47             : 
      48             : /*
      49             :  * geqo_selection
      50             :  *   according to bias described by input parameters,
      51             :  *   first and second genes are selected from the pool
      52             :  */
      53             : void
      54          64 : geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
      55             :                Pool *pool, double bias)
      56             : {
      57             :     int         first,
      58             :                 second;
      59             : 
      60          64 :     first = linear_rand(root, pool->size, bias);
      61          64 :     second = linear_rand(root, pool->size, bias);
      62             : 
      63             :     /*
      64             :      * Ensure we have selected different genes, except if pool size is only
      65             :      * one, when we can't.
      66             :      *
      67             :      * This code was observed to hang up in an infinite loop when the
      68             :      * platform's implementation of erand48() was broken.  We now always use
      69             :      * our own version.
      70             :      */
      71          64 :     if (pool->size > 1)
      72             :     {
      73         128 :         while (first == second)
      74           0 :             second = linear_rand(root, pool->size, bias);
      75             :     }
      76             : 
      77          64 :     geqo_copy(root, momma, &pool->data[first], pool->string_length);
      78          64 :     geqo_copy(root, daddy, &pool->data[second], pool->string_length);
      79          64 : }
      80             : 
      81             : /*
      82             :  * linear_rand
      83             :  *    generates random integer between 0 and input max number
      84             :  *    using input linear bias
      85             :  *
      86             :  *    bias is y-intercept of linear distribution
      87             :  *
      88             :  *    probability distribution function is: f(x) = bias - 2(bias - 1)x
      89             :  *           bias = (prob of first rule) / (prob of middle rule)
      90             :  */
      91             : static int
      92         128 : linear_rand(PlannerInfo *root, int pool_size, double bias)
      93             : {
      94             :     double      index;          /* index between 0 and pop_size */
      95         128 :     double      max = (double) pool_size;
      96             : 
      97             :     /*
      98             :      * If geqo_rand() returns exactly 1.0 then we will get exactly max from
      99             :      * this equation, whereas we need 0 <= index < max.  Also it seems
     100             :      * possible that roundoff error might deliver values slightly outside the
     101             :      * range; in particular avoid passing a value slightly less than 0 to
     102             :      * sqrt(). If we get a bad value just try again.
     103             :      */
     104             :     do
     105             :     {
     106             :         double      sqrtval;
     107             : 
     108         128 :         sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
     109         128 :         if (sqrtval > 0.0)
     110         128 :             sqrtval = sqrt(sqrtval);
     111         128 :         index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
     112         128 :     } while (index < 0.0 || index >= max);
     113             : 
     114         128 :     return (int) index;
     115             : }