Adding upstream version 14.5.upstream/14.5upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

16 files changed, 2624 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..4f6226b
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_copy.c
@@ -0,0 +1,54 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_copy.c
+ *
+ * Portions Copyright (c) 1996-2021, 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..3b8d2fe
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_cx.c
@@ -0,0 +1,124 @@
+/*------------------------------------------------------------------------
+*
+* 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..3b92f42
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_erx.c
@@ -0,0 +1,471 @@
+/*------------------------------------------------------------------------
+*
+* 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..2ecba83
--- /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-2021, 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 (old_clump->size + new_clump->size < num_gene)
+					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..36df346
--- /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-2021, 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..02b5a70
--- /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-2021, 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..10d2d0a
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_ox1.c
@@ -0,0 +1,95 @@
+/*------------------------------------------------------------------------
+*
+* 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..72b9b0f
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_ox2.c
@@ -0,0 +1,112 @@
+/*------------------------------------------------------------------------
+*
+* 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..ddbc781
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_pmx.c
@@ -0,0 +1,224 @@
+/*------------------------------------------------------------------------
+*
+* 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..1fc103b
--- /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-2021, 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..ad5ad3f
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_px.c
@@ -0,0 +1,110 @@
+/*------------------------------------------------------------------------
+*
+* 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..f21bc04
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_random.c
@@ -0,0 +1,40 @@
+/*------------------------------------------------------------------------
+ *
+ * geqo_random.c
+ *	   random number generator
+ *
+ * Portions Copyright (c) 1996-2021, 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;
+
+	/*
+	 * XXX. This seeding algorithm could certainly be improved - but it is not
+	 * critical to do so.
+	 */
+	memset(private->random_state, 0, sizeof(private->random_state));
+	memcpy(private->random_state,
+		   &seed,
+		   Min(sizeof(private->random_state), sizeof(seed)));
+}
+
+double
+geqo_rand(PlannerInfo *root)
+{
+	GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
+
+	return pg_erand48(private->random_state);
+}
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..66b6c8a
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_selection.c
@@ -0,0 +1,115 @@
+/*-------------------------------------------------------------------------
+ *
+ * geqo_selection.c
+ *	  linear selection scheme for the genetic query optimizer
+ *
+ * Portions Copyright (c) 1996-2021, 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.
+	 *
+	 * This code was observed to hang up in an infinite loop when the
+	 * platform's implementation of erand48() was broken.  We now always use
+	 * our own version.
+	 */
+	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;
+
+	/*
+	 * If geqo_rand() returns exactly 1.0 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;
+}