summaryrefslogtreecommitdiffstats
path: root/src/backend/optimizer/geqo
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/optimizer/geqo')
-rw-r--r--src/backend/optimizer/geqo/Makefile33
-rw-r--r--src/backend/optimizer/geqo/geqo_copy.c54
-rw-r--r--src/backend/optimizer/geqo/geqo_cx.c123
-rw-r--r--src/backend/optimizer/geqo/geqo_erx.c468
-rw-r--r--src/backend/optimizer/geqo/geqo_eval.c338
-rw-r--r--src/backend/optimizer/geqo/geqo_main.c353
-rw-r--r--src/backend/optimizer/geqo/geqo_misc.c132
-rw-r--r--src/backend/optimizer/geqo/geqo_mutation.c66
-rw-r--r--src/backend/optimizer/geqo/geqo_ox1.c94
-rw-r--r--src/backend/optimizer/geqo/geqo_ox2.c111
-rw-r--r--src/backend/optimizer/geqo/geqo_pmx.c218
-rw-r--r--src/backend/optimizer/geqo/geqo_pool.c265
-rw-r--r--src/backend/optimizer/geqo/geqo_px.c107
-rw-r--r--src/backend/optimizer/geqo/geqo_random.c45
-rw-r--r--src/backend/optimizer/geqo/geqo_recombination.c92
-rw-r--r--src/backend/optimizer/geqo/geqo_selection.c111
16 files changed, 2610 insertions, 0 deletions
diff --git a/src/backend/optimizer/geqo/Makefile b/src/backend/optimizer/geqo/Makefile
new file mode 100644
index 0000000..1978c14
--- /dev/null
+++ b/src/backend/optimizer/geqo/Makefile
@@ -0,0 +1,33 @@
+#-------------------------------------------------------------------------
+#
+# Makefile--
+# Makefile for the genetic query optimizer module
+#
+# Copyright (c) 1994, Regents of the University of California
+#
+# src/backend/optimizer/geqo/Makefile
+#
+#-------------------------------------------------------------------------
+
+subdir = src/backend/optimizer/geqo
+top_builddir = ../../../..
+include $(top_builddir)/src/Makefile.global
+
+OBJS = \
+ geqo_copy.o \
+ geqo_cx.o \
+ geqo_erx.o \
+ geqo_eval.o \
+ geqo_main.o \
+ geqo_misc.o \
+ geqo_mutation.o \
+ geqo_ox1.o \
+ geqo_ox2.o \
+ geqo_pmx.o \
+ geqo_pool.o \
+ geqo_px.o \
+ geqo_random.o \
+ geqo_recombination.o \
+ geqo_selection.o
+
+include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/geqo/geqo_copy.c b/src/backend/optimizer/geqo/geqo_copy.c
new file mode 100644
index 0000000..62302f4
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_copy.c
@@ -0,0 +1,54 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_copy.c
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_copy.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 "optimizer/geqo_copy.h"
+
+/* geqo_copy
+ *
+ * copies one gene to another
+ *
+ */
+void
+geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2,
+ int string_length)
+{
+ int i;
+
+ for (i = 0; i < string_length; i++)
+ chromo1->string[i] = chromo2->string[i];
+
+ chromo1->worth = chromo2->worth;
+}
diff --git a/src/backend/optimizer/geqo/geqo_cx.c b/src/backend/optimizer/geqo/geqo_cx.c
new file mode 100644
index 0000000..34cc53a
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_cx.c
@@ -0,0 +1,123 @@
+/*------------------------------------------------------------------------
+*
+* geqo_cx.c
+*
+* cycle crossover [CX] routines;
+* CX operator according to Oliver et al
+* (Proc 2nd Int'l Conf on GA's)
+*
+* src/backend/optimizer/geqo/geqo_cx.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the cx algorithm is adopted from Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(CX)
+
+/* cx
+ *
+ * cycle crossover
+ */
+int
+cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
+ int num_gene, City * city_table)
+{
+ int i,
+ start_pos,
+ curr_pos;
+ int count = 0;
+ int num_diffs = 0;
+
+ /* initialize city table */
+ for (i = 1; i <= num_gene; i++)
+ {
+ city_table[i].used = 0;
+ city_table[tour2[i - 1]].tour2_position = i - 1;
+ city_table[tour1[i - 1]].tour1_position = i - 1;
+ }
+
+ /* choose random cycle starting position */
+ start_pos = geqo_randint(root, num_gene - 1, 0);
+
+ /* child inherits first city */
+ offspring[start_pos] = tour1[start_pos];
+
+ /* begin cycle with tour1 */
+ curr_pos = start_pos;
+ city_table[(int) tour1[start_pos]].used = 1;
+
+ count++;
+
+ /* cx main part */
+
+
+/* STEP 1 */
+
+ while (tour2[curr_pos] != tour1[start_pos])
+ {
+ city_table[(int) tour2[curr_pos]].used = 1;
+ curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
+ offspring[curr_pos] = tour1[curr_pos];
+ count++;
+ }
+
+
+/* STEP 2 */
+
+ /* failed to create a complete tour */
+ if (count < num_gene)
+ {
+ for (i = 1; i <= num_gene; i++)
+ {
+ if (!city_table[i].used)
+ {
+ offspring[city_table[i].tour2_position] =
+ tour2[(int) city_table[i].tour2_position];
+ count++;
+ }
+ }
+ }
+
+
+/* STEP 3 */
+
+ /* still failed to create a complete tour */
+ if (count < num_gene)
+ {
+
+ /* count the number of differences between mom and offspring */
+ for (i = 0; i < num_gene; i++)
+ if (tour1[i] != offspring[i])
+ num_diffs++;
+ }
+
+ return num_diffs;
+}
+
+#endif /* defined(CX) */
diff --git a/src/backend/optimizer/geqo/geqo_erx.c b/src/backend/optimizer/geqo/geqo_erx.c
new file mode 100644
index 0000000..cc06613
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_erx.c
@@ -0,0 +1,468 @@
+/*------------------------------------------------------------------------
+*
+* geqo_erx.c
+* edge recombination crossover [ER]
+*
+* src/backend/optimizer/geqo/geqo_erx.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the edge recombination algorithm is adopted from Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(ERX)
+
+static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
+static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
+static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
+
+static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene);
+
+
+/* alloc_edge_table
+ *
+ * allocate memory for edge table
+ *
+ */
+
+Edge *
+alloc_edge_table(PlannerInfo *root, int num_gene)
+{
+ Edge *edge_table;
+
+ /*
+ * palloc one extra location so that nodes numbered 1..n can be indexed
+ * directly; 0 will not be used
+ */
+
+ edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
+
+ return edge_table;
+}
+
+/* free_edge_table
+ *
+ * deallocate memory of edge table
+ *
+ */
+void
+free_edge_table(PlannerInfo *root, Edge *edge_table)
+{
+ pfree(edge_table);
+}
+
+/* gimme_edge_table
+ *
+ * fills a data structure which represents the set of explicit
+ * edges between points in the (2) input genes
+ *
+ * assumes circular tours and bidirectional edges
+ *
+ * gimme_edge() will set "shared" edges to negative values
+ *
+ * returns average number edges/city in range 2.0 - 4.0
+ * where 2.0=homogeneous; 4.0=diverse
+ *
+ */
+float
+gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
+ int num_gene, Edge *edge_table)
+{
+ int i,
+ index1,
+ index2;
+ int edge_total; /* total number of unique edges in two genes */
+
+ /* at first clear the edge table's old data */
+ for (i = 1; i <= num_gene; i++)
+ {
+ edge_table[i].total_edges = 0;
+ edge_table[i].unused_edges = 0;
+ }
+
+ /* fill edge table with new data */
+
+ edge_total = 0;
+
+ for (index1 = 0; index1 < num_gene; index1++)
+ {
+ /*
+ * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation
+ * maps n back to 1
+ */
+
+ index2 = (index1 + 1) % num_gene;
+
+ /*
+ * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
+ * twice per edge
+ */
+
+ edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
+ gimme_edge(root, tour1[index2], tour1[index1], edge_table);
+
+ edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
+ gimme_edge(root, tour2[index2], tour2[index1], edge_table);
+ }
+
+ /* return average number of edges per index */
+ return ((float) (edge_total * 2) / (float) num_gene);
+}
+
+/* gimme_edge
+ *
+ * registers edge from city1 to city2 in input edge table
+ *
+ * no assumptions about directionality are made;
+ * therefore it is up to the calling routine to
+ * call gimme_edge twice to make a bi-directional edge
+ * between city1 and city2;
+ * uni-directional edges are possible as well (just call gimme_edge
+ * once with the direction from city1 to city2)
+ *
+ * returns 1 if edge was not already registered and was just added;
+ * 0 if edge was already registered and edge_table is unchanged
+ */
+static int
+gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
+{
+ int i;
+ int edges;
+ int city1 = (int) gene1;
+ int city2 = (int) gene2;
+
+
+ /* check whether edge city1->city2 already exists */
+ edges = edge_table[city1].total_edges;
+
+ for (i = 0; i < edges; i++)
+ {
+ if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
+ {
+
+ /* mark shared edges as negative */
+ edge_table[city1].edge_list[i] = 0 - city2;
+
+ return 0;
+ }
+ }
+
+ /* add city1->city2; */
+ edge_table[city1].edge_list[edges] = city2;
+
+ /* increment the number of edges from city1 */
+ edge_table[city1].total_edges++;
+ edge_table[city1].unused_edges++;
+
+ return 1;
+}
+
+/* gimme_tour
+ *
+ * creates a new tour using edges from the edge table.
+ * priority is given to "shared" edges (i.e. edges which
+ * all parent genes possess and are marked as negative
+ * in the edge table.)
+ *
+ */
+int
+gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
+{
+ int i;
+ int edge_failures = 0;
+
+ /* choose int between 1 and num_gene */
+ new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
+
+ for (i = 1; i < num_gene; i++)
+ {
+ /*
+ * as each point is entered into the tour, remove it from the edge
+ * table
+ */
+
+ remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
+
+ /* find destination for the newly entered point */
+
+ if (edge_table[new_gene[i - 1]].unused_edges > 0)
+ new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
+
+ else
+ { /* cope with fault */
+ edge_failures++;
+
+ new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
+ }
+
+ /* mark this node as incorporated */
+ edge_table[(int) new_gene[i - 1]].unused_edges = -1;
+ } /* for (i=1; i<num_gene; i++) */
+
+ return edge_failures;
+}
+
+/* remove_gene
+ *
+ * removes input gene from edge_table.
+ * input edge is used
+ * to identify deletion locations within edge table.
+ *
+ */
+static void
+remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
+{
+ int i,
+ j;
+ int possess_edge;
+ int genes_remaining;
+
+ /*
+ * do for every gene known to have an edge to input gene (i.e. in
+ * edge_list for input edge)
+ */
+
+ for (i = 0; i < edge.unused_edges; i++)
+ {
+ possess_edge = (int) Abs(edge.edge_list[i]);
+ genes_remaining = edge_table[possess_edge].unused_edges;
+
+ /* find the input gene in all edge_lists and delete it */
+ for (j = 0; j < genes_remaining; j++)
+ {
+
+ if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
+ {
+
+ edge_table[possess_edge].unused_edges--;
+
+ edge_table[possess_edge].edge_list[j] =
+ edge_table[possess_edge].edge_list[genes_remaining - 1];
+
+ break;
+ }
+ }
+ }
+}
+
+/* gimme_gene
+ *
+ * priority is given to "shared" edges
+ * (i.e. edges which both genes possess)
+ *
+ */
+static Gene
+gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
+{
+ int i;
+ Gene friend;
+ int minimum_edges;
+ int minimum_count = -1;
+ int rand_decision;
+
+ /*
+ * no point has edges to more than 4 other points thus, this contrived
+ * minimum will be replaced
+ */
+
+ minimum_edges = 5;
+
+ /* consider candidate destination points in edge list */
+
+ for (i = 0; i < edge.unused_edges; i++)
+ {
+ friend = (Gene) edge.edge_list[i];
+
+ /*
+ * give priority to shared edges that are negative; so return 'em
+ */
+
+ /*
+ * negative values are caught here so we need not worry about
+ * converting to absolute values
+ */
+ if (friend < 0)
+ return (Gene) Abs(friend);
+
+
+ /*
+ * give priority to candidates with fewest remaining unused edges;
+ * find out what the minimum number of unused edges is
+ * (minimum_edges); if there is more than one candidate with the
+ * minimum number of unused edges keep count of this number
+ * (minimum_count);
+ */
+
+ /*
+ * The test for minimum_count can probably be removed at some point
+ * but comments should probably indicate exactly why it is guaranteed
+ * that the test will always succeed the first time around. If it can
+ * fail then the code is in error
+ */
+
+
+ if (edge_table[(int) friend].unused_edges < minimum_edges)
+ {
+ minimum_edges = edge_table[(int) friend].unused_edges;
+ minimum_count = 1;
+ }
+ else if (minimum_count == -1)
+ elog(ERROR, "minimum_count not set");
+ else if (edge_table[(int) friend].unused_edges == minimum_edges)
+ minimum_count++;
+ } /* for (i=0; i<edge.unused_edges; i++) */
+
+
+ /* random decision of the possible candidates to use */
+ rand_decision = geqo_randint(root, minimum_count - 1, 0);
+
+
+ for (i = 0; i < edge.unused_edges; i++)
+ {
+ friend = (Gene) edge.edge_list[i];
+
+ /* return the chosen candidate point */
+ if (edge_table[(int) friend].unused_edges == minimum_edges)
+ {
+ minimum_count--;
+
+ if (minimum_count == rand_decision)
+ return friend;
+ }
+ }
+
+ /* ... should never be reached */
+ elog(ERROR, "neither shared nor minimum number nor random edge found");
+ return 0; /* to keep the compiler quiet */
+}
+
+/* edge_failure
+ *
+ * routine for handling edge failure
+ *
+ */
+static Gene
+edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
+{
+ int i;
+ Gene fail_gene = gene[index];
+ int remaining_edges = 0;
+ int four_count = 0;
+ int rand_decision;
+
+
+ /*
+ * how many edges remain? how many gene with four total (initial) edges
+ * remain?
+ */
+
+ for (i = 1; i <= num_gene; i++)
+ {
+ if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
+ {
+ remaining_edges++;
+
+ if (edge_table[i].total_edges == 4)
+ four_count++;
+ }
+ }
+
+ /*
+ * random decision of the gene with remaining edges and whose total_edges
+ * == 4
+ */
+
+ if (four_count != 0)
+ {
+
+ rand_decision = geqo_randint(root, four_count - 1, 0);
+
+ for (i = 1; i <= num_gene; i++)
+ {
+
+ if ((Gene) i != fail_gene &&
+ edge_table[i].unused_edges != -1 &&
+ edge_table[i].total_edges == 4)
+ {
+
+ four_count--;
+
+ if (rand_decision == four_count)
+ return (Gene) i;
+ }
+ }
+
+ elog(LOG, "no edge found via random decision and total_edges == 4");
+ }
+ else if (remaining_edges != 0)
+ {
+ /* random decision of the gene with remaining edges */
+ rand_decision = geqo_randint(root, remaining_edges - 1, 0);
+
+ for (i = 1; i <= num_gene; i++)
+ {
+
+ if ((Gene) i != fail_gene &&
+ edge_table[i].unused_edges != -1)
+ {
+
+ remaining_edges--;
+
+ if (rand_decision == remaining_edges)
+ return i;
+ }
+ }
+
+ elog(LOG, "no edge found via random decision with remaining edges");
+ }
+
+ /*
+ * edge table seems to be empty; this happens sometimes on the last point
+ * due to the fact that the first point is removed from the table even
+ * though only one of its edges has been determined
+ */
+
+ else
+ { /* occurs only at the last point in the tour;
+ * simply look for the point which is not yet
+ * used */
+
+ for (i = 1; i <= num_gene; i++)
+ if (edge_table[i].unused_edges >= 0)
+ return (Gene) i;
+
+ elog(LOG, "no edge found via looking for the last unused point");
+ }
+
+
+ /* ... should never be reached */
+ elog(ERROR, "no edge found");
+ return 0; /* to keep the compiler quiet */
+}
+
+#endif /* defined(ERX) */
diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c
new file mode 100644
index 0000000..004481d
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_eval.c
@@ -0,0 +1,338 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_eval.c
+ * Routines to evaluate query trees
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_eval.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+#include "postgres.h"
+
+#include <float.h>
+#include <limits.h>
+#include <math.h>
+
+#include "optimizer/geqo.h"
+#include "optimizer/joininfo.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "utils/memutils.h"
+
+
+/* A "clump" of already-joined relations within gimme_tree */
+typedef struct
+{
+ RelOptInfo *joinrel; /* joinrel for the set of relations */
+ int size; /* number of input relations in clump */
+} Clump;
+
+static List *merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump,
+ int num_gene, bool force);
+static bool desirable_join(PlannerInfo *root,
+ RelOptInfo *outer_rel, RelOptInfo *inner_rel);
+
+
+/*
+ * geqo_eval
+ *
+ * Returns cost of a query tree as an individual of the population.
+ *
+ * If no legal join order can be extracted from the proposed tour,
+ * returns DBL_MAX.
+ */
+Cost
+geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
+{
+ MemoryContext mycontext;
+ MemoryContext oldcxt;
+ RelOptInfo *joinrel;
+ Cost fitness;
+ int savelength;
+ struct HTAB *savehash;
+
+ /*
+ * Create a private memory context that will hold all temp storage
+ * allocated inside gimme_tree().
+ *
+ * Since geqo_eval() will be called many times, we can't afford to let all
+ * that memory go unreclaimed until end of statement. Note we make the
+ * temp context a child of the planner's normal context, so that it will
+ * be freed even if we abort via ereport(ERROR).
+ */
+ mycontext = AllocSetContextCreate(CurrentMemoryContext,
+ "GEQO",
+ ALLOCSET_DEFAULT_SIZES);
+ oldcxt = MemoryContextSwitchTo(mycontext);
+
+ /*
+ * gimme_tree will add entries to root->join_rel_list, which may or may
+ * not already contain some entries. The newly added entries will be
+ * recycled by the MemoryContextDelete below, so we must ensure that the
+ * list is restored to its former state before exiting. We can do this by
+ * truncating the list to its original length. NOTE this assumes that any
+ * added entries are appended at the end!
+ *
+ * We also must take care not to mess up the outer join_rel_hash, if there
+ * is one. We can do this by just temporarily setting the link to NULL.
+ * (If we are dealing with enough join rels, which we very likely are, a
+ * new hash table will get built and used locally.)
+ *
+ * join_rel_level[] shouldn't be in use, so just Assert it isn't.
+ */
+ savelength = list_length(root->join_rel_list);
+ savehash = root->join_rel_hash;
+ Assert(root->join_rel_level == NULL);
+
+ root->join_rel_hash = NULL;
+
+ /* construct the best path for the given combination of relations */
+ joinrel = gimme_tree(root, tour, num_gene);
+
+ /*
+ * compute fitness, if we found a valid join
+ *
+ * XXX geqo does not currently support optimization for partial result
+ * retrieval, nor do we take any cognizance of possible use of
+ * parameterized paths --- how to fix?
+ */
+ if (joinrel)
+ {
+ Path *best_path = joinrel->cheapest_total_path;
+
+ fitness = best_path->total_cost;
+ }
+ else
+ fitness = DBL_MAX;
+
+ /*
+ * Restore join_rel_list to its former state, and put back original
+ * hashtable if any.
+ */
+ root->join_rel_list = list_truncate(root->join_rel_list,
+ savelength);
+ root->join_rel_hash = savehash;
+
+ /* release all the memory acquired within gimme_tree */
+ MemoryContextSwitchTo(oldcxt);
+ MemoryContextDelete(mycontext);
+
+ return fitness;
+}
+
+/*
+ * gimme_tree
+ * Form planner estimates for a join tree constructed in the specified
+ * order.
+ *
+ * 'tour' is the proposed join order, of length 'num_gene'
+ *
+ * Returns a new join relation whose cheapest path is the best plan for
+ * this join order. NB: will return NULL if join order is invalid and
+ * we can't modify it into a valid order.
+ *
+ * The original implementation of this routine always joined in the specified
+ * order, and so could only build left-sided plans (and right-sided and
+ * mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
+ * It could never produce a "bushy" plan. This had a couple of big problems,
+ * of which the worst was that there are situations involving join order
+ * restrictions where the only valid plans are bushy.
+ *
+ * The present implementation takes the given tour as a guideline, but
+ * postpones joins that are illegal or seem unsuitable according to some
+ * heuristic rules. This allows correct bushy plans to be generated at need,
+ * and as a nice side-effect it seems to materially improve the quality of the
+ * generated plans. Note however that since it's just a heuristic, it can
+ * still fail in some cases. (In particular, we might clump together
+ * relations that actually mustn't be joined yet due to LATERAL restrictions;
+ * since there's no provision for un-clumping, this must lead to failure.)
+ */
+RelOptInfo *
+gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
+{
+ GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
+ List *clumps;
+ int rel_count;
+
+ /*
+ * Sometimes, a relation can't yet be joined to others due to heuristics
+ * or actual semantic restrictions. We maintain a list of "clumps" of
+ * successfully joined relations, with larger clumps at the front. Each
+ * new relation from the tour is added to the first clump it can be joined
+ * to; if there is none then it becomes a new clump of its own. When we
+ * enlarge an existing clump we check to see if it can now be merged with
+ * any other clumps. After the tour is all scanned, we forget about the
+ * heuristics and try to forcibly join any remaining clumps. If we are
+ * unable to merge all the clumps into one, fail.
+ */
+ clumps = NIL;
+
+ for (rel_count = 0; rel_count < num_gene; rel_count++)
+ {
+ int cur_rel_index;
+ RelOptInfo *cur_rel;
+ Clump *cur_clump;
+
+ /* Get the next input relation */
+ cur_rel_index = (int) tour[rel_count];
+ cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
+ cur_rel_index - 1);
+
+ /* Make it into a single-rel clump */
+ cur_clump = (Clump *) palloc(sizeof(Clump));
+ cur_clump->joinrel = cur_rel;
+ cur_clump->size = 1;
+
+ /* Merge it into the clumps list, using only desirable joins */
+ clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
+ }
+
+ if (list_length(clumps) > 1)
+ {
+ /* Force-join the remaining clumps in some legal order */
+ List *fclumps;
+ ListCell *lc;
+
+ fclumps = NIL;
+ foreach(lc, clumps)
+ {
+ Clump *clump = (Clump *) lfirst(lc);
+
+ fclumps = merge_clump(root, fclumps, clump, num_gene, true);
+ }
+ clumps = fclumps;
+ }
+
+ /* Did we succeed in forming a single join relation? */
+ if (list_length(clumps) != 1)
+ return NULL;
+
+ return ((Clump *) linitial(clumps))->joinrel;
+}
+
+/*
+ * Merge a "clump" into the list of existing clumps for gimme_tree.
+ *
+ * We try to merge the clump into some existing clump, and repeat if
+ * successful. When no more merging is possible, insert the clump
+ * into the list, preserving the list ordering rule (namely, that
+ * clumps of larger size appear earlier).
+ *
+ * If force is true, merge anywhere a join is legal, even if it causes
+ * a cartesian join to be performed. When force is false, do only
+ * "desirable" joins.
+ */
+static List *
+merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
+ bool force)
+{
+ ListCell *lc;
+ int pos;
+
+ /* Look for a clump that new_clump can join to */
+ foreach(lc, clumps)
+ {
+ Clump *old_clump = (Clump *) lfirst(lc);
+
+ if (force ||
+ desirable_join(root, old_clump->joinrel, new_clump->joinrel))
+ {
+ RelOptInfo *joinrel;
+
+ /*
+ * Construct a RelOptInfo representing the join of these two input
+ * relations. Note that we expect the joinrel not to exist in
+ * root->join_rel_list yet, and so the paths constructed for it
+ * will only include the ones we want.
+ */
+ joinrel = make_join_rel(root,
+ old_clump->joinrel,
+ new_clump->joinrel);
+
+ /* Keep searching if join order is not valid */
+ if (joinrel)
+ {
+ /* Create paths for partitionwise joins. */
+ generate_partitionwise_join_paths(root, joinrel);
+
+ /*
+ * Except for the topmost scan/join rel, consider gathering
+ * partial paths. We'll do the same for the topmost scan/join
+ * rel once we know the final targetlist (see
+ * grouping_planner).
+ */
+ if (!bms_equal(joinrel->relids, root->all_baserels))
+ generate_useful_gather_paths(root, joinrel, false);
+
+ /* Find and save the cheapest paths for this joinrel */
+ set_cheapest(joinrel);
+
+ /* Absorb new clump into old */
+ old_clump->joinrel = joinrel;
+ old_clump->size += new_clump->size;
+ pfree(new_clump);
+
+ /* Remove old_clump from list */
+ clumps = foreach_delete_current(clumps, lc);
+
+ /*
+ * Recursively try to merge the enlarged old_clump with
+ * others. When no further merge is possible, we'll reinsert
+ * it into the list.
+ */
+ return merge_clump(root, clumps, old_clump, num_gene, force);
+ }
+ }
+ }
+
+ /*
+ * No merging is possible, so add new_clump as an independent clump, in
+ * proper order according to size. We can be fast for the common case
+ * where it has size 1 --- it should always go at the end.
+ */
+ if (clumps == NIL || new_clump->size == 1)
+ return lappend(clumps, new_clump);
+
+ /* Else search for the place to insert it */
+ for (pos = 0; pos < list_length(clumps); pos++)
+ {
+ Clump *old_clump = (Clump *) list_nth(clumps, pos);
+
+ if (new_clump->size > old_clump->size)
+ break; /* new_clump belongs before old_clump */
+ }
+ clumps = list_insert_nth(clumps, pos, new_clump);
+
+ return clumps;
+}
+
+/*
+ * Heuristics for gimme_tree: do we want to join these two relations?
+ */
+static bool
+desirable_join(PlannerInfo *root,
+ RelOptInfo *outer_rel, RelOptInfo *inner_rel)
+{
+ /*
+ * Join if there is an applicable join clause, or if there is a join order
+ * restriction forcing these rels to be joined.
+ */
+ if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
+ have_join_order_restriction(root, outer_rel, inner_rel))
+ return true;
+
+ /* Otherwise postpone the join till later. */
+ return false;
+}
diff --git a/src/backend/optimizer/geqo/geqo_main.c b/src/backend/optimizer/geqo/geqo_main.c
new file mode 100644
index 0000000..68ed743
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_main.c
@@ -0,0 +1,353 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_main.c
+ * solution to the query optimization problem
+ * by means of a Genetic Algorithm (GA)
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_main.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
+
+#include "postgres.h"
+
+#include <math.h>
+
+#include "optimizer/geqo_misc.h"
+#include "optimizer/geqo_mutation.h"
+#include "optimizer/geqo_pool.h"
+#include "optimizer/geqo_random.h"
+#include "optimizer/geqo_selection.h"
+
+
+/*
+ * Configuration options
+ */
+int Geqo_effort;
+int Geqo_pool_size;
+int Geqo_generations;
+double Geqo_selection_bias;
+double Geqo_seed;
+
+
+static int gimme_pool_size(int nr_rel);
+static int gimme_number_generations(int pool_size);
+
+/* complain if no recombination mechanism is #define'd */
+#if !defined(ERX) && \
+ !defined(PMX) && \
+ !defined(CX) && \
+ !defined(PX) && \
+ !defined(OX1) && \
+ !defined(OX2)
+#error "must choose one GEQO recombination mechanism in geqo.h"
+#endif
+
+
+/*
+ * geqo
+ * solution of the query optimization problem
+ * similar to a constrained Traveling Salesman Problem (TSP)
+ */
+
+RelOptInfo *
+geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
+{
+ GeqoPrivateData private;
+ int generation;
+ Chromosome *momma;
+ Chromosome *daddy;
+ Chromosome *kid;
+ Pool *pool;
+ int pool_size,
+ number_generations;
+
+#ifdef GEQO_DEBUG
+ int status_interval;
+#endif
+ Gene *best_tour;
+ RelOptInfo *best_rel;
+
+#if defined(ERX)
+ Edge *edge_table; /* list of edges */
+ int edge_failures = 0;
+#endif
+#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
+ City *city_table; /* list of cities */
+#endif
+#if defined(CX)
+ int cycle_diffs = 0;
+ int mutations = 0;
+#endif
+
+/* set up private information */
+ root->join_search_private = (void *) &private;
+ private.initial_rels = initial_rels;
+
+/* initialize private number generator */
+ geqo_set_seed(root, Geqo_seed);
+
+/* set GA parameters */
+ pool_size = gimme_pool_size(number_of_rels);
+ number_generations = gimme_number_generations(pool_size);
+#ifdef GEQO_DEBUG
+ status_interval = 10;
+#endif
+
+/* allocate genetic pool memory */
+ pool = alloc_pool(root, pool_size, number_of_rels);
+
+/* random initialization of the pool */
+ random_init_pool(root, pool);
+
+/* sort the pool according to cheapest path as fitness */
+ sort_pool(root, pool); /* we have to do it only one time, since all
+ * kids replace the worst individuals in
+ * future (-> geqo_pool.c:spread_chromo ) */
+
+#ifdef GEQO_DEBUG
+ elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
+ pool_size,
+ pool->data[0].worth,
+ pool->data[pool_size - 1].worth);
+#endif
+
+/* allocate chromosome momma and daddy memory */
+ momma = alloc_chromo(root, pool->string_length);
+ daddy = alloc_chromo(root, pool->string_length);
+
+#if defined (ERX)
+#ifdef GEQO_DEBUG
+ elog(DEBUG2, "using edge recombination crossover [ERX]");
+#endif
+/* allocate edge table memory */
+ edge_table = alloc_edge_table(root, pool->string_length);
+#elif defined(PMX)
+#ifdef GEQO_DEBUG
+ elog(DEBUG2, "using partially matched crossover [PMX]");
+#endif
+/* allocate chromosome kid memory */
+ kid = alloc_chromo(root, pool->string_length);
+#elif defined(CX)
+#ifdef GEQO_DEBUG
+ elog(DEBUG2, "using cycle crossover [CX]");
+#endif
+/* allocate city table memory */
+ kid = alloc_chromo(root, pool->string_length);
+ city_table = alloc_city_table(root, pool->string_length);
+#elif defined(PX)
+#ifdef GEQO_DEBUG
+ elog(DEBUG2, "using position crossover [PX]");
+#endif
+/* allocate city table memory */
+ kid = alloc_chromo(root, pool->string_length);
+ city_table = alloc_city_table(root, pool->string_length);
+#elif defined(OX1)
+#ifdef GEQO_DEBUG
+ elog(DEBUG2, "using order crossover [OX1]");
+#endif
+/* allocate city table memory */
+ kid = alloc_chromo(root, pool->string_length);
+ city_table = alloc_city_table(root, pool->string_length);
+#elif defined(OX2)
+#ifdef GEQO_DEBUG
+ elog(DEBUG2, "using order crossover [OX2]");
+#endif
+/* allocate city table memory */
+ kid = alloc_chromo(root, pool->string_length);
+ city_table = alloc_city_table(root, pool->string_length);
+#endif
+
+
+/* my pain main part: */
+/* iterative optimization */
+
+ for (generation = 0; generation < number_generations; generation++)
+ {
+ /* SELECTION: using linear bias function */
+ geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);
+
+#if defined (ERX)
+ /* EDGE RECOMBINATION CROSSOVER */
+ gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);
+
+ kid = momma;
+
+ /* are there any edge failures ? */
+ edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
+#elif defined(PMX)
+ /* PARTIALLY MATCHED CROSSOVER */
+ pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
+#elif defined(CX)
+ /* CYCLE CROSSOVER */
+ cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
+ /* mutate the child */
+ if (cycle_diffs == 0)
+ {
+ mutations++;
+ geqo_mutation(root, kid->string, pool->string_length);
+ }
+#elif defined(PX)
+ /* POSITION CROSSOVER */
+ px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
+#elif defined(OX1)
+ /* ORDER CROSSOVER */
+ ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
+#elif defined(OX2)
+ /* ORDER CROSSOVER */
+ ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
+#endif
+
+
+ /* EVALUATE FITNESS */
+ kid->worth = geqo_eval(root, kid->string, pool->string_length);
+
+ /* push the kid into the wilderness of life according to its worth */
+ spread_chromo(root, kid, pool);
+
+
+#ifdef GEQO_DEBUG
+ if (status_interval && !(generation % status_interval))
+ print_gen(stdout, pool, generation);
+#endif
+
+ }
+
+
+#if defined(ERX)
+#if defined(GEQO_DEBUG)
+ if (edge_failures != 0)
+ elog(LOG, "[GEQO] failures: %d, average: %d",
+ edge_failures, (int) number_generations / edge_failures);
+ else
+ elog(LOG, "[GEQO] no edge failures detected");
+#else
+ /* suppress variable-set-but-not-used warnings from some compilers */
+ (void) edge_failures;
+#endif
+#endif
+
+#if defined(CX) && defined(GEQO_DEBUG)
+ if (mutations != 0)
+ elog(LOG, "[GEQO] mutations: %d, generations: %d",
+ mutations, number_generations);
+ else
+ elog(LOG, "[GEQO] no mutations processed");
+#endif
+
+#ifdef GEQO_DEBUG
+ print_pool(stdout, pool, 0, pool_size - 1);
+#endif
+
+#ifdef GEQO_DEBUG
+ elog(DEBUG1, "GEQO best is %.2f after %d generations",
+ pool->data[0].worth, number_generations);
+#endif
+
+
+ /*
+ * got the cheapest query tree processed by geqo; first element of the
+ * population indicates the best query tree
+ */
+ best_tour = (Gene *) pool->data[0].string;
+
+ best_rel = gimme_tree(root, best_tour, pool->string_length);
+
+ if (best_rel == NULL)
+ elog(ERROR, "geqo failed to make a valid plan");
+
+ /* DBG: show the query plan */
+#ifdef NOT_USED
+ print_plan(best_plan, root);
+#endif
+
+ /* ... free memory stuff */
+ free_chromo(root, momma);
+ free_chromo(root, daddy);
+
+#if defined (ERX)
+ free_edge_table(root, edge_table);
+#elif defined(PMX)
+ free_chromo(root, kid);
+#elif defined(CX)
+ free_chromo(root, kid);
+ free_city_table(root, city_table);
+#elif defined(PX)
+ free_chromo(root, kid);
+ free_city_table(root, city_table);
+#elif defined(OX1)
+ free_chromo(root, kid);
+ free_city_table(root, city_table);
+#elif defined(OX2)
+ free_chromo(root, kid);
+ free_city_table(root, city_table);
+#endif
+
+ free_pool(root, pool);
+
+ /* ... clear root pointer to our private storage */
+ root->join_search_private = NULL;
+
+ return best_rel;
+}
+
+
+/*
+ * Return either configured pool size or a good default
+ *
+ * The default is based on query size (no. of relations) = 2^(QS+1),
+ * but constrained to a range based on the effort value.
+ */
+static int
+gimme_pool_size(int nr_rel)
+{
+ double size;
+ int minsize;
+ int maxsize;
+
+ /* Legal pool size *must* be at least 2, so ignore attempt to select 1 */
+ if (Geqo_pool_size >= 2)
+ return Geqo_pool_size;
+
+ size = pow(2.0, nr_rel + 1.0);
+
+ maxsize = 50 * Geqo_effort; /* 50 to 500 individuals */
+ if (size > maxsize)
+ return maxsize;
+
+ minsize = 10 * Geqo_effort; /* 10 to 100 individuals */
+ if (size < minsize)
+ return minsize;
+
+ return (int) ceil(size);
+}
+
+
+/*
+ * Return either configured number of generations or a good default
+ *
+ * The default is the same as the pool size, which allows us to be
+ * sure that less-fit individuals get pushed out of the breeding
+ * population before the run finishes.
+ */
+static int
+gimme_number_generations(int pool_size)
+{
+ if (Geqo_generations > 0)
+ return Geqo_generations;
+
+ return pool_size;
+}
diff --git a/src/backend/optimizer/geqo/geqo_misc.c b/src/backend/optimizer/geqo/geqo_misc.c
new file mode 100644
index 0000000..890ac36
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_misc.c
@@ -0,0 +1,132 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_misc.c
+ * misc. printout and debug stuff
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_misc.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+#include "postgres.h"
+
+#include "optimizer/geqo_misc.h"
+
+
+#ifdef GEQO_DEBUG
+
+
+/*
+ * avg_pool
+ */
+static double
+avg_pool(Pool *pool)
+{
+ int i;
+ double cumulative = 0.0;
+
+ if (pool->size <= 0)
+ elog(ERROR, "pool_size is zero");
+
+ /*
+ * Since the pool may contain multiple occurrences of DBL_MAX, divide by
+ * pool->size before summing, not after, to avoid overflow. This loses a
+ * little in speed and accuracy, but this routine is only used for debug
+ * printouts, so we don't care that much.
+ */
+ for (i = 0; i < pool->size; i++)
+ cumulative += pool->data[i].worth / pool->size;
+
+ return cumulative;
+}
+
+/* print_pool
+ */
+void
+print_pool(FILE *fp, Pool *pool, int start, int stop)
+{
+ int i,
+ j;
+
+ /* be extra careful that start and stop are valid inputs */
+
+ if (start < 0)
+ start = 0;
+ if (stop > pool->size)
+ stop = pool->size;
+
+ if (start + stop > pool->size)
+ {
+ start = 0;
+ stop = pool->size;
+ }
+
+ for (i = start; i < stop; i++)
+ {
+ fprintf(fp, "%d)\t", i);
+ for (j = 0; j < pool->string_length; j++)
+ fprintf(fp, "%d ", pool->data[i].string[j]);
+ fprintf(fp, "%g\n", pool->data[i].worth);
+ }
+
+ fflush(fp);
+}
+
+/* print_gen
+ *
+ * printout for chromosome: best, worst, mean, average
+ */
+void
+print_gen(FILE *fp, Pool *pool, int generation)
+{
+ int lowest;
+
+ /* Get index to lowest ranking gene in population. */
+ /* Use 2nd to last since last is buffer. */
+ lowest = pool->size > 1 ? pool->size - 2 : 0;
+
+ fprintf(fp,
+ "%5d | Best: %g Worst: %g Mean: %g Avg: %g\n",
+ generation,
+ pool->data[0].worth,
+ pool->data[lowest].worth,
+ pool->data[pool->size / 2].worth,
+ avg_pool(pool));
+
+ fflush(fp);
+}
+
+
+void
+print_edge_table(FILE *fp, Edge *edge_table, int num_gene)
+{
+ int i,
+ j;
+
+ fprintf(fp, "\nEDGE TABLE\n");
+
+ for (i = 1; i <= num_gene; i++)
+ {
+ fprintf(fp, "%d :", i);
+ for (j = 0; j < edge_table[i].unused_edges; j++)
+ fprintf(fp, " %d", edge_table[i].edge_list[j]);
+ fprintf(fp, "\n");
+ }
+
+ fprintf(fp, "\n");
+
+ fflush(fp);
+}
+
+#endif /* GEQO_DEBUG */
diff --git a/src/backend/optimizer/geqo/geqo_mutation.c b/src/backend/optimizer/geqo/geqo_mutation.c
new file mode 100644
index 0000000..2af0295
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_mutation.c
@@ -0,0 +1,66 @@
+/*------------------------------------------------------------------------
+*
+* geqo_mutation.c
+*
+* TSP mutation routines
+*
+* src/backend/optimizer/geqo/geqo_mutation.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 Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_mutation.h"
+#include "optimizer/geqo_random.h"
+
+#if defined(CX) /* currently used only in CX mode */
+
+void
+geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene)
+{
+ int swap1;
+ int swap2;
+ int num_swaps = geqo_randint(root, num_gene / 3, 0);
+ Gene temp;
+
+
+ while (num_swaps > 0)
+ {
+ swap1 = geqo_randint(root, num_gene - 1, 0);
+ swap2 = geqo_randint(root, num_gene - 1, 0);
+
+ while (swap1 == swap2)
+ swap2 = geqo_randint(root, num_gene - 1, 0);
+
+ temp = tour[swap1];
+ tour[swap1] = tour[swap2];
+ tour[swap2] = temp;
+
+
+ num_swaps -= 1;
+ }
+}
+
+#endif /* defined(CX) */
diff --git a/src/backend/optimizer/geqo/geqo_ox1.c b/src/backend/optimizer/geqo/geqo_ox1.c
new file mode 100644
index 0000000..ede7abb
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_ox1.c
@@ -0,0 +1,94 @@
+/*------------------------------------------------------------------------
+*
+* geqo_ox1.c
+*
+* order crossover [OX] routines;
+* OX1 operator according to Davis
+* (Proc Int'l Joint Conf on AI)
+*
+* src/backend/optimizer/geqo/geqo_ox1.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the ox algorithm is adopted from Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(OX1)
+
+/* ox1
+ *
+ * position crossover
+ */
+void
+ox1(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
+ City * city_table)
+{
+ int left,
+ right,
+ k,
+ p,
+ temp;
+
+ /* initialize city table */
+ for (k = 1; k <= num_gene; k++)
+ city_table[k].used = 0;
+
+ /* select portion to copy from tour1 */
+ left = geqo_randint(root, num_gene - 1, 0);
+ right = geqo_randint(root, num_gene - 1, 0);
+
+ if (left > right)
+ {
+ temp = left;
+ left = right;
+ right = temp;
+ }
+
+ /* copy portion from tour1 to offspring */
+ for (k = left; k <= right; k++)
+ {
+ offspring[k] = tour1[k];
+ city_table[(int) tour1[k]].used = 1;
+ }
+
+ k = (right + 1) % num_gene; /* index into offspring */
+ p = k; /* index into tour2 */
+
+ /* copy stuff from tour2 to offspring */
+ while (k != left)
+ {
+ if (!city_table[(int) tour2[p]].used)
+ {
+ offspring[k] = tour2[p];
+ k = (k + 1) % num_gene;
+ city_table[(int) tour2[p]].used = 1;
+ }
+ p = (p + 1) % num_gene; /* increment tour2-index */
+ }
+}
+
+#endif /* defined(OX1) */
diff --git a/src/backend/optimizer/geqo/geqo_ox2.c b/src/backend/optimizer/geqo/geqo_ox2.c
new file mode 100644
index 0000000..080dbc0
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_ox2.c
@@ -0,0 +1,111 @@
+/*------------------------------------------------------------------------
+*
+* geqo_ox2.c
+*
+* order crossover [OX] routines;
+* OX2 operator according to Syswerda
+* (The Genetic Algorithms Handbook, ed L Davis)
+*
+* src/backend/optimizer/geqo/geqo_ox2.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the ox algorithm is adopted from Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(OX2)
+
+/* ox2
+ *
+ * position crossover
+ */
+void
+ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City * city_table)
+{
+ int k,
+ j,
+ count,
+ pos,
+ select,
+ num_positions;
+
+ /* initialize city table */
+ for (k = 1; k <= num_gene; k++)
+ {
+ city_table[k].used = 0;
+ city_table[k - 1].select_list = -1;
+ }
+
+ /* determine the number of positions to be inherited from tour1 */
+ num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
+
+ /* make a list of selected cities */
+ for (k = 0; k < num_positions; k++)
+ {
+ pos = geqo_randint(root, num_gene - 1, 0);
+ city_table[pos].select_list = (int) tour1[pos];
+ city_table[(int) tour1[pos]].used = 1; /* mark used */
+ }
+
+
+ count = 0;
+ k = 0;
+
+ /* consolidate the select list to adjacent positions */
+ while (count < num_positions)
+ {
+ if (city_table[k].select_list == -1)
+ {
+ j = k + 1;
+ while ((city_table[j].select_list == -1) && (j < num_gene))
+ j++;
+
+ city_table[k].select_list = city_table[j].select_list;
+ city_table[j].select_list = -1;
+ count++;
+ }
+ else
+ count++;
+ k++;
+ }
+
+ select = 0;
+
+ for (k = 0; k < num_gene; k++)
+ {
+ if (city_table[(int) tour2[k]].used)
+ {
+ offspring[k] = (Gene) city_table[select].select_list;
+ select++; /* next city in the select list */
+ }
+ else
+ /* city isn't used yet, so inherit from tour2 */
+ offspring[k] = tour2[k];
+ }
+}
+
+#endif /* defined(OX2) */
diff --git a/src/backend/optimizer/geqo/geqo_pmx.c b/src/backend/optimizer/geqo/geqo_pmx.c
new file mode 100644
index 0000000..e44fd0b
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_pmx.c
@@ -0,0 +1,218 @@
+/*------------------------------------------------------------------------
+*
+* geqo_pmx.c
+*
+* partially matched crossover [PMX] routines;
+* PMX operator according to Goldberg & Lingle
+* (Proc Int'l Conf on GA's)
+*
+* src/backend/optimizer/geqo/geqo_pmx.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the pmx algorithm is adopted from Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(PMX)
+
+/* pmx
+ *
+ * partially matched crossover
+ */
+void
+pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
+{
+ int *failed = (int *) palloc((num_gene + 1) * sizeof(int));
+ int *from = (int *) palloc((num_gene + 1) * sizeof(int));
+ int *indx = (int *) palloc((num_gene + 1) * sizeof(int));
+ int *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
+
+ int left,
+ right,
+ temp,
+ i,
+ j,
+ k;
+ int mx_fail,
+ found,
+ mx_hold;
+
+
+/* no mutation so start up the pmx replacement algorithm */
+/* initialize failed[], from[], check_list[] */
+ for (k = 0; k < num_gene; k++)
+ {
+ failed[k] = -1;
+ from[k] = -1;
+ check_list[k + 1] = 0;
+ }
+
+/* locate crossover points */
+ left = geqo_randint(root, num_gene - 1, 0);
+ right = geqo_randint(root, num_gene - 1, 0);
+
+ if (left > right)
+ {
+ temp = left;
+ left = right;
+ right = temp;
+ }
+
+
+/* copy tour2 into offspring */
+ for (k = 0; k < num_gene; k++)
+ {
+ offspring[k] = tour2[k];
+ from[k] = DAD;
+ check_list[tour2[k]]++;
+ }
+
+/* copy tour1 into offspring */
+ for (k = left; k <= right; k++)
+ {
+ check_list[offspring[k]]--;
+ offspring[k] = tour1[k];
+ from[k] = MOM;
+ check_list[tour1[k]]++;
+ }
+
+
+/* pmx main part */
+
+ mx_fail = 0;
+
+/* STEP 1 */
+
+ for (k = left; k <= right; k++)
+ { /* for all elements in the tour1-2 */
+
+ if (tour1[k] == tour2[k])
+ found = 1; /* find match in tour2 */
+
+ else
+ {
+ found = 0; /* substitute elements */
+
+ j = 0;
+ while (!(found) && (j < num_gene))
+ {
+ if ((offspring[j] == tour1[k]) && (from[j] == DAD))
+ {
+
+ check_list[offspring[j]]--;
+ offspring[j] = tour2[k];
+ found = 1;
+ check_list[tour2[k]]++;
+ }
+
+ j++;
+ }
+ }
+
+ if (!(found))
+ { /* failed to replace gene */
+ failed[mx_fail] = (int) tour1[k];
+ indx[mx_fail] = k;
+ mx_fail++;
+ }
+ } /* ... for */
+
+
+/* STEP 2 */
+
+ /* see if any genes could not be replaced */
+ if (mx_fail > 0)
+ {
+ mx_hold = mx_fail;
+
+ for (k = 0; k < mx_hold; k++)
+ {
+ found = 0;
+
+ j = 0;
+ while (!(found) && (j < num_gene))
+ {
+
+ if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
+ {
+ check_list[offspring[j]]--;
+ offspring[j] = tour2[indx[k]];
+ check_list[tour2[indx[k]]]++;
+
+ found = 1;
+ failed[k] = -1;
+ mx_fail--;
+ }
+
+ j++;
+ }
+ } /* ... for */
+ } /* ... if */
+
+
+/* STEP 3 */
+
+ for (k = 1; k <= num_gene; k++)
+ {
+
+ if (check_list[k] > 1)
+ {
+ i = 0;
+
+ while (i < num_gene)
+ {
+ if ((offspring[i] == (Gene) k) && (from[i] == DAD))
+ {
+ j = 1;
+
+ while (j <= num_gene)
+ {
+ if (check_list[j] == 0)
+ {
+ offspring[i] = (Gene) j;
+ check_list[k]--;
+ check_list[j]++;
+ i = num_gene + 1;
+ j = i;
+ }
+
+ j++;
+ }
+ } /* ... if */
+
+ i++;
+ } /* end while */
+ }
+ } /* ... for */
+
+ pfree(failed);
+ pfree(from);
+ pfree(indx);
+ pfree(check_list);
+}
+
+#endif /* defined(PMX) */
diff --git a/src/backend/optimizer/geqo/geqo_pool.c b/src/backend/optimizer/geqo/geqo_pool.c
new file mode 100644
index 0000000..0dfef1f
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_pool.c
@@ -0,0 +1,265 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_pool.c
+ * Genetic Algorithm (GA) pool stuff
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_pool.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
+
+#include "postgres.h"
+
+#include <float.h>
+#include <limits.h>
+#include <math.h>
+
+#include "optimizer/geqo_copy.h"
+#include "optimizer/geqo_pool.h"
+#include "optimizer/geqo_recombination.h"
+
+
+static int compare(const void *arg1, const void *arg2);
+
+/*
+ * alloc_pool
+ * allocates memory for GA pool
+ */
+Pool *
+alloc_pool(PlannerInfo *root, int pool_size, int string_length)
+{
+ Pool *new_pool;
+ Chromosome *chromo;
+ int i;
+
+ /* pool */
+ new_pool = (Pool *) palloc(sizeof(Pool));
+ new_pool->size = (int) pool_size;
+ new_pool->string_length = (int) string_length;
+
+ /* all chromosome */
+ new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
+
+ /* all gene */
+ chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
+ for (i = 0; i < pool_size; i++)
+ chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
+
+ return new_pool;
+}
+
+/*
+ * free_pool
+ * deallocates memory for GA pool
+ */
+void
+free_pool(PlannerInfo *root, Pool *pool)
+{
+ Chromosome *chromo;
+ int i;
+
+ /* all gene */
+ chromo = (Chromosome *) pool->data; /* vector of all chromos */
+ for (i = 0; i < pool->size; i++)
+ pfree(chromo[i].string);
+
+ /* all chromosome */
+ pfree(pool->data);
+
+ /* pool */
+ pfree(pool);
+}
+
+/*
+ * random_init_pool
+ * initialize genetic pool
+ */
+void
+random_init_pool(PlannerInfo *root, Pool *pool)
+{
+ Chromosome *chromo = (Chromosome *) pool->data;
+ int i;
+ int bad = 0;
+
+ /*
+ * We immediately discard any invalid individuals (those that geqo_eval
+ * returns DBL_MAX for), thereby not wasting pool space on them.
+ *
+ * If we fail to make any valid individuals after 10000 tries, give up;
+ * this probably means something is broken, and we shouldn't just let
+ * ourselves get stuck in an infinite loop.
+ */
+ i = 0;
+ while (i < pool->size)
+ {
+ init_tour(root, chromo[i].string, pool->string_length);
+ pool->data[i].worth = geqo_eval(root, chromo[i].string,
+ pool->string_length);
+ if (pool->data[i].worth < DBL_MAX)
+ i++;
+ else
+ {
+ bad++;
+ if (i == 0 && bad >= 10000)
+ elog(ERROR, "geqo failed to make a valid plan");
+ }
+ }
+
+#ifdef GEQO_DEBUG
+ if (bad > 0)
+ elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
+ bad, pool->size);
+#endif
+}
+
+/*
+ * sort_pool
+ * sorts input pool according to worth, from smallest to largest
+ *
+ * maybe you have to change compare() for different ordering ...
+ */
+void
+sort_pool(PlannerInfo *root, Pool *pool)
+{
+ qsort(pool->data, pool->size, sizeof(Chromosome), compare);
+}
+
+/*
+ * compare
+ * qsort comparison function for sort_pool
+ */
+static int
+compare(const void *arg1, const void *arg2)
+{
+ const Chromosome *chromo1 = (const Chromosome *) arg1;
+ const Chromosome *chromo2 = (const Chromosome *) arg2;
+
+ if (chromo1->worth == chromo2->worth)
+ return 0;
+ else if (chromo1->worth > chromo2->worth)
+ return 1;
+ else
+ return -1;
+}
+
+/* alloc_chromo
+ * allocates a chromosome and string space
+ */
+Chromosome *
+alloc_chromo(PlannerInfo *root, int string_length)
+{
+ Chromosome *chromo;
+
+ chromo = (Chromosome *) palloc(sizeof(Chromosome));
+ chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
+
+ return chromo;
+}
+
+/* free_chromo
+ * deallocates a chromosome and string space
+ */
+void
+free_chromo(PlannerInfo *root, Chromosome *chromo)
+{
+ pfree(chromo->string);
+ pfree(chromo);
+}
+
+/* spread_chromo
+ * inserts a new chromosome into the pool, displacing worst gene in pool
+ * assumes best->worst = smallest->largest
+ */
+void
+spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
+{
+ int top,
+ mid,
+ bot;
+ int i,
+ index;
+ Chromosome swap_chromo,
+ tmp_chromo;
+
+ /* new chromo is so bad we can't use it */
+ if (chromo->worth > pool->data[pool->size - 1].worth)
+ return;
+
+ /* do a binary search to find the index of the new chromo */
+
+ top = 0;
+ mid = pool->size / 2;
+ bot = pool->size - 1;
+ index = -1;
+
+ while (index == -1)
+ {
+ /* these 4 cases find a new location */
+
+ if (chromo->worth <= pool->data[top].worth)
+ index = top;
+ else if (chromo->worth == pool->data[mid].worth)
+ index = mid;
+ else if (chromo->worth == pool->data[bot].worth)
+ index = bot;
+ else if (bot - top <= 1)
+ index = bot;
+
+
+ /*
+ * these 2 cases move the search indices since a new location has not
+ * yet been found.
+ */
+
+ else if (chromo->worth < pool->data[mid].worth)
+ {
+ bot = mid;
+ mid = top + ((bot - top) / 2);
+ }
+ else
+ { /* (chromo->worth > pool->data[mid].worth) */
+ top = mid;
+ mid = top + ((bot - top) / 2);
+ }
+ } /* ... while */
+
+ /* now we have index for chromo */
+
+ /*
+ * move every gene from index on down one position to make room for chromo
+ */
+
+ /*
+ * copy new gene into pool storage; always replace worst gene in pool
+ */
+
+ geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
+
+ swap_chromo.string = pool->data[pool->size - 1].string;
+ swap_chromo.worth = pool->data[pool->size - 1].worth;
+
+ for (i = index; i < pool->size; i++)
+ {
+ tmp_chromo.string = pool->data[i].string;
+ tmp_chromo.worth = pool->data[i].worth;
+
+ pool->data[i].string = swap_chromo.string;
+ pool->data[i].worth = swap_chromo.worth;
+
+ swap_chromo.string = tmp_chromo.string;
+ swap_chromo.worth = tmp_chromo.worth;
+ }
+}
diff --git a/src/backend/optimizer/geqo/geqo_px.c b/src/backend/optimizer/geqo/geqo_px.c
new file mode 100644
index 0000000..914296b
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_px.c
@@ -0,0 +1,107 @@
+/*------------------------------------------------------------------------
+*
+* geqo_px.c
+*
+* position crossover [PX] routines;
+* PX operator according to Syswerda
+* (The Genetic Algorithms Handbook, L Davis, ed)
+*
+* src/backend/optimizer/geqo/geqo_px.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the px algorithm is adopted from Genitor : */
+/*************************************************************/
+/* */
+/* 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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(PX)
+
+/* px
+ *
+ * position crossover
+ */
+void
+px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
+ City * city_table)
+{
+ int num_positions;
+ int i,
+ pos,
+ tour2_index,
+ offspring_index;
+
+ /* initialize city table */
+ for (i = 1; i <= num_gene; i++)
+ city_table[i].used = 0;
+
+ /* choose random positions that will be inherited directly from parent */
+ num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
+
+ /* choose random position */
+ for (i = 0; i < num_positions; i++)
+ {
+ pos = geqo_randint(root, num_gene - 1, 0);
+
+ offspring[pos] = tour1[pos]; /* transfer cities to child */
+ city_table[(int) tour1[pos]].used = 1; /* mark city used */
+ }
+
+ tour2_index = 0;
+ offspring_index = 0;
+
+
+ /* px main part */
+
+ while (offspring_index < num_gene)
+ {
+
+ /* next position in offspring filled */
+ if (!city_table[(int) tour1[offspring_index]].used)
+ {
+
+ /* next city in tour1 not used */
+ if (!city_table[(int) tour2[tour2_index]].used)
+ {
+
+ /* inherit from tour1 */
+ offspring[offspring_index] = tour2[tour2_index];
+
+ tour2_index++;
+ offspring_index++;
+ }
+ else
+ { /* next city in tour2 has been used */
+ tour2_index++;
+ }
+ }
+ else
+ { /* next position in offspring is filled */
+ offspring_index++;
+ }
+ }
+}
+
+#endif /* defined(PX) */
diff --git a/src/backend/optimizer/geqo/geqo_random.c b/src/backend/optimizer/geqo/geqo_random.c
new file mode 100644
index 0000000..c6b7648
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_random.c
@@ -0,0 +1,45 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_random.c
+ * random number generator
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/optimizer/geqo/geqo_random.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "optimizer/geqo_random.h"
+
+
+void
+geqo_set_seed(PlannerInfo *root, double seed)
+{
+ GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
+
+ pg_prng_fseed(&private->random_state, seed);
+}
+
+double
+geqo_rand(PlannerInfo *root)
+{
+ GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
+
+ return pg_prng_double(&private->random_state);
+}
+
+int
+geqo_randint(PlannerInfo *root, int upper, int lower)
+{
+ GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
+
+ /*
+ * In current usage, "lower" is never negative so we can just use
+ * pg_prng_uint64_range directly.
+ */
+ return (int) pg_prng_uint64_range(&private->random_state, lower, upper);
+}
diff --git a/src/backend/optimizer/geqo/geqo_recombination.c b/src/backend/optimizer/geqo/geqo_recombination.c
new file mode 100644
index 0000000..a5d3e47
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_recombination.c
@@ -0,0 +1,92 @@
+/*------------------------------------------------------------------------
+*
+* geqo_recombination.c
+* misc recombination procedures
+*
+* src/backend/optimizer/geqo/geqo_recombination.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
+
+#include "postgres.h"
+
+#include "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+
+/*
+ * init_tour
+ *
+ * Randomly generates a legal "traveling salesman" tour
+ * (i.e. where each point is visited only once.)
+ */
+void
+init_tour(PlannerInfo *root, Gene *tour, int num_gene)
+{
+ int i,
+ j;
+
+ /*
+ * We must fill the tour[] array with a random permutation of the numbers
+ * 1 .. num_gene. We can do that in one pass using the "inside-out"
+ * variant of the Fisher-Yates shuffle algorithm. Notionally, we append
+ * each new value to the array and then swap it with a randomly-chosen
+ * array element (possibly including itself, else we fail to generate
+ * permutations with the last city last). The swap step can be optimized
+ * by combining it with the insertion.
+ */
+ if (num_gene > 0)
+ tour[0] = (Gene) 1;
+
+ for (i = 1; i < num_gene; i++)
+ {
+ j = geqo_randint(root, i, 0);
+ /* i != j check avoids fetching uninitialized array element */
+ if (i != j)
+ tour[i] = tour[j];
+ tour[j] = (Gene) (i + 1);
+ }
+}
+
+/* city table is used in these recombination methods: */
+#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
+
+/* alloc_city_table
+ *
+ * allocate memory for city table
+ */
+City *
+alloc_city_table(PlannerInfo *root, int num_gene)
+{
+ City *city_table;
+
+ /*
+ * palloc one extra location so that nodes numbered 1..n can be indexed
+ * directly; 0 will not be used
+ */
+ city_table = (City *) palloc((num_gene + 1) * sizeof(City));
+
+ return city_table;
+}
+
+/* free_city_table
+ *
+ * deallocate memory of city table
+ */
+void
+free_city_table(PlannerInfo *root, City * city_table)
+{
+ pfree(city_table);
+}
+
+#endif /* CX || PX || OX1 || OX2 */
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;
+}