PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
geqo_selection.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * geqo_selection.c
4 * linear selection scheme for the genetic query optimizer
5 *
6 * Portions Copyright (c) 1996-2025, 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"
44
45static 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 */
53void
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 if (pool->size > 1)
68 {
69 while (first == second)
70 second = linear_rand(root, pool->size, bias);
71 }
72
73 geqo_copy(root, momma, &pool->data[first], pool->string_length);
74 geqo_copy(root, daddy, &pool->data[second], pool->string_length);
75}
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 */
87static int
88linear_rand(PlannerInfo *root, int pool_size, double bias)
89{
90 double index; /* index between 0 and pool_size */
91 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 sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
105 if (sqrtval > 0.0)
106 sqrtval = sqrt(sqrtval);
107 index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
108 } while (index < 0.0 || index >= max);
109
110 return (int) index;
111}
void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length)
Definition: geqo_copy.c:45
double geqo_rand(PlannerInfo *root)
Definition: geqo_random.c:28
static int linear_rand(PlannerInfo *root, int pool_size, double bias)
void geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
tree ctl root
Definition: radixtree.h:1857
Definition: geqo_gene.h:39
int string_length
Definition: geqo_gene.h:42
int size
Definition: geqo_gene.h:41
Chromosome * data
Definition: geqo_gene.h:40
Definition: type.h:96