summaryrefslogtreecommitdiffstats
path: root/src/backend/optimizer/geqo/geqo_selection.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:17:33 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:17:33 +0000
commit5e45211a64149b3c659b90ff2de6fa982a5a93ed (patch)
tree739caf8c461053357daa9f162bef34516c7bf452 /src/backend/optimizer/geqo/geqo_selection.c
parentInitial commit. (diff)
downloadpostgresql-15-5e45211a64149b3c659b90ff2de6fa982a5a93ed.tar.xz
postgresql-15-5e45211a64149b3c659b90ff2de6fa982a5a93ed.zip
Adding upstream version 15.5.upstream/15.5
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_selection.c')
-rw-r--r--src/backend/optimizer/geqo/geqo_selection.c111
1 files changed, 111 insertions, 0 deletions
diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c
new file mode 100644
index 0000000..50f678a
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_selection.c
@@ -0,0 +1,111 @@
+/*-------------------------------------------------------------------------
+ *
+ * geqo_selection.c
+ * linear selection scheme for the genetic query optimizer
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_selection.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* this is adopted from D. Whitley's Genitor algorithm */
+
+/*************************************************************/
+/* */
+/* Copyright (c) 1990 */
+/* Darrell L. Whitley */
+/* Computer Science Department */
+/* Colorado State University */
+/* */
+/* Permission is hereby granted to copy all or any part of */
+/* this program for free distribution. The author's name */
+/* and this copyright notice must be included in any copy. */
+/* */
+/*************************************************************/
+
+#include "postgres.h"
+
+#include <math.h>
+
+#include "optimizer/geqo_copy.h"
+#include "optimizer/geqo_random.h"
+#include "optimizer/geqo_selection.h"
+
+static int linear_rand(PlannerInfo *root, int max, double bias);
+
+
+/*
+ * geqo_selection
+ * according to bias described by input parameters,
+ * first and second genes are selected from the pool
+ */
+void
+geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
+ Pool *pool, double bias)
+{
+ int first,
+ second;
+
+ first = linear_rand(root, pool->size, bias);
+ second = linear_rand(root, pool->size, bias);
+
+ /*
+ * Ensure we have selected different genes, except if pool size is only
+ * one, when we can't.
+ */
+ if (pool->size > 1)
+ {
+ while (first == second)
+ second = linear_rand(root, pool->size, bias);
+ }
+
+ geqo_copy(root, momma, &pool->data[first], pool->string_length);
+ geqo_copy(root, daddy, &pool->data[second], pool->string_length);
+}
+
+/*
+ * linear_rand
+ * generates random integer between 0 and input max number
+ * using input linear bias
+ *
+ * bias is y-intercept of linear distribution
+ *
+ * probability distribution function is: f(x) = bias - 2(bias - 1)x
+ * bias = (prob of first rule) / (prob of middle rule)
+ */
+static int
+linear_rand(PlannerInfo *root, int pool_size, double bias)
+{
+ double index; /* index between 0 and pool_size */
+ double max = (double) pool_size;
+
+ /*
+ * geqo_rand() is not supposed to return 1.0, but if it does then we will
+ * get exactly max from this equation, whereas we need 0 <= index < max.
+ * Also it seems possible that roundoff error might deliver values
+ * slightly outside the range; in particular avoid passing a value
+ * slightly less than 0 to sqrt(). If we get a bad value just try again.
+ */
+ do
+ {
+ double sqrtval;
+
+ sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
+ if (sqrtval > 0.0)
+ sqrtval = sqrt(sqrtval);
+ index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
+ } while (index < 0.0 || index >= max);
+
+ return (int) index;
+}