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-2026, 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 pool_size, 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         1092 : geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
      55              :                Pool *pool, double bias)
      56              : {
      57              :     int         first,
      58              :                 second;
      59              : 
      60         1092 :     first = linear_rand(root, pool->size, bias);
      61         1092 :     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         1092 :     if (pool->size > 1)
      68              :     {
      69         1170 :         while (first == second)
      70           78 :             second = linear_rand(root, pool->size, bias);
      71              :     }
      72              : 
      73         1092 :     geqo_copy(root, momma, &pool->data[first], pool->string_length);
      74         1092 :     geqo_copy(root, daddy, &pool->data[second], pool->string_length);
      75         1092 : }
      76              : 
      77              : /*
      78              :  * linear_rand
      79              :  *    generates random integer between 0 and input max number
      80              :  *    using input linear bias
      81              :  *
      82              :  *    bias is y-intercept of linear distribution
      83              :  *
      84              :  *    probability distribution function is: f(x) = bias - 2(bias - 1)x
      85              :  *           bias = (prob of first rule) / (prob of middle rule)
      86              :  */
      87              : static int
      88         2262 : linear_rand(PlannerInfo *root, int pool_size, double bias)
      89              : {
      90              :     double      index;          /* index between 0 and pool_size */
      91         2262 :     double      max = (double) pool_size;
      92              : 
      93              :     /*
      94              :      * geqo_rand() is not supposed to return 1.0, but if it does then we will
      95              :      * get exactly max from this equation, whereas we need 0 <= index < max.
      96              :      * Also it seems possible that roundoff error might deliver values
      97              :      * slightly outside the range; in particular avoid passing a value
      98              :      * slightly less than 0 to sqrt().  If we get a bad value just try again.
      99              :      */
     100              :     do
     101              :     {
     102              :         double      sqrtval;
     103              : 
     104         2262 :         sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
     105         2262 :         if (sqrtval > 0.0)
     106         2262 :             sqrtval = sqrt(sqrtval);
     107         2262 :         index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
     108         2262 :     } while (index < 0.0 || index >= max);
     109              : 
     110         2262 :     return (int) index;
     111              : }