aboutsummaryrefslogtreecommitdiff
path: root/src/backend/optimizer/geqo/geqo_main.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_main.c')
-rw-r--r--src/backend/optimizer/geqo/geqo_main.c249
1 files changed, 131 insertions, 118 deletions
diff --git a/src/backend/optimizer/geqo/geqo_main.c b/src/backend/optimizer/geqo/geqo_main.c
index 4b450002885..eab939c03e6 100644
--- a/src/backend/optimizer/geqo/geqo_main.c
+++ b/src/backend/optimizer/geqo/geqo_main.c
@@ -1,21 +1,21 @@
/*------------------------------------------------------------------------
*
* geqo_main.c--
- * solution of the query optimization problem
- * by means of a Genetic Algorithm (GA)
+ * solution of the query optimization problem
+ * by means of a Genetic Algorithm (GA)
*
* Copyright (c) 1994, Regents of the University of California
*
- * $Id: geqo_main.c,v 1.3 1997/03/14 16:02:51 scrappy Exp $
+ * $Id: geqo_main.c,v 1.4 1997/09/07 04:43:09 momjian Exp $
*
*-------------------------------------------------------------------------
*/
/* contributed by:
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
- * Martin Utesch * Institute of Automatic Control *
- = = University of Mining and Technology =
- * utesch@aut.tu-freiberg.de * Freiberg, Germany *
+ * Martin Utesch * Institute of Automatic Control *
+ = = University of Mining and Technology =
+ * utesch@aut.tu-freiberg.de * Freiberg, Germany *
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
*/
@@ -48,228 +48,241 @@
/* define edge recombination crossover [ERX] per default */
#if !defined(ERX) && \
- !defined(PMX) && \
- !defined(CX) && \
- !defined(PX) && \
- !defined(OX1) && \
- !defined(OX2)
+ !defined(PMX) && \
+ !defined(CX) && \
+ !defined(PX) && \
+ !defined(OX1) && \
+ !defined(OX2)
#define ERX
#endif
/*
* geqo--
- * solution of the query optimization problem
- * similar to a constrained Traveling Salesman Problem (TSP)
+ * solution of the query optimization problem
+ * similar to a constrained Traveling Salesman Problem (TSP)
*/
-Rel *
-geqo(Query *root)
+Rel *
+geqo(Query * root)
{
- int generation;
- Chromosome *momma;
- Chromosome *daddy;
- Chromosome *kid;
+ int generation;
+ Chromosome *momma;
+ Chromosome *daddy;
+ Chromosome *kid;
#if defined(ERX)
- Edge *edge_table; /* list of edges */
- int edge_failures=0;
- float difference;
-#endif
+ Edge *edge_table; /* list of edges */
+ int edge_failures = 0;
+ float difference;
+
+#endif
#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
- City *city_table; /* list of cities */
+ City *city_table; /* list of cities */
+
#endif
#if defined(CX)
- int cycle_diffs=0;
- int mutations=0;
+ int cycle_diffs = 0;
+ int mutations = 0;
+
#endif
- int number_of_rels;
+ int number_of_rels;
- Pool *pool;
- int pool_size, number_generations, status_interval;
+ Pool *pool;
+ int pool_size,
+ number_generations,
+ status_interval;
- Gene *best_tour;
- Rel *best_rel;
-/* Plan *best_plan; */
+ Gene *best_tour;
+ Rel *best_rel;
+
+/* Plan *best_plan; */
/* set tour size */
- number_of_rels = length(root->base_relation_list_);
+ number_of_rels = length(root->base_relation_list_);
/* set GA parameters */
- geqo_params(number_of_rels) ; /* out of "$PGDATA/pg_geqo" file */
- pool_size = PoolSize;
- number_generations = Generations;
- status_interval = 10;
+ geqo_params(number_of_rels);/* out of "$PGDATA/pg_geqo" file */
+ pool_size = PoolSize;
+ number_generations = Generations;
+ status_interval = 10;
/* seed random number generator */
- srandom(RandomSeed);
+ srandom(RandomSeed);
/* allocate genetic pool memory */
- pool = alloc_pool(pool_size, number_of_rels);
+ pool = alloc_pool(pool_size, number_of_rels);
/* random initialization of the pool */
- random_init_pool (root, pool, 0, pool->size);
+ random_init_pool(root, pool, 0, pool->size);
/* 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 ) */
+ 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
+ * ) */
/* allocate chromosome momma and daddy memory */
- momma = alloc_chromo(pool->string_length);
- daddy = alloc_chromo(pool->string_length);
+ momma = alloc_chromo(pool->string_length);
+ daddy = alloc_chromo(pool->string_length);
#if defined (ERX)
- elog(DEBUG,"geqo_main: using edge recombination crossover [ERX]");
+ elog(DEBUG, "geqo_main: using edge recombination crossover [ERX]");
/* allocate edge table memory */
- edge_table = alloc_edge_table(pool->string_length);
+ edge_table = alloc_edge_table(pool->string_length);
#elif defined(PMX)
- elog(DEBUG,"geqo_main: using partially matched crossover [PMX]");
+ elog(DEBUG, "geqo_main: using partially matched crossover [PMX]");
/* allocate chromosome kid memory */
- kid = alloc_chromo(pool->string_length);
+ kid = alloc_chromo(pool->string_length);
#elif defined(CX)
- elog(DEBUG,"geqo_main: using cycle crossover [CX]");
+ elog(DEBUG, "geqo_main: using cycle crossover [CX]");
/* allocate city table memory */
- kid = alloc_chromo(pool->string_length);
- city_table = alloc_city_table(pool->string_length);
+ kid = alloc_chromo(pool->string_length);
+ city_table = alloc_city_table(pool->string_length);
#elif defined(PX)
- elog(DEBUG,"geqo_main: using position crossover [PX]");
+ elog(DEBUG, "geqo_main: using position crossover [PX]");
/* allocate city table memory */
- kid = alloc_chromo(pool->string_length);
- city_table = alloc_city_table(pool->string_length);
+ kid = alloc_chromo(pool->string_length);
+ city_table = alloc_city_table(pool->string_length);
#elif defined(OX1)
- elog(DEBUG,"geqo_main: using order crossover [OX1]");
+ elog(DEBUG, "geqo_main: using order crossover [OX1]");
/* allocate city table memory */
- kid = alloc_chromo(pool->string_length);
- city_table = alloc_city_table(pool->string_length);
+ kid = alloc_chromo(pool->string_length);
+ city_table = alloc_city_table(pool->string_length);
#elif defined(OX2)
- elog(DEBUG,"geqo_main: using order crossover [OX2]");
+ elog(DEBUG, "geqo_main: using order crossover [OX2]");
/* allocate city table memory */
- kid = alloc_chromo(pool->string_length);
- city_table = alloc_city_table(pool->string_length);
+ kid = alloc_chromo(pool->string_length);
+ city_table = alloc_city_table(pool->string_length);
#endif
/* my pain main part: */
/* iterative optimization */
- for (generation = 0; generation < number_generations; generation++) {
+ for (generation = 0; generation < number_generations; generation++)
+ {
- /* SELECTION */
- geqo_selection(momma, daddy, pool, SelectionBias); /* using linear bias function */
+ /* SELECTION */
+ geqo_selection(momma, daddy, pool, SelectionBias); /* using linear bias
+ * function */
#if defined (ERX)
- /* EDGE RECOMBINATION CROSSOVER */
- difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);
+ /* EDGE RECOMBINATION CROSSOVER */
+ difference = gimme_edge_table(momma->string, daddy->string, pool->string_length, edge_table);
- /* let the kid grow in momma's womb (storage) for nine months ;-) */
- /* sleep(23328000) -- har har har */
- kid = momma;
+ /* let the kid grow in momma's womb (storage) for nine months ;-) */
+ /* sleep(23328000) -- har har har */
+ kid = momma;
- /* are there any edge failures ? */
- edge_failures += gimme_tour(edge_table, kid->string, pool->string_length);
+ /* 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);
+ /* 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);
- }
+ /* 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);
+ /* 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);
+ /* 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);
+ /* ORDER CROSSOVER */
+ ox2(momma->string, daddy->string, kid->string, pool->string_length, city_table);
#endif
- /* EVALUATE FITNESS */
- kid->worth = geqo_eval (root, kid->string, pool->string_length);
+ /* 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 (kid, pool);
+ /* push the kid into the wilderness of life according to its worth */
+ spread_chromo(kid, pool);
#ifdef GEQO_DEBUG
- if (status_interval && !(generation % status_interval))
- print_gen (stdout, pool, generation);
+ if (status_interval && !(generation % status_interval))
+ print_gen(stdout, pool, generation);
#endif
- } /* end of iterative optimization */
+ } /* end of iterative optimization */
#if defined(ERX) && defined(GEQO_DEBUG)
-if (edge_failures != 0)
- fprintf (stdout, "\nFailures: %d Avg: %d\n", edge_failures, (int) generation/edge_failures);
+ if (edge_failures != 0)
+ fprintf(stdout, "\nFailures: %d Avg: %d\n", edge_failures, (int) generation / edge_failures);
-else fprintf (stdout, "No edge failures detected.\n");
+ else
+ fprintf(stdout, "No edge failures detected.\n");
#endif
#if defined(CX) && defined(GEQO_DEBUG)
-if (mutations != 0)
- fprintf (stdout, "\nMutations: %d Generations: %d\n", mutations, generation);
+ if (mutations != 0)
+ fprintf(stdout, "\nMutations: %d Generations: %d\n", mutations, generation);
-else fprintf (stdout, "No mutations processed.\n");
+ else
+ fprintf(stdout, "No mutations processed.\n");
#endif
-
+
#ifdef GEQO_DEBUG
-fprintf (stdout, "\n");
-print_pool (stdout, pool, 0, pool_size-1);
+ fprintf(stdout, "\n");
+ print_pool(stdout, pool, 0, pool_size - 1);
#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_tour = (Gene *) pool->data[0].string;
/* root->join_relation_list_ will be modified during this ! */
-best_rel = (Rel *) gimme_tree(root, best_tour, 0, pool->string_length, NULL);
+ best_rel = (Rel *) gimme_tree(root, best_tour, 0, pool->string_length, NULL);
/* DBG: show the query plan
print_plan(best_plan, root);
DBG */
/* ... free memory stuff */
-free_chromo(momma);
-free_chromo(daddy);
+ free_chromo(momma);
+ free_chromo(daddy);
#if defined (ERX)
-free_edge_table(edge_table);
+ free_edge_table(edge_table);
#elif defined(PMX)
-free_chromo(kid);
+ free_chromo(kid);
#elif defined(CX)
-free_chromo(kid);
-free_city_table(city_table);
+ free_chromo(kid);
+ free_city_table(city_table);
#elif defined(PX)
-free_chromo(kid);
-free_city_table(city_table);
+ free_chromo(kid);
+ free_city_table(city_table);
#elif defined(OX1)
-free_chromo(kid);
-free_city_table(city_table);
+ free_chromo(kid);
+ free_city_table(city_table);
#elif defined(OX2)
-free_chromo(kid);
-free_city_table(city_table);
+ free_chromo(kid);
+ free_city_table(city_table);
#endif
-free_pool(pool);
+ free_pool(pool);
-return(best_rel);
+ return (best_rel);
}
-
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-24 11:14:02 +0000