1 /*-------------------------------------------------------------------------
2 *
3 * geqo_selection.c
4 * linear selection scheme for the genetic query optimizer
5 *
6 * Portions Copyright (c) 1996-2021, 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
geqo_selection(PlannerInfo * root,Chromosome * momma,Chromosome * daddy,Pool * pool,double bias)54 geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
55 Pool *pool, double bias)
56 {
57 int first,
58 second;
59
60 first = linear_rand(root, pool->size, bias);
61 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 if (pool->size > 1)
72 {
73 while (first == second)
74 second = linear_rand(root, pool->size, bias);
75 }
76
77 geqo_copy(root, momma, &pool->data[first], pool->string_length);
78 geqo_copy(root, daddy, &pool->data[second], pool->string_length);
79 }
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
linear_rand(PlannerInfo * root,int pool_size,double bias)92 linear_rand(PlannerInfo *root, int pool_size, double bias)
93 {
94 double index; /* index between 0 and pool_size */
95 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 sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
109 if (sqrtval > 0.0)
110 sqrtval = sqrt(sqrtval);
111 index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
112 } while (index < 0.0 || index >= max);
113
114 return (int) index;
115 }
116