Make planning via GEQO repeatable

Hi,

Query planning via GEQO currently can yield a different plan on every
invokation of the planner due to its non-exhaustive nature.

This often can be inconvenient because at times there may be a very
bad plan. It also makes it very hard to reproduce a problem with GEQO.

[PATCH 1/3] Add erand48() implementation for non-unixoid systems.

I could not find any suitable PRNG with a visible/changeable state for
windows. Currently random() on windows is mapped to drand48() copied
out of FreeBSD. I copied erand48(state) from there as well.
As I have no windows with a buildsystem available at the moment this
is untested on windows!

[PATCH 2/3] Support a 'geqo_seed' GUC to make planning via GEQO repeatable.

This patch adds a GUC geqo_seed to control whether the PRNG should be
repeatable or not. If geqo_seed = 0 a global/per-backend state is
used, thus the planning is not repeatable.
If set to a value in (0,1] that number is used to initialize the
generator on every planning.

It adds a "void *join_search_private" variable to PlannerInfo to hold
the random number generator. This variable could also be used by a
join_order plugin.
Alternatively it would be possible to start passing GeqoEvalData
around everywhere, but the suggestion to extend PlannerInfo came from
Tom...

"PlannerInfo *root" is now passed to all non-static geqo related
functions. It seems cleaner to do this for all functions than only
functions internally using the random generator.

GeqoEvalData, which is sparsely used, is replaced GeqoPrivateData
which is passed via join_search_private.

[PATCH 3/3] Document geqo_seed variable.

I will submit this to the commitfest. I guess thats OK?

Andres

---
src/include/port.h | 2 ++
src/port/rand.c | 8 ++++++++
2 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/src/include/port.h b/src/include/port.h
index cbf9dcf..af96620 100644
*** a/src/include/port.h
--- b/src/include/port.h
*************** extern FILE *pgwin32_fopen(const char *,
*** 320,325 ****
--- 320,327 ----
extern long lrand48(void);
extern void srand48(long seed);

+ extern long erand48(unsigned short[3]);
+
/* New versions of MingW have gettimeofday, old mingw and msvc don't */
#ifndef HAVE_GETTIMEOFDAY
/* Last parameter not used */
diff --git a/src/port/rand.c b/src/port/rand.c
index 6c14a64..6904bb1 100644
*** a/src/port/rand.c
--- b/src/port/rand.c
*************** srand48(long seed)
*** 80,82 ****
--- 80,90 ----
_rand48_mult[2] = RAND48_MULT_2;
_rand48_add = RAND48_ADD;
}
+
+ double erand48(unsigned short xseed[3])
+ {
+ _dorand48(xseed);
+ return ldexp((double) xseed[0], -48) +
+ ldexp((double) xseed[1], -32) +
+ ldexp((double) xseed[2], -16);
+ }
--
1.6.3.3.335.ge09a8

---
src/backend/optimizer/geqo/Makefile | 1 +
src/backend/optimizer/geqo/geqo_copy.c | 4 +-
src/backend/optimizer/geqo/geqo_cx.c | 6 +-
src/backend/optimizer/geqo/geqo_erx.c | 47 ++++++------
src/backend/optimizer/geqo/geqo_eval.c | 28 ++++----
src/backend/optimizer/geqo/geqo_main.c | 90 ++++++++++++-----------
src/backend/optimizer/geqo/geqo_mutation.c | 10 +-
src/backend/optimizer/geqo/geqo_ox1.c | 8 +-
src/backend/optimizer/geqo/geqo_ox2.c | 7 +-
src/backend/optimizer/geqo/geqo_pmx.c | 7 +-
src/backend/optimizer/geqo/geqo_pool.c | 23 +++---
src/backend/optimizer/geqo/geqo_px.c | 8 +-
src/backend/optimizer/geqo/geqo_random.c | 42 +++++++++++
src/backend/optimizer/geqo/geqo_recombination.c | 9 +-
src/backend/optimizer/geqo/geqo_selection.c | 19 +++--
src/backend/optimizer/path/allpaths.c | 2 +
src/backend/utils/misc/guc.c | 9 ++
src/include/nodes/relation.h | 3 +
src/include/optimizer/geqo.h | 17 ++---
src/include/optimizer/geqo_copy.h | 3 +-
src/include/optimizer/geqo_mutation.h | 3 +-
src/include/optimizer/geqo_pool.h | 14 ++--
src/include/optimizer/geqo_random.h | 9 +-
src/include/optimizer/geqo_recombination.h | 33 +++++---
src/include/optimizer/geqo_selection.h | 4 +-
25 files changed, 244 insertions(+), 162 deletions(-)
create mode 100644 src/backend/optimizer/geqo/geqo_random.c

diff --git a/src/backend/optimizer/geqo/Makefile b/src/backend/optimizer/geqo/Makefile
index dbc6c28..e5a01d7 100644
*** a/src/backend/optimizer/geqo/Makefile
--- b/src/backend/optimizer/geqo/Makefile
*************** top_builddir = ../../../..
*** 14,19 ****
--- 14,20 ----
include $(top_builddir)/src/Makefile.global

OBJS = geqo_copy.o geqo_eval.o geqo_main.o geqo_misc.o \
+ geqo_random.o \
geqo_mutation.o geqo_pool.o geqo_recombination.o \
geqo_selection.o \
geqo_erx.o geqo_pmx.o geqo_cx.o geqo_px.o geqo_ox1.o geqo_ox2.o
diff --git a/src/backend/optimizer/geqo/geqo_copy.c b/src/backend/optimizer/geqo/geqo_copy.c
index 83af33a..373a924 100644
*** a/src/backend/optimizer/geqo/geqo_copy.c
--- b/src/backend/optimizer/geqo/geqo_copy.c
***************
*** 35,40 ****
--- 35,41 ----

#include "postgres.h"
#include "optimizer/geqo_copy.h"
+ #include "optimizer/geqo_copy.h"

/* geqo_copy
*
***************
*** 42,48 ****
*
*/
void
! geqo_copy(Chromosome *chromo1, Chromosome *chromo2, int string_length)
{
int i;

--- 43,50 ----
*
*/
void
! geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2,
! int string_length)
{
int i;

diff --git a/src/backend/optimizer/geqo/geqo_cx.c b/src/backend/optimizer/geqo/geqo_cx.c
index 3d5102f..ad861ce 100644
*** a/src/backend/optimizer/geqo/geqo_cx.c
--- b/src/backend/optimizer/geqo/geqo_cx.c
***************
*** 35,40 ****
--- 35,41 ----


#include "postgres.h"
+ #include "optimizer/geqo.h"
#include "optimizer/geqo_recombination.h"
#include "optimizer/geqo_random.h"

***************
*** 44,50 ****
* cycle crossover
*/
int
! cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
{

int i,
--- 45,52 ----
* cycle crossover
*/
int
! cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
! int num_gene, City *city_table)
{

int i,
*************** cx(Gene *tour1, Gene *tour2, Gene *offsp
*** 62,68 ****
}

/* choose random cycle starting position */
! start_pos = geqo_randint(num_gene - 1, 0);

/* child inherits first city */
offspring[start_pos] = tour1[start_pos];
--- 64,70 ----
}

/* choose random cycle starting position */
! start_pos = geqo_randint(root, num_gene - 1, 0);

/* child inherits first city */
offspring[start_pos] = tour1[start_pos];
diff --git a/src/backend/optimizer/geqo/geqo_erx.c b/src/backend/optimizer/geqo/geqo_erx.c
index 35e1a28..5bae059 100644
*** a/src/backend/optimizer/geqo/geqo_erx.c
--- b/src/backend/optimizer/geqo/geqo_erx.c
***************
*** 36,46 ****
#include "optimizer/geqo_random.h"


! static int gimme_edge(Gene gene1, Gene gene2, Edge *edge_table);
! static void remove_gene(Gene gene, Edge edge, Edge *edge_table);
! static Gene gimme_gene(Edge edge, Edge *edge_table);

! static Gene edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene);


/* alloc_edge_table
--- 36,46 ----
#include "optimizer/geqo_random.h"


! 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
*************** static Gene edge_failure(Gene *gene, int
*** 50,56 ****
*/

Edge *
! alloc_edge_table(int num_gene)
{
Edge *edge_table;

--- 50,56 ----
*/

Edge *
! alloc_edge_table(PlannerInfo *root, int num_gene)
{
Edge *edge_table;

*************** alloc_edge_table(int num_gene)
*** 70,76 ****
*
*/
void
! free_edge_table(Edge *edge_table)
{
pfree(edge_table);
}
--- 70,76 ----
*
*/
void
! free_edge_table(PlannerInfo *root, Edge *edge_table)
{
pfree(edge_table);
}
*************** free_edge_table(Edge *edge_table)
*** 89,95 ****
*
*/
float
! gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
{
int i,
index1,
--- 89,96 ----
*
*/
float
! gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
! int num_gene, Edge *edge_table)
{
int i,
index1,
*************** gimme_edge_table(Gene *tour1, Gene *tour
*** 121,131 ****
* twice per edge
*/

! edge_total += gimme_edge(tour1[index1], tour1[index2], edge_table);
! gimme_edge(tour1[index2], tour1[index1], edge_table);

! edge_total += gimme_edge(tour2[index1], tour2[index2], edge_table);
! gimme_edge(tour2[index2], tour2[index1], edge_table);
}

/* return average number of edges per index */
--- 122,132 ----
* 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 */
*************** gimme_edge_table(Gene *tour1, Gene *tour
*** 147,153 ****
* 0 if edge was already registered and edge_table is unchanged
*/
static int
! gimme_edge(Gene gene1, Gene gene2, Edge *edge_table)
{
int i;
int edges;
--- 148,154 ----
* 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;
*************** gimme_edge(Gene gene1, Gene gene2, Edge
*** 189,200 ****
*
*/
int
! gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene)
{
int i;
int edge_failures = 0;

! new_gene[0] = (Gene) geqo_randint(num_gene, 1); /* choose int between 1
* and num_gene */

for (i = 1; i < num_gene; i++)
--- 190,201 ----
*
*/
int
! gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
{
int i;
int edge_failures = 0;

! new_gene[0] = (Gene) geqo_randint(root, num_gene, 1); /* choose int between 1
* and num_gene */

for (i = 1; i < num_gene; i++)
*************** gimme_tour(Edge *edge_table, Gene *new_g
*** 204,221 ****
* table
*/

! remove_gene(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(edge_table[(int) new_gene[i - 1]], edge_table);

else
{ /* cope with fault */
edge_failures++;

! new_gene[i] = edge_failure(new_gene, i - 1, edge_table, num_gene);
}

/* mark this node as incorporated */
--- 205,222 ----
* 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 */
*************** gimme_tour(Edge *edge_table, Gene *new_g
*** 235,241 ****
*
*/
static void
! remove_gene(Gene gene, Edge edge, Edge *edge_table)
{
int i,
j;
--- 236,242 ----
*
*/
static void
! remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
{
int i,
j;
*************** remove_gene(Gene gene, Edge edge, Edge *
*** 277,283 ****
*
*/
static Gene
! gimme_gene(Edge edge, Edge *edge_table)
{
int i;
Gene friend;
--- 278,284 ----
*
*/
static Gene
! gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
{
int i;
Gene friend;
*************** gimme_gene(Edge edge, Edge *edge_table)
*** 340,346 ****


/* random decision of the possible candidates to use */
! rand_decision = (int) geqo_randint(minimum_count - 1, 0);


for (i = 0; i < edge.unused_edges; i++)
--- 341,347 ----


/* 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++)
*************** gimme_gene(Edge edge, Edge *edge_table)
*** 368,374 ****
*
*/
static Gene
! edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene)
{
int i;
Gene fail_gene = gene[index];
--- 369,375 ----
*
*/
static Gene
! edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
{
int i;
Gene fail_gene = gene[index];
*************** edge_failure(Gene *gene, int index, Edge
*** 401,407 ****
if (four_count != 0)
{

! rand_decision = (int) geqo_randint(four_count - 1, 0);

for (i = 1; i <= num_gene; i++)
{
--- 402,408 ----
if (four_count != 0)
{

! rand_decision = geqo_randint(root, four_count - 1, 0);

for (i = 1; i <= num_gene; i++)
{
*************** edge_failure(Gene *gene, int index, Edge
*** 423,429 ****
else if (remaining_edges != 0)
{
/* random decision of the gene with remaining edges */
! rand_decision = (int) geqo_randint(remaining_edges - 1, 0);

for (i = 1; i <= num_gene; i++)
{
--- 424,430 ----
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++)
{
diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c
index 04b3bfe..11903a5 100644
*** a/src/backend/optimizer/geqo/geqo_eval.c
--- b/src/backend/optimizer/geqo/geqo_eval.c
*************** static bool desirable_join(PlannerInfo *
*** 42,48 ****
* Returns cost of a query tree as an individual of the population.
*/
Cost
! geqo_eval(Gene *tour, int num_gene, GeqoEvalData *evaldata)
{
MemoryContext mycontext;
MemoryContext oldcxt;
--- 42,48 ----
* Returns cost of a query tree as an individual of the population.
*/
Cost
! geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
{
MemoryContext mycontext;
MemoryContext oldcxt;
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 94,106 ****
* (If we are dealing with enough join rels, which we very likely are, a
* new hash table will get built and used locally.)
*/
! savelength = list_length(evaldata->root->join_rel_list);
! savehash = evaldata->root->join_rel_hash;

! evaldata->root->join_rel_hash = NULL;

/* construct the best path for the given combination of relations */
! joinrel = gimme_tree(tour, num_gene, evaldata);

/*
* compute fitness
--- 94,106 ----
* (If we are dealing with enough join rels, which we very likely are, a
* new hash table will get built and used locally.)
*/
! savelength = list_length(root->join_rel_list);
! savehash = root->join_rel_hash;

! root->join_rel_hash = NULL;

/* construct the best path for the given combination of relations */
! joinrel = gimme_tree(root, tour, num_gene);

/*
* compute fitness
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 117,125 ****
* Restore join_rel_list to its former state, and put back original
* hashtable if any.
*/
! evaldata->root->join_rel_list = list_truncate(evaldata->root->join_rel_list,
! savelength);
! evaldata->root->join_rel_hash = savehash;

/* release all the memory acquired within gimme_tree */
MemoryContextSwitchTo(oldcxt);
--- 117,125 ----
* 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);
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 134,140 ****
* order.
*
* 'tour' is the proposed join order, of length 'num_gene'
- * 'evaldata' contains the context we need
*
* 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.
--- 134,139 ----
*************** geqo_eval(Gene *tour, int num_gene, Geqo
*** 153,159 ****
* plans.
*/
RelOptInfo *
! gimme_tree(Gene *tour, int num_gene, GeqoEvalData *evaldata)
{
RelOptInfo **stack;
int stack_depth;
--- 152,158 ----
* plans.
*/
RelOptInfo *
! gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
{
RelOptInfo **stack;
int stack_depth;
*************** gimme_tree(Gene *tour, int num_gene, Geq
*** 193,200 ****

/* Get the next input relation and push it */
cur_rel_index = (int) tour[rel_count];
! stack[stack_depth] = (RelOptInfo *) list_nth(evaldata->initial_rels,
! cur_rel_index - 1);
stack_depth++;

/*
--- 192,200 ----

/* Get the next input relation and push it */
cur_rel_index = (int) tour[rel_count];
! stack[stack_depth] = (RelOptInfo *) list_nth(
! ((GeqoPrivateData*)root->join_search_private)->initial_rels,
! cur_rel_index - 1);
stack_depth++;

/*
*************** gimme_tree(Gene *tour, int num_gene, Geq
*** 211,217 ****
* have exhausted the input, the heuristics can't prevent popping.
*/
if (rel_count < num_gene - 1 &&
! !desirable_join(evaldata->root, outer_rel, inner_rel))
break;

/*
--- 211,217 ----
* have exhausted the input, the heuristics can't prevent popping.
*/
if (rel_count < num_gene - 1 &&
! !desirable_join(root, outer_rel, inner_rel))
break;

/*
*************** gimme_tree(Gene *tour, int num_gene, Geq
*** 220,226 ****
* root->join_rel_list yet, and so the paths constructed for it
* will only include the ones we want.
*/
! joinrel = make_join_rel(evaldata->root, outer_rel, inner_rel);

/* Can't pop stack here if join order is not valid */
if (!joinrel)
--- 220,226 ----
* root->join_rel_list yet, and so the paths constructed for it
* will only include the ones we want.
*/
! joinrel = make_join_rel(root, outer_rel, inner_rel);

/* Can't pop stack here if join order is not valid */
if (!joinrel)
diff --git a/src/backend/optimizer/geqo/geqo_main.c b/src/backend/optimizer/geqo/geqo_main.c
index 72b0b57..10f64f4 100644
*** a/src/backend/optimizer/geqo/geqo_main.c
--- b/src/backend/optimizer/geqo/geqo_main.c
***************
*** 29,34 ****
--- 29,35 ----
#include "optimizer/geqo_misc.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_selection.h"
+ #include "optimizer/geqo_random.h"


/*
*************** int Geqo_effort;
*** 38,43 ****
--- 39,45 ----
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
*** 63,69 ****
RelOptInfo *
geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
{
- GeqoEvalData evaldata;
int generation;
Chromosome *momma;
Chromosome *daddy;
--- 65,70 ----
*************** geqo(PlannerInfo *root, int number_of_re
*** 88,96 ****
int mutations = 0;
#endif

! /* set up evaldata */
! evaldata.root = root;
! evaldata.initial_rels = initial_rels;

/* set GA parameters */
pool_size = gimme_pool_size(number_of_rels);
--- 89,102 ----
int mutations = 0;
#endif

! /* setup private information */
! root->join_search_private = (GeqoPrivateData*)palloc0(sizeof(GeqoPrivateData));
! ((GeqoPrivateData*)root->join_search_private)->initial_rels = initial_rels;
!
! /* initialize private number generator */
! if(Geqo_seed != 0){
! geqo_seed(root, Geqo_seed);
! }

/* set GA parameters */
pool_size = gimme_pool_size(number_of_rels);
*************** geqo(PlannerInfo *root, int number_of_re
*** 98,110 ****
status_interval = 10;

/* allocate genetic pool memory */
! pool = alloc_pool(pool_size, number_of_rels);

/* random initialization of the pool */
! random_init_pool(pool, &evaldata);

/* sort the pool according to cheapest path as fitness */
! sort_pool(pool); /* we have to do it only one time, since all
* kids replace the worst individuals in
* future (-> geqo_pool.c:spread_chromo ) */

--- 104,116 ----
status_interval = 10;

/* 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 ) */

*************** geqo(PlannerInfo *root, int number_of_re
*** 116,164 ****
#endif

/* allocate chromosome momma and daddy memory */
! momma = alloc_chromo(pool->string_length);
! daddy = alloc_chromo(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(pool->string_length);
#elif defined(PMX)
#ifdef GEQO_DEBUG
elog(DEBUG2, "using partially matched crossover [PMX]");
#endif
/* allocate chromosome kid memory */
! kid = alloc_chromo(pool->string_length);
#elif defined(CX)
#ifdef GEQO_DEBUG
elog(DEBUG2, "using cycle crossover [CX]");
#endif
/* allocate city table memory */
! kid = alloc_chromo(pool->string_length);
! city_table = alloc_city_table(pool->string_length);
#elif defined(PX)
#ifdef GEQO_DEBUG
elog(DEBUG2, "using position crossover [PX]");
#endif
/* allocate city table memory */
! kid = alloc_chromo(pool->string_length);
! city_table = alloc_city_table(pool->string_length);
#elif defined(OX1)
#ifdef GEQO_DEBUG
elog(DEBUG2, "using order crossover [OX1]");
#endif
/* allocate city table memory */
kid = alloc_chromo(pool->string_length);
! city_table = alloc_city_table(pool->string_length);
#elif defined(OX2)
#ifdef GEQO_DEBUG
elog(DEBUG2, "using order crossover [OX2]");
#endif
/* allocate city table memory */
kid = alloc_chromo(pool->string_length);
! city_table = alloc_city_table(pool->string_length);
#endif


--- 122,170 ----
#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(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(pool->string_length);
! city_table = alloc_city_table(root, pool->string_length);
#endif


*************** geqo(PlannerInfo *root, int number_of_re
*** 168,212 ****
for (generation = 0; generation < number_generations; generation++)
{
/* SELECTION: using linear bias function */
! geqo_selection(momma, daddy, pool, Geqo_selection_bias);

#if defined (ERX)
/* EDGE RECOMBINATION CROSSOVER */
! difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);

kid = momma;

/* are there any edge failures ? */
! edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
#elif defined(PMX)
/* PARTIALLY MATCHED CROSSOVER */
! pmx(momma->string, daddy->string, kid->string, pool->string_length);
#elif defined(CX)
/* CYCLE CROSSOVER */
! cycle_diffs = cx(momma->string, daddy->string, kid->string, pool->string_length, city_table);
/* mutate the child */
if (cycle_diffs == 0)
{
mutations++;
! geqo_mutation(kid->string, pool->string_length);
}
#elif defined(PX)
/* POSITION CROSSOVER */
! px(momma->string, daddy->string, kid->string, pool->string_length, city_table);
#elif defined(OX1)
/* ORDER CROSSOVER */
! ox1(momma->string, daddy->string, kid->string, pool->string_length, city_table);
#elif defined(OX2)
/* ORDER CROSSOVER */
! ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
#endif


/* EVALUATE FITNESS */
! kid->worth = geqo_eval(kid->string, pool->string_length, &evaldata);

/* push the kid into the wilderness of life according to its worth */
! spread_chromo(kid, pool);


#ifdef GEQO_DEBUG
--- 174,218 ----
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 */
! difference = 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
*************** geqo(PlannerInfo *root, int number_of_re
*** 249,255 ****
*/
best_tour = (Gene *) pool->data[0].string;

! best_rel = gimme_tree(best_tour, pool->string_length, &evaldata);

if (best_rel == NULL)
elog(ERROR, "failed to make a valid plan");
--- 255,261 ----
*/
best_tour = (Gene *) pool->data[0].string;

! best_rel = gimme_tree(root, best_tour, pool->string_length);

if (best_rel == NULL)
elog(ERROR, "failed to make a valid plan");
*************** geqo(PlannerInfo *root, int number_of_re
*** 260,287 ****
#endif

/* ... free memory stuff */
! free_chromo(momma);
! free_chromo(daddy);

#if defined (ERX)
! free_edge_table(edge_table);
#elif defined(PMX)
! free_chromo(kid);
#elif defined(CX)
! free_chromo(kid);
! free_city_table(city_table);
#elif defined(PX)
! free_chromo(kid);
! free_city_table(city_table);
#elif defined(OX1)
! free_chromo(kid);
! free_city_table(city_table);
#elif defined(OX2)
! free_chromo(kid);
! free_city_table(city_table);
#endif

! free_pool(pool);

return best_rel;
}
--- 266,293 ----
#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);

return best_rel;
}
diff --git a/src/backend/optimizer/geqo/geqo_mutation.c b/src/backend/optimizer/geqo/geqo_mutation.c
index 899410c..acf3b34 100644
*** a/src/backend/optimizer/geqo/geqo_mutation.c
--- b/src/backend/optimizer/geqo/geqo_mutation.c
***************
*** 36,56 ****
#include "optimizer/geqo_random.h"

void
! geqo_mutation(Gene *tour, int num_gene)
{
int swap1;
int swap2;
! int num_swaps = geqo_randint(num_gene / 3, 0);
Gene temp;


while (num_swaps > 0)
{
! swap1 = geqo_randint(num_gene - 1, 0);
! swap2 = geqo_randint(num_gene - 1, 0);

while (swap1 == swap2)
! swap2 = geqo_randint(num_gene - 1, 0);

temp = tour[swap1];
tour[swap1] = tour[swap2];
--- 36,56 ----
#include "optimizer/geqo_random.h"

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];
diff --git a/src/backend/optimizer/geqo/geqo_ox1.c b/src/backend/optimizer/geqo/geqo_ox1.c
index cd979df..d292e98 100644
*** a/src/backend/optimizer/geqo/geqo_ox1.c
--- b/src/backend/optimizer/geqo/geqo_ox1.c
***************
*** 34,39 ****
--- 34,40 ----
/*************************************************************/

#include "postgres.h"
+ #include "optimizer/geqo.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

***************
*** 43,49 ****
* position crossover
*/
void
! ox1(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
{
int left,
right,
--- 44,51 ----
* position crossover
*/
void
! ox1(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
! City *city_table)
{
int left,
right,
*************** ox1(Gene *tour1, Gene *tour2, Gene *offs
*** 56,63 ****
city_table[k].used = 0;

/* select portion to copy from tour1 */
! left = geqo_randint(num_gene - 1, 0);
! right = geqo_randint(num_gene - 1, 0);

if (left > right)
{
--- 58,65 ----
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)
{
diff --git a/src/backend/optimizer/geqo/geqo_ox2.c b/src/backend/optimizer/geqo/geqo_ox2.c
index 0d2e0de..a2fdfe8 100644
*** a/src/backend/optimizer/geqo/geqo_ox2.c
--- b/src/backend/optimizer/geqo/geqo_ox2.c
***************
*** 34,39 ****
--- 34,40 ----
/*************************************************************/

#include "postgres.h"
+ #include "optimizer/geqo.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

***************
*** 43,49 ****
* position crossover
*/
void
! ox2(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
{
int k,
j,
--- 44,50 ----
* position crossover
*/
void
! ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
{
int k,
j,
*************** ox2(Gene *tour1, Gene *tour2, Gene *offs
*** 60,71 ****
}

/* determine the number of positions to be inherited from tour1 */
! num_positions = geqo_randint(2 * num_gene / 3, num_gene / 3);

/* make a list of selected cities */
for (k = 0; k < num_positions; k++)
{
! pos = geqo_randint(num_gene - 1, 0);
city_table[pos].select_list = (int) tour1[pos];
city_table[(int) tour1[pos]].used = 1; /* mark used */
}
--- 61,72 ----
}

/* 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 */
}
diff --git a/src/backend/optimizer/geqo/geqo_pmx.c b/src/backend/optimizer/geqo/geqo_pmx.c
index fe9d4b4..a8d18c5 100644
*** a/src/backend/optimizer/geqo/geqo_pmx.c
--- b/src/backend/optimizer/geqo/geqo_pmx.c
***************
*** 34,39 ****
--- 34,40 ----
/*************************************************************/

#include "postgres.h"
+ #include "optimizer/geqo.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

***************
*** 43,49 ****
* partially matched crossover
*/
void
! pmx(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));
--- 44,50 ----
* 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));
*************** pmx(Gene *tour1, Gene *tour2, Gene *offs
*** 71,78 ****
}

/* locate crossover points */
! left = geqo_randint(num_gene - 1, 0);
! right = geqo_randint(num_gene - 1, 0);

if (left > right)
{
--- 72,79 ----
}

/* locate crossover points */
! left = geqo_randint(root, num_gene - 1, 0);
! right = geqo_randint(root, num_gene - 1, 0);

if (left > right)
{
diff --git a/src/backend/optimizer/geqo/geqo_pool.c b/src/backend/optimizer/geqo/geqo_pool.c
index 72eb34f..64e23ba 100644
*** a/src/backend/optimizer/geqo/geqo_pool.c
--- b/src/backend/optimizer/geqo/geqo_pool.c
*************** static int compare(const void *arg1, con
*** 39,45 ****
* allocates memory for GA pool
*/
Pool *
! alloc_pool(int pool_size, int string_length)
{
Pool *new_pool;
Chromosome *chromo;
--- 39,45 ----
* allocates memory for GA pool
*/
Pool *
! alloc_pool(PlannerInfo *root, int pool_size, int string_length)
{
Pool *new_pool;
Chromosome *chromo;
*************** alloc_pool(int pool_size, int string_len
*** 66,72 ****
* deallocates memory for GA pool
*/
void
! free_pool(Pool *pool)
{
Chromosome *chromo;
int i;
--- 66,72 ----
* deallocates memory for GA pool
*/
void
! free_pool(PlannerInfo *root, Pool *pool)
{
Chromosome *chromo;
int i;
*************** free_pool(Pool *pool)
*** 88,94 ****
* initialize genetic pool
*/
void
! random_init_pool(Pool *pool, GeqoEvalData *evaldata)
{
Chromosome *chromo = (Chromosome *) pool->data;
int i;
--- 88,94 ----
* initialize genetic pool
*/
void
! random_init_pool(PlannerInfo *root, Pool *pool)
{
Chromosome *chromo = (Chromosome *) pool->data;
int i;
*************** random_init_pool(Pool *pool, GeqoEvalDat
*** 105,114 ****
i = 0;
while (i < pool->size)
{
! init_tour(chromo[i].string, pool->string_length);
! pool->data[i].worth = geqo_eval(chromo[i].string,
! pool->string_length,
! evaldata);
if (pool->data[i].worth < DBL_MAX)
i++;
else
--- 105,113 ----
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
*************** random_init_pool(Pool *pool, GeqoEvalDat
*** 133,139 ****
* maybe you have to change compare() for different ordering ...
*/
void
! sort_pool(Pool *pool)
{
qsort(pool->data, pool->size, sizeof(Chromosome), compare);
}
--- 132,138 ----
* 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(const void *arg1, const void *ar
*** 160,166 ****
* allocates a chromosome and string space
*/
Chromosome *
! alloc_chromo(int string_length)
{
Chromosome *chromo;

--- 159,165 ----
* allocates a chromosome and string space
*/
Chromosome *
! alloc_chromo(PlannerInfo *root, int string_length)
{
Chromosome *chromo;

*************** alloc_chromo(int string_length)
*** 174,180 ****
* deallocates a chromosome and string space
*/
void
! free_chromo(Chromosome *chromo)
{
pfree(chromo->string);
pfree(chromo);
--- 173,179 ----
* deallocates a chromosome and string space
*/
void
! free_chromo(PlannerInfo *root, Chromosome *chromo)
{
pfree(chromo->string);
pfree(chromo);
*************** free_chromo(Chromosome *chromo)
*** 185,191 ****
* assumes best->worst = smallest->largest
*/
void
! spread_chromo(Chromosome *chromo, Pool *pool)
{
int top,
mid,
--- 184,190 ----
* assumes best->worst = smallest->largest
*/
void
! spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
{
int top,
mid,
*************** spread_chromo(Chromosome *chromo, Pool *
*** 247,253 ****
* copy new gene into pool storage; always replace worst gene in pool
*/

! geqo_copy(&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;
--- 246,252 ----
* 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;
diff --git a/src/backend/optimizer/geqo/geqo_px.c b/src/backend/optimizer/geqo/geqo_px.c
index 07f41cd..9e9cee2 100644
*** a/src/backend/optimizer/geqo/geqo_px.c
--- b/src/backend/optimizer/geqo/geqo_px.c
***************
*** 34,39 ****
--- 34,40 ----
/*************************************************************/

#include "postgres.h"
+ #include "optimizer/geqo.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

***************
*** 43,49 ****
* position crossover
*/
void
! px(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
{

int num_positions;
--- 44,51 ----
* position crossover
*/
void
! px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
! City *city_table)
{

int num_positions;
*************** px(Gene *tour1, Gene *tour2, Gene *offsp
*** 57,68 ****
city_table[i].used = 0;

/* choose random positions that will be inherited directly from parent */
! num_positions = geqo_randint(2 * num_gene / 3, num_gene / 3);

/* choose random position */
for (i = 0; i < num_positions; i++)
{
! pos = geqo_randint(num_gene - 1, 0);

offspring[pos] = tour1[pos]; /* transfer cities to child */
city_table[(int) tour1[pos]].used = 1; /* mark city used */
--- 59,70 ----
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 */
diff --git a/src/backend/optimizer/geqo/geqo_random.c b/src/backend/optimizer/geqo/geqo_random.c
index ...59d5e42 .
*** a/src/backend/optimizer/geqo/geqo_random.c
--- b/src/backend/optimizer/geqo/geqo_random.c
***************
*** 0 ****
--- 1,42 ----
+ /*------------------------------------------------------------------------
+ *
+ * geqo_misc.c
+ * misc. printout and debug stuff
+ *
+ * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL$
+ *
+ *-------------------------------------------------------------------------
+ */
+
+ #include "postgres.h"
+
+ #include "optimizer/geqo.h"
+ #include "optimizer/geqo_random.h"
+
+
+ static unsigned short global_random_state[3];
+
+ void geqo_seed(PlannerInfo *root, double seed){
+ GeqoPrivateData *private = (GeqoPrivateData*)root->join_search_private;
+
+ private->random_state = palloc(sizeof(global_random_state));
+
+ /*
+ * XXX. This seeding algorithm could certainly be improved - but
+ * it is not critical to do so.
+ */
+ memcpy(private->random_state,
+ &seed,
+ Min(sizeof(global_random_state),
+ sizeof(seed))
+ );
+ }
+
+ double geqo_rand(PlannerInfo *root){
+ if(!((GeqoPrivateData*)root->join_search_private)->random_state)
+ return erand48(global_random_state);
+ return erand48(((GeqoPrivateData*)root->join_search_private)->random_state);
+ };
diff --git a/src/backend/optimizer/geqo/geqo_recombination.c b/src/backend/optimizer/geqo/geqo_recombination.c
index 3972fb1..e2b69a3 100644
*** a/src/backend/optimizer/geqo/geqo_recombination.c
--- b/src/backend/optimizer/geqo/geqo_recombination.c
***************
*** 20,25 ****
--- 20,26 ----

#include "postgres.h"

+ #include "optimizer/geqo.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

***************
*** 35,41 ****
* and the procedure repeated.
*/
void
! init_tour(Gene *tour, int num_gene)
{
Gene *tmp;
int remainder;
--- 36,42 ----
* and the procedure repeated.
*/
void
! init_tour(PlannerInfo *root, Gene *tour, int num_gene)
{
Gene *tmp;
int remainder;
*************** init_tour(Gene *tour, int num_gene)
*** 53,59 ****
for (i = 0; i < num_gene; i++)
{
/* choose value between 0 and remainder inclusive */
! next = (int) geqo_randint(remainder, 0);
/* output that element of the tmp array */
tour[i] = tmp[next];
/* and delete it */
--- 54,60 ----
for (i = 0; i < num_gene; i++)
{
/* choose value between 0 and remainder inclusive */
! next = (int) geqo_randint(root, remainder, 0);
/* output that element of the tmp array */
tour[i] = tmp[next];
/* and delete it */
*************** init_tour(Gene *tour, int num_gene)
*** 81,87 ****
* allocate memory for city table
*/
City *
! alloc_city_table(int num_gene)
{
City *city_table;

--- 82,88 ----
* allocate memory for city table
*/
City *
! alloc_city_table(PlannerInfo *root, int num_gene)
{
City *city_table;

*************** alloc_city_table(int num_gene)
*** 99,105 ****
* deallocate memory of city table
*/
void
! free_city_table(City *city_table)
{
pfree(city_table);
}
--- 100,106 ----
* deallocate memory of city table
*/
void
! free_city_table(PlannerInfo *root, City *city_table)
{
pfree(city_table);
}
diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c
index d4f2c4d..2cd7402 100644
*** a/src/backend/optimizer/geqo/geqo_selection.c
--- b/src/backend/optimizer/geqo/geqo_selection.c
***************
*** 42,48 ****
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_selection.h"

! static int linear(int max, double bias);


/*
--- 42,48 ----
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_selection.h"

! static int linear(PlannerInfo *root, int max, double bias);


/*
*************** static int linear(int max, double bias);
*** 51,72 ****
* first and second genes are selected from the pool
*/
void
! geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
{
int first,
second;

! first = linear(pool->size, bias);
! second = linear(pool->size, bias);

if (pool->size > 1)
{
while (first == second)
! second = linear(pool->size, bias);
}

! geqo_copy(momma, &pool->data[first], pool->string_length);
! geqo_copy(daddy, &pool->data[second], pool->string_length);
}

/*
--- 51,73 ----
* 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(root, pool->size, bias);
! second = linear(root, pool->size, bias);

if (pool->size > 1)
{
while (first == second)
! second = linear(root, pool->size, bias);
}

! geqo_copy(root, momma, &pool->data[first], pool->string_length);
! geqo_copy(root, daddy, &pool->data[second], pool->string_length);
}

/*
*************** geqo_selection(Chromosome *momma, Chromo
*** 78,84 ****
* bias = (prob of first rule) / (prob of middle rule)
*/
static int
! linear(int pool_size, double bias) /* bias is y-intercept of linear
* distribution */
{
double index; /* index between 0 and pop_size */
--- 79,85 ----
* bias = (prob of first rule) / (prob of middle rule)
*/
static int
! linear(PlannerInfo *root, int pool_size, double bias) /* bias is y-intercept of linear
* distribution */
{
double index; /* index between 0 and pop_size */
*************** linear(int pool_size, double bias) /* b
*** 95,101 ****
{
double sqrtval;

! sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand();
if (sqrtval > 0.0)
sqrtval = sqrt(sqrtval);
index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
--- 96,102 ----
{
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);
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b375902..777d75d 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** standard_join_search(PlannerInfo *root,
*** 901,906 ****
--- 901,908 ----
int lev;
RelOptInfo *rel;

+ Assert(root->join_search_private == 0);
+
/*
* We employ a simple "dynamic programming" algorithm: we first find all
* ways to build joins of two jointree items, then all ways to build joins
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 2430185..4126516 100644
*** a/src/backend/utils/misc/guc.c
--- b/src/backend/utils/misc/guc.c
*************** static struct config_real ConfigureNames
*** 2026,2031 ****
--- 2026,2040 ----
DEFAULT_GEQO_SELECTION_BIAS, MIN_GEQO_SELECTION_BIAS,
MAX_GEQO_SELECTION_BIAS, NULL, NULL
},
+ {
+ {"geqo_seed", PGC_USERSET, QUERY_TUNING_GEQO,
+ gettext_noop("GEQO: seed for random path selection for repeatable plan generation."),
+ gettext_noop("If zero planning will not be repeatable"),
+ GUC_NOT_IN_SAMPLE
+ },
+ &Geqo_seed,
+ 0, 0, 1, NULL, NULL
+ },

{
{"bgwriter_lru_multiplier", PGC_SIGHUP, RESOURCES,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index ea48889..8f82d71 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 192,197 ****
--- 192,200 ----
/* These fields are used only when hasRecursion is true: */
int wt_param_id; /* PARAM_EXEC ID for the work table */
struct Plan *non_recursive_plan; /* plan for non-recursive term */
+
+ /* private data for join-order implementation, i.e. GEQO */
+ void *join_search_private;
} PlannerInfo;


diff --git a/src/include/optimizer/geqo.h b/src/include/optimizer/geqo.h
index ea4c812..7a9b6a4 100644
*** a/src/include/optimizer/geqo.h
--- b/src/include/optimizer/geqo.h
*************** extern int Geqo_pool_size; /* 2 .. inf,
*** 59,88 ****
extern int Geqo_generations; /* 1 .. inf, or 0 to use default */

extern double Geqo_selection_bias;

#define DEFAULT_GEQO_SELECTION_BIAS 2.0
#define MIN_GEQO_SELECTION_BIAS 1.5
#define MAX_GEQO_SELECTION_BIAS 2.0


- /*
- * Data structure to encapsulate information needed for building plan trees
- * (i.e., geqo_eval and gimme_tree).
- */
typedef struct
{
! PlannerInfo *root; /* the query we are planning */
! List *initial_rels; /* the base relations */
! } GeqoEvalData;
!

/* routines in geqo_main.c */
extern RelOptInfo *geqo(PlannerInfo *root,
int number_of_rels, List *initial_rels);

/* routines in geqo_eval.c */
! extern Cost geqo_eval(Gene *tour, int num_gene, GeqoEvalData *evaldata);
! extern RelOptInfo *gimme_tree(Gene *tour, int num_gene,
! GeqoEvalData *evaldata);

#endif /* GEQO_H */
--- 59,83 ----
extern int Geqo_generations; /* 1 .. inf, or 0 to use default */

extern double Geqo_selection_bias;
+ extern double Geqo_seed;

#define DEFAULT_GEQO_SELECTION_BIAS 2.0
#define MIN_GEQO_SELECTION_BIAS 1.5
#define MAX_GEQO_SELECTION_BIAS 2.0


typedef struct
{
! List *initial_rels;
! unsigned short *random_state;
! } GeqoPrivateData;

/* routines in geqo_main.c */
extern RelOptInfo *geqo(PlannerInfo *root,
int number_of_rels, List *initial_rels);

/* routines in geqo_eval.c */
! extern Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_geneo);
! extern RelOptInfo *gimme_tree(PlannerInfo *root, Gene *tour, int num_gene);

#endif /* GEQO_H */
diff --git a/src/include/optimizer/geqo_copy.h b/src/include/optimizer/geqo_copy.h
index ae13059..63b7c83 100644
*** a/src/include/optimizer/geqo_copy.h
--- b/src/include/optimizer/geqo_copy.h
***************
*** 22,29 ****
#ifndef GEQO_COPY_H
#define GEQO_COPY_H

#include "optimizer/geqo_gene.h"

! extern void geqo_copy(Chromosome *chromo1, Chromosome *chromo2, int string_length);

#endif /* GEQO_COPY_H */
--- 22,30 ----
#ifndef GEQO_COPY_H
#define GEQO_COPY_H

+ #include "optimizer/geqo.h"
#include "optimizer/geqo_gene.h"

! extern void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length);

#endif /* GEQO_COPY_H */
diff --git a/src/include/optimizer/geqo_mutation.h b/src/include/optimizer/geqo_mutation.h
index 0384de8..3ada430 100644
*** a/src/include/optimizer/geqo_mutation.h
--- b/src/include/optimizer/geqo_mutation.h
***************
*** 22,29 ****
#ifndef GEQO_MUTATION_H
#define GEQO_MUTATION_H

#include "optimizer/geqo_gene.h"

! extern void geqo_mutation(Gene *tour, int num_gene);

#endif /* GEQO_MUTATION_H */
--- 22,30 ----
#ifndef GEQO_MUTATION_H
#define GEQO_MUTATION_H

+ #include "optimizer/geqo.h"
#include "optimizer/geqo_gene.h"

! extern void geqo_mutation(PlannerInfo *root, Gene *tour, int num_gene);

#endif /* GEQO_MUTATION_H */
diff --git a/src/include/optimizer/geqo_pool.h b/src/include/optimizer/geqo_pool.h
index 950e667..dbc6a01 100644
*** a/src/include/optimizer/geqo_pool.h
--- b/src/include/optimizer/geqo_pool.h
***************
*** 26,40 ****
#include "optimizer/geqo.h"


! extern Pool *alloc_pool(int pool_size, int string_length);
! extern void free_pool(Pool *pool);

! extern void random_init_pool(Pool *pool, GeqoEvalData *evaldata);
! extern Chromosome *alloc_chromo(int string_length);
! extern void free_chromo(Chromosome *chromo);

! extern void spread_chromo(Chromosome *chromo, Pool *pool);

! extern void sort_pool(Pool *pool);

#endif /* GEQO_POOL_H */
--- 26,40 ----
#include "optimizer/geqo.h"


! extern Pool *alloc_pool(PlannerInfo *root, int pool_size, int string_length);
! extern void free_pool(PlannerInfo *root, Pool *pool);

! extern void random_init_pool(PlannerInfo *root, Pool *pool);
! extern Chromosome *alloc_chromo(PlannerInfo *root, int string_length);
! extern void free_chromo(PlannerInfo *root, Chromosome *chromo);

! extern void spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool);

! extern void sort_pool(PlannerInfo *root, Pool *pool);

#endif /* GEQO_POOL_H */
diff --git a/src/include/optimizer/geqo_random.h b/src/include/optimizer/geqo_random.h
index fab0728..6fcfa7f 100644
*** a/src/include/optimizer/geqo_random.h
--- b/src/include/optimizer/geqo_random.h
***************
*** 27,38 ****
#include <math.h>

/* geqo_rand returns a random float value between 0 and 1 inclusive */
!
! #define geqo_rand() ((double) random() / (double) MAX_RANDOM_VALUE)

/* geqo_randint returns integer value between lower and upper inclusive */
!
! #define geqo_randint(upper,lower) \
! ( (int) floor( geqo_rand()*(((upper)-(lower))+0.999999) ) + (lower) )

#endif /* GEQO_RANDOM_H */
--- 27,37 ----
#include <math.h>

/* geqo_rand returns a random float value between 0 and 1 inclusive */
! double geqo_rand(PlannerInfo *root);
! void geqo_seed(PlannerInfo *root, double);

/* geqo_randint returns integer value between lower and upper inclusive */
! #define geqo_randint(root, upper,lower) \
! ( (int) floor( geqo_rand(root)*(((upper)-(lower))+0.999999) ) + (lower) )

#endif /* GEQO_RANDOM_H */
diff --git a/src/include/optimizer/geqo_recombination.h b/src/include/optimizer/geqo_recombination.h
index 2c4a338..2484259 100644
*** a/src/include/optimizer/geqo_recombination.h
--- b/src/include/optimizer/geqo_recombination.h
***************
*** 24,32 ****
#ifndef GEQO_RECOMBINATION_H
#define GEQO_RECOMBINATION_H

#include "optimizer/geqo_gene.h"

! extern void init_tour(Gene *tour, int num_gene);


/* edge recombination crossover [ERX] */
--- 24,33 ----
#ifndef GEQO_RECOMBINATION_H
#define GEQO_RECOMBINATION_H

+ #include "optimizer/geqo.h"
#include "optimizer/geqo_gene.h"

! extern void init_tour(PlannerInfo *root, Gene *tour, int num_gene);


/* edge recombination crossover [ERX] */
*************** typedef struct Edge
*** 38,49 ****
int unused_edges;
} Edge;

! extern Edge *alloc_edge_table(int num_gene);
! extern void free_edge_table(Edge *edge_table);

! extern float gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table);

! extern int gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene);


/* partially matched crossover [PMX] */
--- 39,52 ----
int unused_edges;
} Edge;

! extern Edge *alloc_edge_table(PlannerInfo *root, int num_gene);
! extern void free_edge_table(PlannerInfo *root, Edge *edge_table);

! extern float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
! int num_gene, Edge *edge_table);

! extern int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene,
! int num_gene);


/* partially matched crossover [PMX] */
*************** extern int gimme_tour(Edge *edge_table,
*** 51,57 ****
#define DAD 1 /* indicator for gene from dad */
#define MOM 0 /* indicator for gene from mom */

! extern void pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene);


typedef struct City
--- 54,62 ----
#define DAD 1 /* indicator for gene from dad */
#define MOM 0 /* indicator for gene from mom */

! extern void pmx(PlannerInfo *root,
! Gene *tour1, Gene *tour2,
! Gene *offspring, int num_gene);


typedef struct City
*************** typedef struct City
*** 62,80 ****
int select_list;
} City;

! extern City *alloc_city_table(int num_gene);
! extern void free_city_table(City *city_table);

/* cycle crossover [CX] */
! extern int cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table);

/* position crossover [PX] */
! extern void px(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table);

/* order crossover [OX1] according to Davis */
! extern void ox1(Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table);

/* order crossover [OX2] according to Syswerda */
! extern void ox2(Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table);

#endif /* GEQO_RECOMBINATION_H */
--- 67,89 ----
int select_list;
} City;

! extern City *alloc_city_table(PlannerInfo *root, int num_gene);
! extern void free_city_table(PlannerInfo *root, City *city_table);

/* cycle crossover [CX] */
! extern int cx(PlannerInfo *root, Gene *tour1, Gene *tour2,
! Gene *offspring, int num_gene, City *city_table);

/* position crossover [PX] */
! extern void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
! int num_gene, City *city_table);

/* order crossover [OX1] according to Davis */
! extern void ox1(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring,
! int num_gene, City *city_table);

/* order crossover [OX2] according to Syswerda */
! extern void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring,
! int num_gene, City *city_table);

#endif /* GEQO_RECOMBINATION_H */
diff --git a/src/include/optimizer/geqo_selection.h b/src/include/optimizer/geqo_selection.h
index 4b336d1..7e93cb4 100644
*** a/src/include/optimizer/geqo_selection.h
--- b/src/include/optimizer/geqo_selection.h
***************
*** 25,30 ****

#include "optimizer/geqo_gene.h"

! extern void geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias);

#endif /* GEQO_SELECTION_H */
--- 25,32 ----

#include "optimizer/geqo_gene.h"

! extern void geqo_selection(PlannerInfo *root,
! Chromosome *momma, Chromosome *daddy,
! Pool *pool, double bias);

#endif /* GEQO_SELECTION_H */
--
1.6.3.3.335.ge09a8

---
doc/src/sgml/config.sgml | 16 ++++++++++++++++
1 files changed, 16 insertions(+), 0 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 99d25d7..5d8eca9 100644
*** a/doc/src/sgml/config.sgml
--- b/doc/src/sgml/config.sgml
*************** archive_command = 'copy "%p" "C:\\server
*** 2150,2155 ****
--- 2150,2171 ----
</listitem>
</varlistentry>

+ <varlistentry id="guc-geqo-seed" xreflabel="geqo_seed">
+ <term><varname>geqo_seed</varname>
+ (<type>floating point</type>)</term>
+ <indexterm>
+ <primary><varname>geqo_seed</> configuration parameter</primary>
+ </indexterm>
+ <listitem>
+ <para>
+ Controls the initialization of the random number generator used
+ by GEQO to select random paths through the join order search space.
+ With the default setting of zero the join order planning is not repeatable.
+ For repeatable planning set a value between 0 (exclusive) and 1 (inclusive).
+ </para>
+ </listitem>
+ </varlistentry>
+
</variablelist>
</sect2>
<sect2 id="runtime-config-query-other">
--
1.6.3.3.335.ge09a8

On Tue, Jul 14, 2009 at 6:34 PM, Andres Freund<andres(at)anarazel(dot)de> wrote:
> ---
>  doc/src/sgml/config.sgml |   16 ++++++++++++++++
>  1 files changed, 16 insertions(+), 0 deletions(-)
>
> diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
> index 99d25d7..5d8eca9 100644
> *** a/doc/src/sgml/config.sgml
> --- b/doc/src/sgml/config.sgml
> *************** archive_command = 'copy "%p" "C:\\server
> *** 2150,2155 ****
> --- 2150,2171 ----
>        </listitem>
>       </varlistentry>
>
> +      <varlistentry id="guc-geqo-seed" xreflabel="geqo_seed">
> +       <term><varname>geqo_seed</varname>
> +       (<type>floating point</type>)</term>
> +       <indexterm>
> +        <primary><varname>geqo_seed</> configuration parameter</primary>
> +       </indexterm>
> +       <listitem>
> +        <para>
> +         Controls the initialization of the random number generator used
> +         by GEQO to select random paths through the join order search space.
> +         With the default setting of zero the join order planning is not repeatable.
> +         For repeatable planning set a value between 0 (exclusive) and 1 (inclusive).
> +        </para>
> +       </listitem>
> +      </varlistentry>
> +
>       </variablelist>
>      </sect2>
>       <sect2 id="runtime-config-query-other">
> --
> 1.6.3.3.335.ge09a8

I don't understand why people (including yourself, but you're not the
only one) have begun submitting relatively trivial patches in multiple
parts. This just creates multiple threads on the mailing list without
adding any value. The doc changes are part of the patch; one email
containing all the changes seems vastly preferable to me.

IMHO, the only reason for submitting multiple patches if it there are
pieces that are separately commitable.

...Robert

Hi,

On Wednesday 15 July 2009 04:14:16 Robert Haas wrote:
> On Tue, Jul 14, 2009 at 6:34 PM, Andres Freund<andres(at)anarazel(dot)de> wrote:
> > ---
> > doc/src/sgml/config.sgml | 16 ++++++++++++++++
> > 1 files changed, 16 insertions(+), 0 deletions(-)
> >
> > diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
> > index 99d25d7..5d8eca9 100644
> > *** a/doc/src/sgml/config.sgml
> > --- b/doc/src/sgml/config.sgml
> > *************** archive_command = 'copy "%p" "C:\\server
> > *** 2150,2155 ****
> > --- 2150,2171 ----
> > </listitem>
> > </varlistentry>
> >
> > + <varlistentry id="guc-geqo-seed" xreflabel="geqo_seed">
> > + <term><varname>geqo_seed</varname>
> > + (<type>floating point</type>)</term>
> > + <indexterm>
> > + <primary><varname>geqo_seed</> configuration parameter</primary>
> > + </indexterm>
> > + <listitem>
> > + <para>
> > + Controls the initialization of the random number generator used
> > + by GEQO to select random paths through the join order search
> > space. + With the default setting of zero the join order planning
> > is not repeatable. + For repeatable planning set a value between
> > 0 (exclusive) and 1 (inclusive). + </para>
> > + </listitem>
> > + </varlistentry>
> > +
> > </variablelist>
> > </sect2>
> > <sect2 id="runtime-config-query-other">
> > --
> > 1.6.3.3.335.ge09a8
>
> I don't understand why people (including yourself, but you're not the
> only one) have begun submitting relatively trivial patches in multiple
> parts. This just creates multiple threads on the mailing list without
> adding any value. The doc changes are part of the patch; one email
> containing all the changes seems vastly preferable to me.
For one reason it got easy. For another doing so - except the doc patch
admittedly - makes it potentially easier to bisect changes (Spent to much time
bisecting kernel problems I guess).
I also find it easier to read a patch when I know what kind of issues to
expect.
For example the patch adding erand48 should definitely be looked at on by
somebody with windows whereas the repetitious changes to GEQO itself do not
necessarily be tested on windows.

It should not create multiple threads I think as all messages were a response
the first mail?

> IMHO, the only reason for submitting multiple patches if it there are
> pieces that are separately commitable.
PG has rather coarse grained commits. I guess some people are not used to that
from their own experience anymore....

Andres

--On 15. Juli 2009 08:06:48 +0200 Andres Freund <andres(at)anarazel(dot)de> wrote:

> It should not create multiple threads I think as all messages were a
> response the first mail?

It does (at least my MUA understood that correctly), but since many people
are reading in a "backlog"-style manner, i have to agree with Robert. It
makes it a little bit harder to track all changes which are intended by a
specific discussion.

--
Thanks

Bernd

On Wed, Jul 15, 2009 at 10:13 AM, Bernd Helmle<mailings(at)oopsware(dot)de> wrote:
> --On 15. Juli 2009 08:06:48 +0200 Andres Freund <andres(at)anarazel(dot)de> wrote:
>
>> It should not create multiple threads I think as all messages were a
>> response  the first mail?
>
> It does (at least my MUA understood that correctly), but since many people
> are reading in a "backlog"-style manner, i have to agree with Robert. It
> makes it a little bit harder to track all changes which are intended by a
> specific discussion.

Gmail starts a new thread if the subject line is changed, but I'm not
going to hold the entire world hostage to my preferred email client.
There are other problems, too, like if I want to apply this patch I
have to download multiple emails to do it, and multiple links have to
be added to the CommitFest app to reference the different parts.

...Robert

On Wednesday 15 July 2009 19:01:05 Robert Haas wrote:
> On Wed, Jul 15, 2009 at 10:13 AM, Bernd Helmle<mailings(at)oopsware(dot)de> wrote:
> > --On 15. Juli 2009 08:06:48 +0200 Andres Freund <andres(at)anarazel(dot)de>
wrote:
> >> It should not create multiple threads I think as all messages were a
> >> response the first mail?
> > It does (at least my MUA understood that correctly), but since many
> > people are reading in a "backlog"-style manner, i have to agree with
> > Robert. It makes it a little bit harder to track all changes which are
> > intended by a specific discussion.
For me its easier, as the different discussions are kept separate...

> Gmail starts a new thread if the subject line is changed, but I'm not
> going to hold the entire world hostage to my preferred email client.
> There are other problems, too, like if I want to apply this patch I
> have to download multiple emails to do it, and multiple links have to
> be added to the CommitFest app to reference the different parts.
Referencing the top Mail seems enough for me. To apply patches from mail I
have setup a filter which can apply an mbox directly...

But as patches I send are not intended to be consumed by me, I will stop
sending patches like that ;-)

Andres

PS: Gmail is a strange beast.

Andres Freund <andres(at)anarazel(dot)de> writes:
> Query planning via GEQO currently can yield a different plan on every
> invokation of the planner due to its non-exhaustive nature.
> This often can be inconvenient because at times there may be a very
> bad plan. It also makes it very hard to reproduce a problem with GEQO.

Applied with some editorialization. Mainly, I didn't see the point of
preserving the ability to have nondeterministic planning, and I
especially didn't care for having that still be the default behavior.
So I just made it unconditionally initialize the seed. It would of
course take only minor tweaking to do things differently.

regards, tom lane

On Thursday 16 July 2009 23:04:58 Tom Lane wrote:
> Andres Freund <andres(at)anarazel(dot)de> writes:
> > Query planning via GEQO currently can yield a different plan on every
> > invokation of the planner due to its non-exhaustive nature.
> > This often can be inconvenient because at times there may be a very
> > bad plan. It also makes it very hard to reproduce a problem with GEQO.
>
> Applied with some editorialization. Mainly, I didn't see the point of
> preserving the ability to have nondeterministic planning, and I
> especially didn't care for having that still be the default behavior.
> So I just made it unconditionally initialize the seed. It would of
> course take only minor tweaking to do things differently.
Nice.
Mainly I did not have the guts to change the behaviour completely...

archive.org has a copy of the dead link to the comp.ai.genetic FAQ linked at
http://web.archive.org/web/20051226001402/http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/www/location.htm
which is the same as the one referenced by alvaro in
http://archives.postgresql.org/pgsql-docs/2009-07/msg00004.php

If considerered relevant enough, you can update the link...

Andres