diff options
Diffstat (limited to 'src/backend/optimizer/geqo')
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_copy.c | 40 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_cx.c | 132 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_erx.c | 567 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_eval.c | 985 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_main.c | 249 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_misc.c | 347 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_mutation.c | 65 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_ox1.c | 122 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_ox2.c | 146 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_params.c | 268 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_paths.c | 190 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_pmx.c | 281 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_pool.c | 301 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_px.c | 121 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_recombination.c | 93 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/geqo_selection.c | 88 | ||||
| -rw-r--r-- | src/backend/optimizer/geqo/minspantree.c | 317 |
17 files changed, 2300 insertions, 2012 deletions
diff --git a/src/backend/optimizer/geqo/geqo_copy.c b/src/backend/optimizer/geqo/geqo_copy.c index 3356f8d5475..4c35f99f9f5 100644 --- a/src/backend/optimizer/geqo/geqo_copy.c +++ b/src/backend/optimizer/geqo/geqo_copy.c @@ -4,32 +4,32 @@ * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_copy.c,v 1.1 1997/02/19 12:56:40 scrappy Exp $ + * $Id: geqo_copy.c,v 1.2 1997/09/07 04:43:01 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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" @@ -52,16 +52,16 @@ /* geqo_copy-- * - * copies one gene to another + * copies one gene to another * */ void -geqo_copy (Chromosome *chromo1, Chromosome *chromo2, int string_length) +geqo_copy(Chromosome * chromo1, Chromosome * chromo2, int string_length) { - int i; + int i; - for (i=0; i<string_length; i++) - chromo1->string[i] = chromo2->string[i]; + for (i = 0; i < string_length; i++) + chromo1->string[i] = chromo2->string[i]; - chromo1->worth = chromo2->worth; + chromo1->worth = chromo2->worth; } diff --git a/src/backend/optimizer/geqo/geqo_cx.c b/src/backend/optimizer/geqo/geqo_cx.c index a3aa6fce4f4..dfde1bdc530 100644 --- a/src/backend/optimizer/geqo/geqo_cx.c +++ b/src/backend/optimizer/geqo/geqo_cx.c @@ -2,35 +2,35 @@ * * geqo_cx.c-- * -* cycle crossover [CX] routines; -* CX operator according to Oliver et al -* (Proc 2nd Int'l Conf on GA's) +* cycle crossover [CX] routines; +* CX operator according to Oliver et al +* (Proc 2nd Int'l Conf on GA's) * -* $Id: geqo_cx.c,v 1.1 1997/02/19 12:56:48 scrappy Exp $ +* $Id: geqo_cx.c,v 1.2 1997/09/07 04:43:02 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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. */ +/* */ /*************************************************************/ @@ -57,73 +57,81 @@ /* cx-- * - * cycle crossover + * cycle crossover */ int -cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table) +cx(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; + 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; - } + /* 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(num_gene - 1, 0); + /* choose random cycle starting position */ + start_pos = geqo_randint(num_gene - 1, 0); - /* child inherits first city */ - offspring[start_pos] = tour1[start_pos]; + /* 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; + /* begin cycle with tour1 */ + curr_pos = start_pos; + city_table[(int) tour1[start_pos]].used = 1; - count++; + count++; - /* cx main part */ + /* 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++; - } + 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++; - } - } - } + /* 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) { + /* 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++; + /* 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); - } + } + return (num_diffs); +} diff --git a/src/backend/optimizer/geqo/geqo_erx.c b/src/backend/optimizer/geqo/geqo_erx.c index 8c3c63d755c..9d0f93efe8c 100644 --- a/src/backend/optimizer/geqo/geqo_erx.c +++ b/src/backend/optimizer/geqo/geqo_erx.c @@ -1,33 +1,33 @@ /*------------------------------------------------------------------------ * * geqo_erx.c-- -* edge recombination crossover [ER] +* edge recombination crossover [ER] * -* $Id: geqo_erx.c,v 1.2 1997/06/06 00:37:23 scrappy Exp $ +* $Id: geqo_erx.c,v 1.3 1997/09/07 04:43:04 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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. */ +/* */ /*************************************************************/ @@ -52,384 +52,441 @@ #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 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); +static Gene edge_failure(Gene * gene, int index, Edge * edge_table, int num_gene); /* alloc_edge_table-- * - * allocate memory for edge table + * allocate memory for edge table * */ -Edge * +Edge * alloc_edge_table(int num_gene) { - Edge *edge_table; + Edge *edge_table; - /* palloc one extra location so that nodes numbered - 1..n can be indexed directly; 0 will not be used */ + /* + * 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)); + edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge)); - return (edge_table); - } + return (edge_table); +} /* free_edge_table-- * - * deallocate memory of edge table + * deallocate memory of edge table * */ - void - free_edge_table(Edge *edge_table) - { - pfree(edge_table); - } +void +free_edge_table(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 + * fills a data structure which represents the set of explicit + * edges between points in the (2) input genes + * + * assumes circular tours and bidirectional edges * - * assumes circular tours and bidirectional edges - * - * gimme_edge() will set "shared" edges to negative values + * 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 + * returns average number edges/city in range 2.0 - 4.0 + * where 2.0=homogeneous; 4.0=diverse * */ float -gimme_edge_table (Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table) +gimme_edge_table(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; + 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 */ + /* fill edge table with new data */ - edge_total = 0; + edge_total = 0; - for (index1 = 0; index1 < num_gene; index1++) { + for (index1 = 0; index1 < num_gene; index1++) + { - /* presume the tour is circular, i.e. 1->2, 2->3, 3->1 - this operaton maps n back to 1 */ + /* + * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this + * operaton maps n back to 1 + */ - index2 = (index1 + 1) % num_gene; + index2 = (index1 + 1) % num_gene; - /* edges are bidirectional, i.e. 1->2 is same as 2->1 - call gimme_edge twice per edge */ + /* + * edges are bidirectional, i.e. 1->2 is same as 2->1 call + * gimme_edge 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(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); - } + 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 */ - return (((float) (edge_total * 2)/ (float) num_gene)); + /* 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 + * registers edge from city1 to city2 in input edge table * - * no assumptions about directionality are made; - * therefor 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) + * no assumptions about directionality are made; + * therefor 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 + * 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 (Gene gene1, Gene gene2, Edge *edge_table) +gimme_edge(Gene gene1, Gene gene2, Edge * edge_table) { - int i; - int edges; - int city1 = (int) gene1; - int city2 = (int) gene2; + 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; + /* 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) { + 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; + /* mark shared edges as negative */ + edge_table[city1].edge_list[i] = 0 - city2; - return (0); - } - } + return (0); + } + } - /* add city1->city2; */ - edge_table[city1].edge_list[edges] = city2; + /* 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++; + /* increment the number of edges from city1 */ + edge_table[city1].total_edges++; + edge_table[city1].unused_edges++; - return (1); + 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.) + * 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 (Edge *edge_table, Gene *new_gene, int num_gene) +gimme_tour(Edge * edge_table, Gene * new_gene, int num_gene) { - int i; - int edge_failures=0; + int i; + int edge_failures = 0; - new_gene[0] = (Gene) geqo_randint(num_gene, 1); /* choose int between 1 and num_gene */ + new_gene[0] = (Gene) geqo_randint(num_gene, 1); /* choose int between 1 + * and num_gene */ - for (i=1; i<num_gene; i++) { - - /* as each point is entered into the tour, - remove it from the edge table */ + for (i = 1; i < num_gene; i++) + { - remove_gene(new_gene[i-1], edge_table[(int) new_gene[i-1]], edge_table); - - /* find destination for the newly entered point */ + /* + * as each point is entered into the tour, remove it from the edge + * table + */ - if (edge_table[new_gene[i-1]].unused_edges > 0) { - new_gene[i] = gimme_gene(edge_table[(int) new_gene[i-1]], edge_table); - } + remove_gene(new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table); - else { /* cope with fault */ - edge_failures++; + /* find destination for the newly entered point */ - new_gene[i] = edge_failure(new_gene, i-1, edge_table, num_gene); - } + if (edge_table[new_gene[i - 1]].unused_edges > 0) + { + new_gene[i] = gimme_gene(edge_table[(int) new_gene[i - 1]], edge_table); + } - /* mark this node as incorporated */ - edge_table[(int) new_gene[i-1]].unused_edges = -1; + else + { /* cope with fault */ + edge_failures++; - } /* for (i=1; i<num_gene; i++) */ + new_gene[i] = edge_failure(new_gene, i - 1, edge_table, num_gene); + } -return(edge_failures); + /* 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. + * removes input gene from edge_table. + * input edge is used + * to identify deletion locations within edge table. * */ static void -remove_gene (Gene gene, Edge edge, Edge *edge_table) +remove_gene(Gene gene, Edge edge, Edge * edge_table) { - int i,j; - int possess_edge; - int genes_remaining; + 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) */ + /* + * 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; + 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++) { + /* 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) { + if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene) + { - edge_table[possess_edge].unused_edges--; + edge_table[possess_edge].unused_edges--; - edge_table[possess_edge].edge_list[j] = - edge_table[possess_edge].edge_list[genes_remaining-1]; + edge_table[possess_edge].edge_list[j] = + edge_table[possess_edge].edge_list[genes_remaining - 1]; - break; - } + break; + } } - } + } } /* gimme_gene-- * - * priority is given to "shared" edges - * (i.e. edges which both genes possess) + * priority is given to "shared" edges + * (i.e. edges which both genes possess) * */ -static Gene -gimme_gene (Edge edge, Edge *edge_table) +static Gene +gimme_gene(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 cadidate 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; + 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 cadidate 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(WARN, "gimme_gene: Internal error - minimum_count not set"); - else - if (edge_table[(int) friend].unused_edges == minimum_edges) - minimum_count++; + else if (minimum_count == -1) + elog(WARN, "gimme_gene: Internal 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++) */ - } /* for (i=0; i<edge.unused_edges; i++) */ - - /* random decision of the possible candidates to use */ - rand_decision = (int) geqo_randint(minimum_count-1, 0); + /* 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++) { - friend = (Gene) edge.edge_list[i]; - /* return the chosen candidate point */ - if (edge_table[(int) friend].unused_edges == minimum_edges) { - minimum_count--; + for (i = 0; i < edge.unused_edges; i++) + { + friend = (Gene) edge.edge_list[i]; - if ( minimum_count == rand_decision ) return (friend); + /* 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(WARN,"gimme_gene: neither shared nor minimum number nor random edge found"); - return 0; /* to keep the compiler quiet */ + /* ... should never be reached */ + elog(WARN, "gimme_gene: neither shared nor minimum number nor random edge found"); + return 0; /* to keep the compiler quiet */ } /* edge_failure-- * - * routine for handling edge failure + * routine for handling edge failure * */ -static Gene -edge_failure (Gene *gene, int index, Edge *edge_table, int num_gene) +static Gene +edge_failure(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++; - } - } + 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 */ + /* + * random decision of the gene with remaining edges and whose + * total_edges == 4 + */ - if (four_count != 0 ) { + if (four_count != 0) + { - rand_decision = (int) geqo_randint(four_count-1, 0); + rand_decision = (int) geqo_randint(four_count - 1, 0); - for (i=1; i<=num_gene; i++) { + for (i = 1; i <= num_gene; i++) + { - if ((Gene) i != fail_gene && + if ((Gene) i != fail_gene && edge_table[i].unused_edges != -1 && - edge_table[i].total_edges==4) { + edge_table[i].total_edges == 4) + { four_count--; - if (rand_decision == four_count) return ((Gene) i); - } + if (rand_decision == four_count) + return ((Gene) i); } + } - elog(DEBUG,"edge_failure(1): no edge found via random decision and total_edges == 4"); + elog(DEBUG, "edge_failure(1): no edge found via random decision and total_edges == 4"); } - else /* random decision of the gene with remaining edges */ + else +/* random decision of the gene with remaining edges */ - if (remaining_edges != 0) { + if (remaining_edges != 0) + { - rand_decision = (int) geqo_randint(remaining_edges-1, 0); + rand_decision = (int) geqo_randint(remaining_edges - 1, 0); - for (i=1; i<=num_gene; i++) { + for (i = 1; i <= num_gene; i++) + { - if ((Gene) i != fail_gene && - edge_table[i].unused_edges != -1) { + if ((Gene) i != fail_gene && + edge_table[i].unused_edges != -1) + { remaining_edges--; - if (rand_decision == remaining_edges) return (i); - } + if (rand_decision == remaining_edges) + return (i); } - - elog(DEBUG,"edge_failure(2): no edge found via random decision and remainig 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 */ + elog(DEBUG, "edge_failure(2): no edge found via random decision and remainig edges"); + } - else { /* occurs only at the last point in the tour; - simply look for the point which is not yet used */ + /* + * 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 + */ - for (i=1; i<=num_gene; i++) - if (edge_table[i].unused_edges >= 0) - return ((Gene) i); - - elog(DEBUG,"edge_failure(3): no edge found via looking for the last ununsed point"); + 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(DEBUG, "edge_failure(3): no edge found via looking for the last ununsed point"); } /* ... should never be reached */ - elog(WARN,"edge_failure: no edge detected"); - return 0; /* to keep the compiler quiet */ + elog(WARN, "edge_failure: no edge detected"); + return 0; /* to keep the compiler quiet */ } - diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 7ec449f2e94..ba34d8f3e02 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -1,20 +1,20 @@ /*------------------------------------------------------------------------ * * geqo_eval.c-- - * Routines to evaluate query trees + * Routines to evaluate query trees * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_eval.c,v 1.12 1997/08/12 22:53:07 momjian Exp $ + * $Id: geqo_eval.c,v 1.13 1997/09/07 04:43:06 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ @@ -22,13 +22,13 @@ #include <math.h> #ifdef HAVE_LIMITS_H -# include <limits.h> -# ifndef MAXINT -# define MAXINT INT_MAX -# endif +#include <limits.h> +#ifndef MAXINT +#define MAXINT INT_MAX +#endif #else -# include <values.h> -#endif +#include <values.h> +#endif #include "nodes/pg_list.h" #include "nodes/relation.h" @@ -50,548 +50,598 @@ #include "optimizer/geqo_paths.h" -static List *gimme_clause_joins(Query *root, Rel *outer_rel, Rel *inner_rel); -static Rel *gimme_clauseless_join(Rel *outer_rel, Rel *inner_rel); -static Rel *init_join_rel(Rel *outer_rel, Rel *inner_rel, JInfo *joininfo); -static List *new_join_tlist(List *tlist, List *other_relids, int first_resdomno); -static List *new_joininfo_list(List *joininfo_list, List *join_relids); -static void geqo_joinrel_size(Rel *joinrel, Rel *outer_rel, Rel *inner_rel); -static Rel *geqo_nth(int stop, List *rels); +static List *gimme_clause_joins(Query * root, Rel * outer_rel, Rel * inner_rel); +static Rel *gimme_clauseless_join(Rel * outer_rel, Rel * inner_rel); +static Rel *init_join_rel(Rel * outer_rel, Rel * inner_rel, JInfo * joininfo); +static List *new_join_tlist(List * tlist, List * other_relids, int first_resdomno); +static List *new_joininfo_list(List * joininfo_list, List * join_relids); +static void geqo_joinrel_size(Rel * joinrel, Rel * outer_rel, Rel * inner_rel); +static Rel *geqo_nth(int stop, List * rels); -/* +/* * geqo_eval-- - * + * * Returns cost of a query tree as an individual of the population. */ Cost -geqo_eval (Query *root, Gene *tour, int num_gene) +geqo_eval(Query * root, Gene * tour, int num_gene) { - Rel *joinrel; - Cost fitness; - List *temp; + Rel *joinrel; + Cost fitness; + List *temp; /* remember root->join_relation_list_ ... */ /* because root->join_relation_list_ will be changed during the following */ - temp = listCopy(root->join_relation_list_); + temp = listCopy(root->join_relation_list_); /* joinrel is readily processed query tree -- left-sided ! */ - joinrel = gimme_tree(root, tour, 0, num_gene, NULL); + joinrel = gimme_tree(root, tour, 0, num_gene, NULL); /* compute fitness */ - fitness = (Cost) joinrel->cheapestpath->path_cost; + fitness = (Cost) joinrel->cheapestpath->path_cost; - root->join_relation_list_ = listCopy(temp); + root->join_relation_list_ = listCopy(temp); - pfree(joinrel); - freeList(temp); + pfree(joinrel); + freeList(temp); - return(fitness); + return (fitness); } -/* +/* * gimme-tree -- - * this program presumes that only LEFT-SIDED TREES are considered! - * + * this program presumes that only LEFT-SIDED TREES are considered! + * * 'outer_rel' is the preceeding join - * + * * Returns a new join relation incorporating all joins in a left-sided tree. */ -Rel * -gimme_tree (Query *root, Gene *tour, int rel_count, int num_gene, Rel *outer_rel) +Rel * +gimme_tree(Query * root, Gene * tour, int rel_count, int num_gene, Rel * outer_rel) { - Rel *inner_rel; /* current relation */ - int base_rel_index; + Rel *inner_rel; /* current relation */ + int base_rel_index; - List *new_rels = NIL; - Rel *new_rel = NULL; + List *new_rels = NIL; + Rel *new_rel = NULL; - if (rel_count < num_gene ) { /* tree not yet finished */ + if (rel_count < num_gene) + { /* tree not yet finished */ - /* tour[0] = 3; tour[1] = 1; tour[2] = 2 */ - base_rel_index = (int) tour[rel_count]; + /* tour[0] = 3; tour[1] = 1; tour[2] = 2 */ + base_rel_index = (int) tour[rel_count]; - inner_rel = (Rel *) geqo_nth(base_rel_index,root->base_relation_list_); + inner_rel = (Rel *) geqo_nth(base_rel_index, root->base_relation_list_); - if (rel_count == 0) { /* processing first join with base_rel_index = (int) tour[0] */ - rel_count++; - return gimme_tree(root, tour, rel_count, num_gene, inner_rel); + if (rel_count == 0) + { /* processing first join with + * base_rel_index = (int) tour[0] */ + rel_count++; + return gimme_tree(root, tour, rel_count, num_gene, inner_rel); } - else { /* tree main part */ - - if(!(new_rels = gimme_clause_joins(root, outer_rel,inner_rel))) { - if (BushyPlanFlag) { - new_rels = lcons(gimme_clauseless_join(outer_rel,outer_rel),NIL); /* ??? MAU */ + else + { /* tree main part */ + + if (!(new_rels = gimme_clause_joins(root, outer_rel, inner_rel))) + { + if (BushyPlanFlag) + { + new_rels = lcons(gimme_clauseless_join(outer_rel, outer_rel), NIL); /* ??? MAU */ } - else { - new_rels = lcons(gimme_clauseless_join(outer_rel,inner_rel),NIL); + else + { + new_rels = lcons(gimme_clauseless_join(outer_rel, inner_rel), NIL); } } - /* process new_rel->pathlist */ - find_all_join_paths(root, new_rels); + /* process new_rel->pathlist */ + find_all_join_paths(root, new_rels); - /* prune new_rels */ - /* MAU: is this necessary? */ - /* what's the matter if more than one new rel is left till now? */ - /* joinrels in newrels with different ordering of relids are not possible */ - if (length(new_rels) > 1) new_rels = geqo_prune_rels(new_rels); + /* prune new_rels */ + /* MAU: is this necessary? */ - if (length(new_rels) > 1) { /* should never be reached ... */ - elog(DEBUG,"gimme_tree: still %d relations left", length(new_rels)); + /* + * what's the matter if more than one new rel is left till + * now? + */ + + /* + * joinrels in newrels with different ordering of relids are + * not possible + */ + if (length(new_rels) > 1) + new_rels = geqo_prune_rels(new_rels); + + if (length(new_rels) > 1) + { /* should never be reached ... */ + elog(DEBUG, "gimme_tree: still %d relations left", length(new_rels)); } - /* get essential new relation */ - new_rel = (Rel *) lfirst(new_rels); - rel_count++; + /* get essential new relation */ + new_rel = (Rel *) lfirst(new_rels); + rel_count++; - /* process new_rel->cheapestpath, new_rel->unorderedpath */ - geqo_rel_paths(new_rel); + /* process new_rel->cheapestpath, new_rel->unorderedpath */ + geqo_rel_paths(new_rel); - /* processing of other new_rel attributes */ - if ( new_rel->size <= 0 ) - new_rel->size = compute_rel_size(new_rel); - new_rel->width = compute_rel_width(new_rel); + /* processing of other new_rel attributes */ + if (new_rel->size <= 0) + new_rel->size = compute_rel_size(new_rel); + new_rel->width = compute_rel_width(new_rel); - root->join_relation_list_ = lcons(new_rel, NIL); + root->join_relation_list_ = lcons(new_rel, NIL); - return gimme_tree(root, tour, rel_count, num_gene, new_rel); + return gimme_tree(root, tour, rel_count, num_gene, new_rel); } } - return (outer_rel); /* tree finished ... */ + return (outer_rel); /* tree finished ... */ } -/* +/* * gimme-clause-joins-- * * 'outer-rel' is the relation entry for the outer relation * 'inner-rel' is the relation entry for the inner relation - * + * * Returns a list of new join relations. */ -static List * -gimme_clause_joins(Query *root, Rel *outer_rel, Rel *inner_rel) +static List * +gimme_clause_joins(Query * root, Rel * outer_rel, Rel * inner_rel) { - List *join_list = NIL; - List *i = NIL; - List *joininfo_list = (List *) outer_rel->joininfo; - - foreach (i, joininfo_list) { - JInfo *joininfo = (JInfo*)lfirst(i); - Rel *rel = NULL; - - if(!joininfo->inactive) { - List *other_rels = (List *)joininfo->otherrels; - - if(other_rels != NIL) { - if( (length(other_rels) == 1) ) { - - if( same(other_rels, inner_rel->relids) ) { /* look if inner_rel is it...*/ - rel = init_join_rel(outer_rel, inner_rel, joininfo); + List *join_list = NIL; + List *i = NIL; + List *joininfo_list = (List *) outer_rel->joininfo; + + foreach(i, joininfo_list) + { + JInfo *joininfo = (JInfo *) lfirst(i); + Rel *rel = NULL; + + if (!joininfo->inactive) + { + List *other_rels = (List *) joininfo->otherrels; + + if (other_rels != NIL) + { + if ((length(other_rels) == 1)) + { + + if (same(other_rels, inner_rel->relids)) + { /* look if inner_rel is it... */ + rel = init_join_rel(outer_rel, inner_rel, joininfo); } } - else if (BushyPlanFlag) { /* ?!? MAU */ - rel = init_join_rel(outer_rel, get_join_rel(root, other_rels), joininfo); - } - else { - rel = NULL; - } + else if (BushyPlanFlag) + { /* ?!? MAU */ + rel = init_join_rel(outer_rel, get_join_rel(root, other_rels), joininfo); + } + else + { + rel = NULL; + } - if (rel != NULL) - join_list = lappend(join_list, rel); + if (rel != NULL) + join_list = lappend(join_list, rel); } } } - return(join_list); + return (join_list); } -/* +/* * gimme-clauseless-join-- - * Given an outer relation 'outer-rel' and an inner relation - * 'inner-rel', create a join relation between 'outer-rel' and 'inner-rel' - * + * Given an outer relation 'outer-rel' and an inner relation + * 'inner-rel', create a join relation between 'outer-rel' and 'inner-rel' + * * Returns a new join relation. */ -static Rel * -gimme_clauseless_join(Rel *outer_rel, Rel *inner_rel) +static Rel * +gimme_clauseless_join(Rel * outer_rel, Rel * inner_rel) { - return(init_join_rel(outer_rel, inner_rel, (JInfo*)NULL)); + return (init_join_rel(outer_rel, inner_rel, (JInfo *) NULL)); } -/* +/* * init-join-rel-- - * Creates and initializes a new join relation. - * + * Creates and initializes a new join relation. + * * 'outer-rel' and 'inner-rel' are relation nodes for the relations to be - * joined + * joined * 'joininfo' is the joininfo node(join clause) containing both - * 'outer-rel' and 'inner-rel', if any exists - * + * 'outer-rel' and 'inner-rel', if any exists + * * Returns the new join relation node. */ -static Rel * -init_join_rel(Rel *outer_rel, Rel *inner_rel, JInfo *joininfo) +static Rel * +init_join_rel(Rel * outer_rel, Rel * inner_rel, JInfo * joininfo) { - Rel *joinrel = makeNode(Rel); - List *joinrel_joininfo_list = NIL; - List *new_outer_tlist; - List *new_inner_tlist; - - /* - * Create a new tlist by removing irrelevant elements from both - * tlists of the outer and inner join relations and then merging - * the results together. - */ - new_outer_tlist = - new_join_tlist(outer_rel->targetlist, /* XXX 1-based attnos */ - inner_rel->relids, 1); - new_inner_tlist = - new_join_tlist(inner_rel->targetlist, /* XXX 1-based attnos */ - outer_rel->relids, - length(new_outer_tlist) + 1); - - joinrel->relids = NIL; - joinrel->indexed = false; - joinrel->pages = 0; - joinrel->tuples = 0; - joinrel->width = 0; -/* joinrel->targetlist = NIL;*/ - joinrel->pathlist = NIL; - joinrel->unorderedpath = (Path *)NULL; - joinrel->cheapestpath = (Path *)NULL; - joinrel->pruneable = true; - joinrel->classlist = NULL; - joinrel->relam = InvalidOid; - joinrel->ordering = NULL; - joinrel->clauseinfo = NIL; - joinrel->joininfo = NULL; - joinrel->innerjoin = NIL; - joinrel->superrels = NIL; - - joinrel->relids = lcons(outer_rel->relids, lcons(inner_rel->relids, NIL)); - - new_outer_tlist = nconc(new_outer_tlist,new_inner_tlist); - joinrel->targetlist = new_outer_tlist; - - if (joininfo) { - joinrel->clauseinfo = joininfo->jinfoclauseinfo; - if (BushyPlanFlag) joininfo->inactive = true; - } - - joinrel_joininfo_list = - new_joininfo_list(append(outer_rel->joininfo, inner_rel->joininfo), - intAppend(outer_rel->relids, inner_rel->relids)); - - joinrel->joininfo = joinrel_joininfo_list; - - geqo_joinrel_size(joinrel, outer_rel, inner_rel); - - return(joinrel); + Rel *joinrel = makeNode(Rel); + List *joinrel_joininfo_list = NIL; + List *new_outer_tlist; + List *new_inner_tlist; + + /* + * Create a new tlist by removing irrelevant elements from both tlists + * of the outer and inner join relations and then merging the results + * together. + */ + new_outer_tlist = + new_join_tlist(outer_rel->targetlist, /* XXX 1-based attnos */ + inner_rel->relids, 1); + new_inner_tlist = + new_join_tlist(inner_rel->targetlist, /* XXX 1-based attnos */ + outer_rel->relids, + length(new_outer_tlist) + 1); + + joinrel->relids = NIL; + joinrel->indexed = false; + joinrel->pages = 0; + joinrel->tuples = 0; + joinrel->width = 0; +/* joinrel->targetlist = NIL;*/ + joinrel->pathlist = NIL; + joinrel->unorderedpath = (Path *) NULL; + joinrel->cheapestpath = (Path *) NULL; + joinrel->pruneable = true; + joinrel->classlist = NULL; + joinrel->relam = InvalidOid; + joinrel->ordering = NULL; + joinrel->clauseinfo = NIL; + joinrel->joininfo = NULL; + joinrel->innerjoin = NIL; + joinrel->superrels = NIL; + + joinrel->relids = lcons(outer_rel->relids, lcons(inner_rel->relids, NIL)); + + new_outer_tlist = nconc(new_outer_tlist, new_inner_tlist); + joinrel->targetlist = new_outer_tlist; + + if (joininfo) + { + joinrel->clauseinfo = joininfo->jinfoclauseinfo; + if (BushyPlanFlag) + joininfo->inactive = true; + } + + joinrel_joininfo_list = + new_joininfo_list(append(outer_rel->joininfo, inner_rel->joininfo), + intAppend(outer_rel->relids, inner_rel->relids)); + + joinrel->joininfo = joinrel_joininfo_list; + + geqo_joinrel_size(joinrel, outer_rel, inner_rel); + + return (joinrel); } -/* +/* * new-join-tlist-- - * Builds a join relations's target list by keeping those elements that - * will be in the final target list and any other elements that are still - * needed for future joins. For a target list entry to still be needed - * for future joins, its 'joinlist' field must not be empty after removal - * of all relids in 'other-relids'. - * + * Builds a join relations's target list by keeping those elements that + * will be in the final target list and any other elements that are still + * needed for future joins. For a target list entry to still be needed + * for future joins, its 'joinlist' field must not be empty after removal + * of all relids in 'other-relids'. + * * 'tlist' is the target list of one of the join relations * 'other-relids' is a list of relids contained within the other - * join relation + * join relation * 'first-resdomno' is the resdom number to use for the first created - * target list entry - * + * target list entry + * * Returns the new target list. */ -static List * -new_join_tlist(List *tlist, - List *other_relids, - int first_resdomno) +static List * +new_join_tlist(List * tlist, + List * other_relids, + int first_resdomno) { - int resdomno = first_resdomno - 1; - TargetEntry *xtl = NULL; - List *temp_node = NIL; - List *t_list = NIL; - List *i = NIL; - List *join_list = NIL; - bool in_final_tlist =false; - - - foreach(i,tlist) { - xtl= lfirst(i); - in_final_tlist = (join_list==NIL); - if( in_final_tlist) { - resdomno += 1; - temp_node = - lcons(create_tl_element(get_expr(xtl), - resdomno), - NIL); - t_list = nconc(t_list,temp_node); - } - } - - return(t_list); + int resdomno = first_resdomno - 1; + TargetEntry *xtl = NULL; + List *temp_node = NIL; + List *t_list = NIL; + List *i = NIL; + List *join_list = NIL; + bool in_final_tlist = false; + + + foreach(i, tlist) + { + xtl = lfirst(i); + in_final_tlist = (join_list == NIL); + if (in_final_tlist) + { + resdomno += 1; + temp_node = + lcons(create_tl_element(get_expr(xtl), + resdomno), + NIL); + t_list = nconc(t_list, temp_node); + } + } + + return (t_list); } -/* +/* * new-joininfo-list-- - * Builds a join relation's joininfo list by checking for join clauses - * which still need to used in future joins involving this relation. A - * join clause is still needed if there are still relations in the clause - * not contained in the list of relations comprising this join relation. - * New joininfo nodes are only created and added to - * 'current-joininfo-list' if a node for a particular join hasn't already - * been created. + * Builds a join relation's joininfo list by checking for join clauses + * which still need to used in future joins involving this relation. A + * join clause is still needed if there are still relations in the clause + * not contained in the list of relations comprising this join relation. + * New joininfo nodes are only created and added to + * 'current-joininfo-list' if a node for a particular join hasn't already + * been created. * - * 'current-joininfo-list' contains a list of those joininfo nodes that - * have already been built + * 'current-joininfo-list' contains a list of those joininfo nodes that + * have already been built * 'joininfo-list' is the list of join clauses involving this relation - * 'join-relids' is a list of relids corresponding to the relations - * currently being joined - * + * 'join-relids' is a list of relids corresponding to the relations + * currently being joined + * * Returns a list of joininfo nodes, new and old. */ -static List * -new_joininfo_list(List *joininfo_list, List *join_relids) +static List * +new_joininfo_list(List * joininfo_list, List * join_relids) { - List *current_joininfo_list = NIL; - List *new_otherrels = NIL; - JInfo *other_joininfo = (JInfo*)NULL; - List *xjoininfo = NIL; - - foreach (xjoininfo, joininfo_list) { - List *or; - JInfo *joininfo = (JInfo*)lfirst(xjoininfo); - - new_otherrels = joininfo->otherrels; - foreach (or, new_otherrels) - { - if ( intMember (lfirsti(or), join_relids) ) - new_otherrels = lremove ((void*)lfirst(or), new_otherrels); - } - joininfo->otherrels = new_otherrels; - if ( new_otherrels != NIL ) + List *current_joininfo_list = NIL; + List *new_otherrels = NIL; + JInfo *other_joininfo = (JInfo *) NULL; + List *xjoininfo = NIL; + + foreach(xjoininfo, joininfo_list) { - other_joininfo = joininfo_member(new_otherrels, - current_joininfo_list); - if(other_joininfo) { - other_joininfo->jinfoclauseinfo = - (List*)LispUnion(joininfo->jinfoclauseinfo, - other_joininfo->jinfoclauseinfo); - }else { - other_joininfo = makeNode(JInfo); - - other_joininfo->otherrels = - joininfo->otherrels; - other_joininfo->jinfoclauseinfo = - joininfo->jinfoclauseinfo; - other_joininfo->mergesortable = - joininfo->mergesortable; - other_joininfo->hashjoinable = - joininfo->hashjoinable; - other_joininfo->inactive = false; - - current_joininfo_list = lcons(other_joininfo, - current_joininfo_list); - } + List *or; + JInfo *joininfo = (JInfo *) lfirst(xjoininfo); + + new_otherrels = joininfo->otherrels; + foreach(or, new_otherrels) + { + if (intMember(lfirsti(or), join_relids)) + new_otherrels = lremove((void *) lfirst(or), new_otherrels); + } + joininfo->otherrels = new_otherrels; + if (new_otherrels != NIL) + { + other_joininfo = joininfo_member(new_otherrels, + current_joininfo_list); + if (other_joininfo) + { + other_joininfo->jinfoclauseinfo = + (List *) LispUnion(joininfo->jinfoclauseinfo, + other_joininfo->jinfoclauseinfo); + } + else + { + other_joininfo = makeNode(JInfo); + + other_joininfo->otherrels = + joininfo->otherrels; + other_joininfo->jinfoclauseinfo = + joininfo->jinfoclauseinfo; + other_joininfo->mergesortable = + joininfo->mergesortable; + other_joininfo->hashjoinable = + joininfo->hashjoinable; + other_joininfo->inactive = false; + + current_joininfo_list = lcons(other_joininfo, + current_joininfo_list); + } + } } - } - return(current_joininfo_list); + return (current_joininfo_list); } #ifdef NOTUSED /* * add-new-joininfos-- - * For each new join relation, create new joininfos that - * use the join relation as inner relation, and add - * the new joininfos to those rel nodes that still - * have joins with the join relation. + * For each new join relation, create new joininfos that + * use the join relation as inner relation, and add + * the new joininfos to those rel nodes that still + * have joins with the join relation. * * 'joinrels' is a list of join relations. * * Modifies the joininfo field of appropriate rel nodes. */ static void -geqo_add_new_joininfos(Query *root, List *joinrels, List *outerrels) +geqo_add_new_joininfos(Query * root, List * joinrels, List * outerrels) { - List *xjoinrel = NIL; - List *xrelid = NIL; - List *xrel = NIL; - List *xjoininfo = NIL; - - Rel *rel; - List *relids; - - List *super_rels; - List *xsuper_rel = NIL; - JInfo *new_joininfo; - - foreach(xjoinrel, joinrels) { - Rel *joinrel = (Rel *)lfirst(xjoinrel); - foreach(xrelid, joinrel->relids) { - /* length(joinrel->relids) should always be greater that 1, because of *JOIN* */ - /* ! BUG BUG ! - Relid relid = (Relid)lfirst(xrelid); - Rel *rel = get_join_rel(root, relid); - */ - - /* - if ( (root->join_relation_list_) != NIL ) { - rel = get_join_rel(root, xrelid); - } - else { - rel = get_base_rel(root, lfirsti(xrelid)); - } - */ - - /* NOTE: STILL BUGGY FOR CLAUSE-JOINS: */ - /* - relids = lconsi(lfirsti(xrelid), NIL); - rel = rel_member(relids, outerrels); - */ + List *xjoinrel = NIL; + List *xrelid = NIL; + List *xrel = NIL; + List *xjoininfo = NIL; + + Rel *rel; + List *relids; + + List *super_rels; + List *xsuper_rel = NIL; + JInfo *new_joininfo; + + foreach(xjoinrel, joinrels) + { + Rel *joinrel = (Rel *) lfirst(xjoinrel); + + foreach(xrelid, joinrel->relids) + { + + /* + * length(joinrel->relids) should always be greater that 1, + * because of *JOIN* + */ + + /* + * ! BUG BUG ! Relid relid = (Relid)lfirst(xrelid); Rel *rel = + * get_join_rel(root, relid); + */ - relids = lconsi(lfirsti(xrelid), NIL); - rel = rel_member(relids, root->base_relation_list_); + /* + * if ( (root->join_relation_list_) != NIL ) { rel = + * get_join_rel(root, xrelid); } else { rel = + * get_base_rel(root, lfirsti(xrelid)); } + */ - add_superrels(rel,joinrel); + /* NOTE: STILL BUGGY FOR CLAUSE-JOINS: */ + + /* + * relids = lconsi(lfirsti(xrelid), NIL); rel = + * rel_member(relids, outerrels); + */ + + relids = lconsi(lfirsti(xrelid), NIL); + rel = rel_member(relids, root->base_relation_list_); + + add_superrels(rel, joinrel); + } } - } - foreach(xjoinrel, joinrels) { - Rel *joinrel = (Rel *)lfirst(xjoinrel); - - foreach(xjoininfo, joinrel->joininfo) { - JInfo *joininfo = (JInfo*)lfirst(xjoininfo); - List *other_rels = joininfo->otherrels; - List *clause_info = joininfo->jinfoclauseinfo; - bool mergesortable = joininfo->mergesortable; - bool hashjoinable = joininfo->hashjoinable; - - foreach(xrelid, other_rels) { - /* ! BUG BUG ! - Relid relid = (Relid)lfirst(xrelid); - Rel *rel = get_join_rel(root, relid); - */ - - /* - if ( (root->join_relation_list_) != NIL ) { - rel = get_join_rel(root, xrelid); - } - else { - rel = get_base_rel(root, lfirsti(xrelid)); - } - */ - - /* NOTE: STILL BUGGY FOR CLAUSE-JOINS: */ - /* - relids = lconsi(lfirsti(xrelid), NIL); - rel = rel_member(relids, outerrels); - */ - - relids = lconsi(lfirsti(xrelid), NIL); - rel = rel_member(relids, root->base_relation_list_); - - super_rels = rel->superrels; - new_joininfo = makeNode(JInfo); - - new_joininfo->otherrels = joinrel->relids; - new_joininfo->jinfoclauseinfo = clause_info; - new_joininfo->mergesortable = mergesortable; - new_joininfo->hashjoinable = hashjoinable; - new_joininfo->inactive = false; - rel->joininfo = - lappend(rel->joininfo, new_joininfo); - - foreach(xsuper_rel, super_rels) { - Rel *super_rel = (Rel *)lfirst(xsuper_rel); - - if( nonoverlap_rels(super_rel,joinrel) ) { - List *new_relids = super_rel->relids; - JInfo *other_joininfo = - joininfo_member(new_relids, - joinrel->joininfo); - - if (other_joininfo) { - other_joininfo->jinfoclauseinfo = - (List*)LispUnion(clause_info, - other_joininfo->jinfoclauseinfo); - } else { - JInfo *new_joininfo = makeNode(JInfo); - - new_joininfo->otherrels = new_relids; - new_joininfo->jinfoclauseinfo = clause_info; - new_joininfo->mergesortable = mergesortable; - new_joininfo->hashjoinable = hashjoinable; - new_joininfo->inactive = false; - joinrel->joininfo = - lappend(joinrel->joininfo, - new_joininfo); + foreach(xjoinrel, joinrels) + { + Rel *joinrel = (Rel *) lfirst(xjoinrel); + + foreach(xjoininfo, joinrel->joininfo) + { + JInfo *joininfo = (JInfo *) lfirst(xjoininfo); + List *other_rels = joininfo->otherrels; + List *clause_info = joininfo->jinfoclauseinfo; + bool mergesortable = joininfo->mergesortable; + bool hashjoinable = joininfo->hashjoinable; + + foreach(xrelid, other_rels) + { + + /* + * ! BUG BUG ! Relid relid = (Relid)lfirst(xrelid); Rel + * *rel = get_join_rel(root, relid); + */ + + /* + * if ( (root->join_relation_list_) != NIL ) { rel = + * get_join_rel(root, xrelid); } else { rel = + * get_base_rel(root, lfirsti(xrelid)); } + */ + + /* NOTE: STILL BUGGY FOR CLAUSE-JOINS: */ + + /* + * relids = lconsi(lfirsti(xrelid), NIL); rel = + * rel_member(relids, outerrels); + */ + + relids = lconsi(lfirsti(xrelid), NIL); + rel = rel_member(relids, root->base_relation_list_); + + super_rels = rel->superrels; + new_joininfo = makeNode(JInfo); + + new_joininfo->otherrels = joinrel->relids; + new_joininfo->jinfoclauseinfo = clause_info; + new_joininfo->mergesortable = mergesortable; + new_joininfo->hashjoinable = hashjoinable; + new_joininfo->inactive = false; + rel->joininfo = + lappend(rel->joininfo, new_joininfo); + + foreach(xsuper_rel, super_rels) + { + Rel *super_rel = (Rel *) lfirst(xsuper_rel); + + if (nonoverlap_rels(super_rel, joinrel)) + { + List *new_relids = super_rel->relids; + JInfo *other_joininfo = + joininfo_member(new_relids, + joinrel->joininfo); + + if (other_joininfo) + { + other_joininfo->jinfoclauseinfo = + (List *) LispUnion(clause_info, + other_joininfo->jinfoclauseinfo); + } + else + { + JInfo *new_joininfo = makeNode(JInfo); + + new_joininfo->otherrels = new_relids; + new_joininfo->jinfoclauseinfo = clause_info; + new_joininfo->mergesortable = mergesortable; + new_joininfo->hashjoinable = hashjoinable; + new_joininfo->inactive = false; + joinrel->joininfo = + lappend(joinrel->joininfo, + new_joininfo); + } + } + } } - } } - } } - } - foreach(xrel, outerrels) { - rel = (Rel *)lfirst(xrel); - rel->superrels = NIL; - } + foreach(xrel, outerrels) + { + rel = (Rel *) lfirst(xrel); + rel->superrels = NIL; + } } /* * final-join-rels-- - * Find the join relation that includes all the original - * relations, i.e. the final join result. + * Find the join relation that includes all the original + * relations, i.e. the final join result. * * 'join-rel-list' is a list of join relations. * * Returns the list of final join relations. */ -static List * -geqo_final_join_rels(List *join_rel_list) +static List * +geqo_final_join_rels(List * join_rel_list) { - List *xrel = NIL; - List *temp = NIL; - List *t_list = NIL; - - /* - * find the relations that has no further joins, - * i.e., its joininfos all have otherrels nil. - */ - foreach(xrel,join_rel_list) { - Rel *rel = (Rel *)lfirst(xrel); - List *xjoininfo = NIL; - bool final = true; - - foreach (xjoininfo, rel->joininfo) { - JInfo *joininfo = (JInfo*)lfirst(xjoininfo); - - if (joininfo->otherrels != NIL) { - final = false; - break; - } - } - if (final) { - temp = lcons(rel, NIL); - t_list = nconc(t_list, temp); + List *xrel = NIL; + List *temp = NIL; + List *t_list = NIL; + + /* + * find the relations that has no further joins, i.e., its joininfos + * all have otherrels nil. + */ + foreach(xrel, join_rel_list) + { + Rel *rel = (Rel *) lfirst(xrel); + List *xjoininfo = NIL; + bool final = true; + + foreach(xjoininfo, rel->joininfo) + { + JInfo *joininfo = (JInfo *) lfirst(xjoininfo); + + if (joininfo->otherrels != NIL) + { + final = false; + break; + } + } + if (final) + { + temp = lcons(rel, NIL); + t_list = nconc(t_list, temp); + } } - } - return(t_list); + return (t_list); } /* * add_superrels-- - * add rel to the temporary property list superrels. + * add rel to the temporary property list superrels. * * 'rel' a rel node * 'super-rel' rel node of a join relation that includes rel @@ -599,65 +649,72 @@ geqo_final_join_rels(List *join_rel_list) * Modifies the superrels field of rel */ static void -add_superrels(Rel *rel, Rel *super_rel) +add_superrels(Rel * rel, Rel * super_rel) { - rel->superrels = lappend(rel->superrels, super_rel); + rel->superrels = lappend(rel->superrels, super_rel); } /* * nonoverlap-rels-- - * test if two join relations overlap, i.e., includes the same - * relation. + * test if two join relations overlap, i.e., includes the same + * relation. * * 'rel1' and 'rel2' are two join relations * * Returns non-nil if rel1 and rel2 do not overlap. */ -static bool -nonoverlap_rels(Rel *rel1, Rel *rel2) +static bool +nonoverlap_rels(Rel * rel1, Rel * rel2) { - return(nonoverlap_sets(rel1->relids, rel2->relids)); + return (nonoverlap_sets(rel1->relids, rel2->relids)); } -static bool -nonoverlap_sets(List *s1, List *s2) +static bool +nonoverlap_sets(List * s1, List * s2) { - List *x = NIL; - - foreach(x,s1) { - int e = lfirsti(x); - if(intMember(e,s2)) - return(false); - } - return(true); + List *x = NIL; + + foreach(x, s1) + { + int e = lfirsti(x); + + if (intMember(e, s2)) + return (false); + } + return (true); } -#endif /* NOTUSED */ + +#endif /* NOTUSED */ /* * geqo_joinrel_size-- - * compute estimate for join relation tuples, even for - * long join queries; so get logarithm of size when MAXINT overflow; + * compute estimate for join relation tuples, even for + * long join queries; so get logarithm of size when MAXINT overflow; */ static void -geqo_joinrel_size(Rel *joinrel, Rel *outer_rel, Rel *inner_rel) +geqo_joinrel_size(Rel * joinrel, Rel * outer_rel, Rel * inner_rel) { - Cost temp; - int ntuples; - + Cost temp; + int ntuples; + temp = (Cost) inner_rel->tuples * (Cost) outer_rel->tuples; /* cartesian product */ - if (joinrel->clauseinfo) { + if (joinrel->clauseinfo) + { temp = temp * product_selec(joinrel->clauseinfo); - } - - if (temp >= (MAXINT -1)) { - ntuples = ceil( geqo_log((double)temp, (double) GEQO_LOG_BASE) ); - } - else { - ntuples = ceil((double)temp); - } + } - if (ntuples < 1) ntuples = 1; /* make the best case 1 instead of 0 */ + if (temp >= (MAXINT - 1)) + { + ntuples = ceil(geqo_log((double) temp, (double) GEQO_LOG_BASE)); + } + else + { + ntuples = ceil((double) temp); + } + + if (ntuples < 1) + ntuples = 1; /* make the best case 1 instead of 0 */ joinrel->tuples = ntuples; } @@ -665,19 +722,21 @@ geqo_joinrel_size(Rel *joinrel, Rel *outer_rel, Rel *inner_rel) double geqo_log(double x, double b) { - return(log(x)/log(b)); + return (log(x) / log(b)); } -static Rel * -geqo_nth(int stop, List *rels) +static Rel * +geqo_nth(int stop, List * rels) { - List *r; - int i=1; + List *r; + int i = 1; - foreach(r, rels) { - if (i == stop) return lfirst(r); + foreach(r, rels) + { + if (i == stop) + return lfirst(r); i++; - } - elog(WARN,"geqo_nth: Internal error - ran off end of list"); - return NULL; /* to keep compiler happy */ + } + elog(WARN, "geqo_nth: Internal error - ran off end of list"); + return NULL; /* to keep compiler happy */ } 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); } - diff --git a/src/backend/optimizer/geqo/geqo_misc.c b/src/backend/optimizer/geqo/geqo_misc.c index 48ae78bdcda..67e810d87ca 100644 --- a/src/backend/optimizer/geqo/geqo_misc.c +++ b/src/backend/optimizer/geqo/geqo_misc.c @@ -1,20 +1,20 @@ /*------------------------------------------------------------------------ * * geqo_misc.c-- - * misc. printout and debug stuff + * misc. printout and debug stuff * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_misc.c,v 1.2 1997/02/19 14:52:01 scrappy Exp $ + * $Id: geqo_misc.c,v 1.3 1997/09/07 04:43:10 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ @@ -41,91 +41,97 @@ #include "optimizer/geqo_recombination.h" #include "optimizer/geqo_misc.h" -static float avg_pool (Pool *pool); +static float avg_pool(Pool * pool); /* avg_pool-- * */ static float -avg_pool (Pool *pool) +avg_pool(Pool * pool) { - int i; - double cumulative = 0.0; - - if (pool->size==0) - elog(WARN,"avg_pool: pool_size of zero"); - - for (i=0; i<pool->size; i++) - cumulative = cumulative + pool->data[i].worth; - - return ((float) cumulative/pool->size); + int i; + double cumulative = 0.0; + + if (pool->size == 0) + elog(WARN, "avg_pool: pool_size of zero"); + + for (i = 0; i < pool->size; i++) + cumulative = cumulative + pool->data[i].worth; + + return ((float) cumulative / pool->size); } /* print_pool-- */ void -print_pool (FILE *fp, Pool *pool, int start, int stop) +print_pool(FILE * fp, Pool * pool, int start, int stop) { - int i, j; + int i, + j; - /* be extra careful that start and stop are valid inputs */ + /* be extra careful that start and stop are valid inputs */ - if (start < 0) start = 0; - if (stop > pool->size) stop = pool->size; + if (start < 0) + start = 0; + if (stop > pool->size) + stop = pool->size; - if (start+stop > pool->size) { - start = 0; - 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, "%f\n", pool->data[i].worth); + 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, "%f\n", pool->data[i].worth); } } /* print_gen-- * - * printout for chromosome: best, worst, mean, average + * printout for chromosome: best, worst, mean, average * */ void -print_gen(FILE *fp, Pool *pool, int generation) +print_gen(FILE * fp, Pool * pool, int generation) { - int lowest; - - /* Get index to lowest ranking gene in poplulation. */ - /* Use 2nd to last since last is buffer. */ - lowest = pool->size > 1 ? pool->size-2 : 0; - - fprintf (fp, - "%5d | Bst: %f Wst: %f Mean: %f Avg: %f\n", - generation, - pool->data[0].worth, - pool->data[lowest].worth, - pool->data[pool->size/2].worth, - avg_pool(pool)); + int lowest; + + /* Get index to lowest ranking gene in poplulation. */ + /* Use 2nd to last since last is buffer. */ + lowest = pool->size > 1 ? pool->size - 2 : 0; + + fprintf(fp, + "%5d | Bst: %f Wst: %f Mean: %f Avg: %f\n", + generation, + pool->data[0].worth, + pool->data[lowest].worth, + pool->data[pool->size / 2].worth, + avg_pool(pool)); } void -print_edge_table (FILE *fp, Edge *edge_table, int num_gene) +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"); + 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"); } /************************************************************* @@ -133,116 +139,147 @@ print_edge_table (FILE *fp, Edge *edge_table, int num_gene) *************************************************************/ void -geqo_print_joinclauses(Query *root, List *clauses) +geqo_print_joinclauses(Query * root, List * clauses) { - List *l; - extern void print_expr(Node *expr, List *rtable); /* in print.c */ + List *l; + extern void print_expr(Node * expr, List * rtable); /* in print.c */ - foreach(l, clauses) { - CInfo *c = lfirst(l); + foreach(l, clauses) + { + CInfo *c = lfirst(l); - print_expr((Node*)c->clause, root->rtable); - if (lnext(l)) printf(" "); - } + print_expr((Node *) c->clause, root->rtable); + if (lnext(l)) + printf(" "); + } } void -geqo_print_path(Query *root, Path *path, int indent) +geqo_print_path(Query * root, Path * path, int indent) { - char *ptype = NULL; - JoinPath *jp; - bool join = false; - int i; - - for(i=0; i < indent; i++) - printf("\t"); - - switch(nodeTag(path)) { - case T_Path: - ptype = "SeqScan"; join=false; break; - case T_IndexPath: - ptype = "IdxScan"; join=false; break; - case T_JoinPath: - ptype = "Nestloop"; join=true; break; - case T_MergePath: - ptype = "MergeJoin"; join=true; break; - case T_HashPath: - ptype = "HashJoin"; join=true; break; - default: - break; - } - if (join) { - int size = path->parent->size; - jp = (JoinPath*)path; - printf("%s size=%d cost=%f\n", ptype, size, path->path_cost); - switch(nodeTag(path)) { + char *ptype = NULL; + JoinPath *jp; + bool join = false; + int i; + + for (i = 0; i < indent; i++) + printf("\t"); + + switch (nodeTag(path)) + { + case T_Path: + ptype = "SeqScan"; + join = false; + break; + case T_IndexPath: + ptype = "IdxScan"; + join = false; + break; + case T_JoinPath: + ptype = "Nestloop"; + join = true; + break; case T_MergePath: + ptype = "MergeJoin"; + join = true; + break; case T_HashPath: - for(i=0; i < indent+1; i++) - printf("\t"); - printf(" clauses=("); - geqo_print_joinclauses(root, - ((JoinPath*)path)->pathclauseinfo); - printf(")\n"); - - if (nodeTag(path)==T_MergePath) { - MergePath *mp = (MergePath*)path; - if (mp->outersortkeys || mp->innersortkeys) { - for(i=0; i < indent+1; i++) - printf("\t"); - printf(" sortouter=%d sortinner=%d\n", - ((mp->outersortkeys)?1:0), - ((mp->innersortkeys)?1:0)); - } - } - break; + ptype = "HashJoin"; + join = true; + break; default: - break; + break; } - geqo_print_path(root, jp->outerjoinpath, indent+1); - geqo_print_path(root, jp->innerjoinpath, indent+1); - } else { - int size = path->parent->size; - int relid = lfirsti(path->parent->relids); - printf("%s(%d) size=%d cost=%f", - ptype, relid, size, path->path_cost); - - if (nodeTag(path)==T_IndexPath) { - List *k, *l; - - printf(" keys="); - foreach (k, path->keys) { - printf("("); - foreach (l, lfirst(k)) { - Var *var = lfirst(l); - printf("%d.%d", var->varnoold, var->varoattno); - if (lnext(l)) printf(", "); + if (join) + { + int size = path->parent->size; + + jp = (JoinPath *) path; + printf("%s size=%d cost=%f\n", ptype, size, path->path_cost); + switch (nodeTag(path)) + { + case T_MergePath: + case T_HashPath: + for (i = 0; i < indent + 1; i++) + printf("\t"); + printf(" clauses=("); + geqo_print_joinclauses(root, + ((JoinPath *) path)->pathclauseinfo); + printf(")\n"); + + if (nodeTag(path) == T_MergePath) + { + MergePath *mp = (MergePath *) path; + + if (mp->outersortkeys || mp->innersortkeys) + { + for (i = 0; i < indent + 1; i++) + printf("\t"); + printf(" sortouter=%d sortinner=%d\n", + ((mp->outersortkeys) ? 1 : 0), + ((mp->innersortkeys) ? 1 : 0)); + } + } + break; + default: + break; } - printf(")"); - if (lnext(k)) printf(", "); - } + geqo_print_path(root, jp->outerjoinpath, indent + 1); + geqo_print_path(root, jp->innerjoinpath, indent + 1); + } + else + { + int size = path->parent->size; + int relid = lfirsti(path->parent->relids); + + printf("%s(%d) size=%d cost=%f", + ptype, relid, size, path->path_cost); + + if (nodeTag(path) == T_IndexPath) + { + List *k, + *l; + + printf(" keys="); + foreach(k, path->keys) + { + printf("("); + foreach(l, lfirst(k)) + { + Var *var = lfirst(l); + + printf("%d.%d", var->varnoold, var->varoattno); + if (lnext(l)) + printf(", "); + } + printf(")"); + if (lnext(k)) + printf(", "); + } + } + printf("\n"); } - printf("\n"); - } } -void -geqo_print_rel(Query *root, Rel *rel) +void +geqo_print_rel(Query * root, Rel * rel) { - List *l; - - printf("______________________________\n"); - printf("("); - foreach(l, rel->relids) { - printf("%d ", lfirsti(l)); - } - printf("): size=%d width=%d\n", rel->size, rel->width); - - printf("\tpath list:\n"); - foreach (l, rel->pathlist) { - geqo_print_path(root, lfirst(l), 1); - } - - printf("\tcheapest path:\n"); - geqo_print_path(root, rel->cheapestpath, 1); + List *l; + + printf("______________________________\n"); + printf("("); + foreach(l, rel->relids) + { + printf("%d ", lfirsti(l)); + } + printf("): size=%d width=%d\n", rel->size, rel->width); + + printf("\tpath list:\n"); + foreach(l, rel->pathlist) + { + geqo_print_path(root, lfirst(l), 1); + } + + printf("\tcheapest path:\n"); + geqo_print_path(root, rel->cheapestpath, 1); } diff --git a/src/backend/optimizer/geqo/geqo_mutation.c b/src/backend/optimizer/geqo/geqo_mutation.c index 9d544564210..a5a43e6e2b9 100644 --- a/src/backend/optimizer/geqo/geqo_mutation.c +++ b/src/backend/optimizer/geqo/geqo_mutation.c @@ -2,33 +2,33 @@ * * geqo_mutation.c-- * -* TSP mutation routines +* TSP mutation routines * -* $Id: geqo_mutation.c,v 1.1 1997/02/19 12:57:13 scrappy Exp $ +* $Id: geqo_mutation.c,v 1.2 1997/09/07 04:43:13 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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" @@ -50,27 +50,28 @@ #include "optimizer/geqo_random.h" #include "optimizer/geqo_mutation.h" - void - geqo_mutation (Gene *tour, int num_gene) - { - int swap1; - int swap2; - int num_swaps = geqo_randint (num_gene/3, 0); - Gene temp; +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 (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); + while (swap1 == swap2) + swap2 = geqo_randint(num_gene - 1, 0); - temp = tour[swap1]; - tour[swap1] = tour[swap2]; - tour[swap2] = temp; + temp = tour[swap1]; + tour[swap1] = tour[swap2]; + tour[swap2] = temp; - num_swaps -= 1; - } + num_swaps -= 1; + } } diff --git a/src/backend/optimizer/geqo/geqo_ox1.c b/src/backend/optimizer/geqo/geqo_ox1.c index 329554f9aae..b88b8950673 100644 --- a/src/backend/optimizer/geqo/geqo_ox1.c +++ b/src/backend/optimizer/geqo/geqo_ox1.c @@ -2,35 +2,35 @@ * * geqo_ox1.c-- * -* order crossover [OX] routines; -* OX1 operator according to Davis -* (Proc Int'l Joint Conf on AI) +* order crossover [OX] routines; +* OX1 operator according to Davis +* (Proc Int'l Joint Conf on AI) * -* $Id: geqo_ox1.c,v 1.1 1997/03/14 16:02:58 scrappy Exp $ +* $Id: geqo_ox1.c,v 1.2 1997/09/07 04:43:14 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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" @@ -56,48 +56,52 @@ /* ox1-- * - * position crossover + * position crossover */ void -ox1(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table) +ox1(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 (num_gene - 1, 0); - right = geqo_randint (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 */ - } - - } + 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(num_gene - 1, 0); + right = geqo_randint(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 */ + } + +} diff --git a/src/backend/optimizer/geqo/geqo_ox2.c b/src/backend/optimizer/geqo/geqo_ox2.c index 2afcece01ff..ef09925b4fa 100644 --- a/src/backend/optimizer/geqo/geqo_ox2.c +++ b/src/backend/optimizer/geqo/geqo_ox2.c @@ -2,35 +2,35 @@ * * geqo_ox2.c-- * -* order crossover [OX] routines; -* OX2 operator according to Syswerda -* (The Genetic Algorithms Handbook, ed L Davis) +* order crossover [OX] routines; +* OX2 operator according to Syswerda +* (The Genetic Algorithms Handbook, ed L Davis) * -* $Id: geqo_ox2.c,v 1.1 1997/03/14 16:03:02 scrappy Exp $ +* $Id: geqo_ox2.c,v 1.2 1997/09/07 04:43:15 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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" @@ -56,58 +56,70 @@ /* ox2-- * - * position crossover + * position crossover */ void -ox2(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table) +ox2(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 (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 */ - } - - - 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]; - } + 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(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 */ + } + + + 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]; + } } diff --git a/src/backend/optimizer/geqo/geqo_params.c b/src/backend/optimizer/geqo/geqo_params.c index 52c57c45378..45f7dfd5ddc 100644 --- a/src/backend/optimizer/geqo/geqo_params.c +++ b/src/backend/optimizer/geqo/geqo_params.c @@ -1,20 +1,20 @@ /*------------------------------------------------------------------------ * * geqo_params.c-- -* routines for determining necessary genetic optimization parameters +* routines for determining necessary genetic optimization parameters * * Copyright (c) 1994, Regents of the University of California * -* $Id: geqo_params.c,v 1.5 1997/08/18 02:14:41 momjian Exp $ +* $Id: geqo_params.c,v 1.6 1997/09/07 04:43:16 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ @@ -45,48 +45,48 @@ #include "storage/fd.h" -#define POOL_TAG "Pool_Size" -#define TRIAL_TAG "Generations" -#define RAND_TAG "Random_Seed" -#define BIAS_TAG "Selection_Bias" +#define POOL_TAG "Pool_Size" +#define TRIAL_TAG "Generations" +#define RAND_TAG "Random_Seed" +#define BIAS_TAG "Selection_Bias" -#define EFFORT_TAG "Effort" /* optimization effort and */ -#define LOW "low" /* corresponding tags */ -#define MEDIUM "medium" -#define HIGH "high" +#define EFFORT_TAG "Effort"/* optimization effort and */ +#define LOW "low" /* corresponding tags */ +#define MEDIUM "medium" +#define HIGH "high" -#define MAX_TOKEN 80 /* Maximum size of one token in the * - * configuration file */ +#define MAX_TOKEN 80 /* Maximum size of one token in the * + * configuration file */ -static int gimme_pool_size(int string_length); -static int gimme_number_generations(int pool_size, int effort); -static int next_token(FILE *, char *, int); +static int gimme_pool_size(int string_length); +static int gimme_number_generations(int pool_size, int effort); +static int next_token(FILE *, char *, int); /* * geqo_param-- - * get ga parameters out of "$PGDATA/pg_geqo" file. + * get ga parameters out of "$PGDATA/pg_geqo" file. */ void geqo_params(int string_length) { - int i; + int i; - char buf[MAX_TOKEN]; - FILE *file; + char buf[MAX_TOKEN]; + FILE *file; - char *conf_file; + char *conf_file; /* these static variables are used to signal that a value has been set */ - int pool_size = 0; - int number_trials = 0; - int random_seed = 0; - int selection_bias = 0; - int effort = 0; + int pool_size = 0; + int number_trials = 0; + int random_seed = 0; + int selection_bias = 0; + int effort = 0; /* put together the full pathname to the config file */ conf_file = - (char *) palloc((strlen(DataDir)+strlen(GEQO_FILE)+2)*sizeof(char)); + (char *) palloc((strlen(DataDir) + strlen(GEQO_FILE) + 2) * sizeof(char)); sprintf(conf_file, "%s/%s", DataDir, GEQO_FILE); @@ -94,99 +94,109 @@ geqo_params(int string_length) file = AllocateFile(conf_file, "r"); if (file) { + /* * empty and comment line stuff */ while ((i = next_token(file, buf, sizeof(buf))) != EOF) { - /* If only token on the line, ignore */ - if (i == '\n') continue; - - /* Comment -- read until end of line then next line */ - if (buf[0] == '#') - { - while (next_token(file, buf, sizeof(buf)) == 0) ; - continue; - } + /* If only token on the line, ignore */ + if (i == '\n') + continue; + + /* Comment -- read until end of line then next line */ + if (buf[0] == '#') + { + while (next_token(file, buf, sizeof(buf)) == 0); + continue; + } /* * get ga parameters by parsing */ - + /*------------------------------------------------- pool size */ - if ( strcmp(buf, POOL_TAG) == 0 ) + if (strcmp(buf, POOL_TAG) == 0) { i = next_token(file, buf, sizeof(buf)); /* get next token */ - - if (i != EOF) /* only ignore if we got no text at all */ + + if (i != EOF) /* only ignore if we got no text at all */ { - if (sscanf (buf, "%d", &PoolSize) == 1) pool_size = 1; + if (sscanf(buf, "%d", &PoolSize) == 1) + pool_size = 1; } - + } - + /*------------------------------------------------- number of trials */ - else if ( strcmp(buf, TRIAL_TAG) == 0 ) + else if (strcmp(buf, TRIAL_TAG) == 0) { i = next_token(file, buf, sizeof(buf)); - + if (i != EOF) { - if (sscanf (buf, "%d", &Generations) == 1) number_trials = 1; + if (sscanf(buf, "%d", &Generations) == 1) + number_trials = 1; } - + } - + /*------------------------------------------------- optimization effort */ - else if ( strcmp(buf, EFFORT_TAG) == 0 ) + else if (strcmp(buf, EFFORT_TAG) == 0) { i = next_token(file, buf, sizeof(buf)); - + if (i != EOF) { - if (strcmp (buf, LOW) == 0) effort = LOW_EFFORT; - else if (strcmp (buf, MEDIUM) == 0) effort = MEDIUM_EFFORT; - else if (strcmp (buf, HIGH) == 0) effort = HIGH_EFFORT; + if (strcmp(buf, LOW) == 0) + effort = LOW_EFFORT; + else if (strcmp(buf, MEDIUM) == 0) + effort = MEDIUM_EFFORT; + else if (strcmp(buf, HIGH) == 0) + effort = HIGH_EFFORT; } - + } - + /*------------------------------------------- random seed */ - else if ( strcmp(buf, RAND_TAG) == 0 ) - { + else if (strcmp(buf, RAND_TAG) == 0) + { i = next_token(file, buf, sizeof(buf)); - + if (i != EOF) { - if (sscanf (buf, "%ld", &RandomSeed) == 1) random_seed = 1; + if (sscanf(buf, "%ld", &RandomSeed) == 1) + random_seed = 1; } - + } - + /*------------------------------------------- selection bias */ - else if ( strcmp(buf, BIAS_TAG) == 0 ) + else if (strcmp(buf, BIAS_TAG) == 0) { i = next_token(file, buf, sizeof(buf)); - + if (i != EOF) { - if (sscanf (buf, "%lf", &SelectionBias) == 1) selection_bias = 1; + if (sscanf(buf, "%lf", &SelectionBias) == 1) + selection_bias = 1; } - + } - + /* unrecognized tags */ else { if (i != EOF) { } - - elog(DEBUG,"geqo_params: unknown parameter type \"%s\"\nin file \'%s\'", buf, conf_file); + + elog(DEBUG, "geqo_params: unknown parameter type \"%s\"\nin file \'%s\'", buf, conf_file); /* if not at end-of-line, keep reading til we are */ - while (i == 0) i = next_token(file, buf, sizeof(buf)); - } + while (i == 0) + i = next_token(file, buf, sizeof(buf)); + } } FreeFile(file); @@ -194,9 +204,9 @@ geqo_params(int string_length) pfree(conf_file); } - else + else { - elog(DEBUG,"geqo_params: ga parameter file\n\'%s\'\ndoes not exist or permissions are not setup correctly", conf_file); + elog(DEBUG, "geqo_params: ga parameter file\n\'%s\'\ndoes not exist or permissions are not setup correctly", conf_file); } /* @@ -204,49 +214,49 @@ geqo_params(int string_length) */ /**************** PoolSize: essential ****************/ - if ( !(pool_size) ) + if (!(pool_size)) { PoolSize = gimme_pool_size(string_length); - elog(DEBUG,"geqo_params: no pool size specified;\nusing computed value of %d", PoolSize); + elog(DEBUG, "geqo_params: no pool size specified;\nusing computed value of %d", PoolSize); } - - + + /**************** Effort: essential ****************/ - if ( !(effort) ) + if (!(effort)) { if (PoolSize == MAX_POOL) effort = HIGH_EFFORT; else effort = MEDIUM_EFFORT; - - elog(DEBUG,"geqo_params: no optimization effort specified;\nusing value of %d", effort); + + elog(DEBUG, "geqo_params: no optimization effort specified;\nusing value of %d", effort); } /**************** Generations: essential ****************/ - if ( !(number_trials) ) + if (!(number_trials)) { Generations = gimme_number_generations(PoolSize, effort); - - elog(DEBUG,"geqo_params: no number of trials specified;\nusing computed value of %d", Generations); + + elog(DEBUG, "geqo_params: no number of trials specified;\nusing computed value of %d", Generations); } /* RandomSeed: */ - if ( !(random_seed) ) + if (!(random_seed)) { RandomSeed = (long) time(NULL); - elog(DEBUG,"geqo_params: no random seed specified;\nusing computed value of %ld", RandomSeed); + elog(DEBUG, "geqo_params: no random seed specified;\nusing computed value of %ld", RandomSeed); } /* SelectionBias: */ - if ( !(selection_bias) ) + if (!(selection_bias)) { SelectionBias = SELECTION_BIAS; - elog(DEBUG,"geqo_params: no selection bias specified;\nusing default value of %f", SelectionBias); + elog(DEBUG, "geqo_params: no selection bias specified;\nusing default value of %f", SelectionBias); } } @@ -255,73 +265,79 @@ geqo_params(int string_length) /* * Grab one token out of fp. Defined as the next string of non-whitespace * in the file. After we get the token, continue reading until EOF, end of - * line or the next token. If it's the last token on the line, return '\n' + * line or the next token. If it's the last token on the line, return '\n' * for the value. If we get EOF before reading a token, return EOF. In all * other cases return 0. */ -static int -next_token(FILE *fp, char *buf, int bufsz) +static int +next_token(FILE * fp, char *buf, int bufsz) { - int c; - char *eb = buf+(bufsz-1); + int c; + char *eb = buf + (bufsz - 1); - /* Discard inital whitespace */ - while (isspace(c = getc(fp))) ; + /* Discard inital whitespace */ + while (isspace(c = getc(fp))); - /* EOF seen before any token so return EOF */ - if (c == EOF) return -1; + /* EOF seen before any token so return EOF */ + if (c == EOF) + return -1; - /* Form a token in buf */ - do { - if (buf < eb) *buf++ = c; - c = getc(fp); - } while (!isspace(c) && c != EOF); - *buf = '\0'; + /* Form a token in buf */ + do + { + if (buf < eb) + *buf++ = c; + c = getc(fp); + } while (!isspace(c) && c != EOF); + *buf = '\0'; - /* Discard trailing tabs and spaces */ - while (c == ' ' || c == '\t') c = getc(fp); + /* Discard trailing tabs and spaces */ + while (c == ' ' || c == '\t') + c = getc(fp); - /* Put back the char that was non-whitespace (putting back EOF is ok) */ - ungetc(c, fp); + /* Put back the char that was non-whitespace (putting back EOF is ok) */ + ungetc(c, fp); - /* If we ended with a newline, return that, otherwise return 0 */ - return (c == '\n' ? '\n' : 0); + /* If we ended with a newline, return that, otherwise return 0 */ + return (c == '\n' ? '\n' : 0); } /* gimme_pool_size-- - * compute good estimation for pool size - * according to number of involved rels in a query + * compute good estimation for pool size + * according to number of involved rels in a query */ -static int +static int gimme_pool_size(int string_length) { - double exponent; - double size; + double exponent; + double size; exponent = (double) string_length + 1.0; - size = pow (2.0, exponent); + size = pow(2.0, exponent); - if (size < MIN_POOL) { + if (size < MIN_POOL) + { return (MIN_POOL); - } - else if (size > MAX_POOL) { + } + else if (size > MAX_POOL) + { return (MAX_POOL); - } - else - return ( (int) ceil(size) ); + } + else + return ((int) ceil(size)); } /* gimme_number_generations-- - * compute good estimation for number of generations size - * for convergence + * compute good estimation for number of generations size + * for convergence */ -static int +static int gimme_number_generations(int pool_size, int effort) { - int number_gens; + int number_gens; - number_gens = (int) ceil ( geqo_log((double) pool_size, 2.0) ); + number_gens = (int) ceil(geqo_log((double) pool_size, 2.0)); return (effort * number_gens); } diff --git a/src/backend/optimizer/geqo/geqo_paths.c b/src/backend/optimizer/geqo/geqo_paths.c index a22be406f5a..d98855d2887 100644 --- a/src/backend/optimizer/geqo/geqo_paths.c +++ b/src/backend/optimizer/geqo/geqo_paths.c @@ -1,11 +1,11 @@ /*------------------------------------------------------------------------- * * geqo_paths.c-- - * Routines to process redundant paths and relations + * Routines to process redundant paths and relations * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_paths.c,v 1.4 1997/06/11 02:44:12 vadim Exp $ + * $Id: geqo_paths.c,v 1.5 1997/09/07 04:43:17 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -28,120 +28,128 @@ #include "optimizer/geqo_paths.h" -static List *geqo_prune_rel(Rel *rel, List *other_rels); -static Path *set_paths(Rel *rel, Path *unorderedpath); +static List *geqo_prune_rel(Rel * rel, List * other_rels); +static Path *set_paths(Rel * rel, Path * unorderedpath); -/* +/* * geqo-prune-rels-- - * Removes any redundant relation entries from a list of rel nodes - * 'rel-list'. - * - * Returns the resulting list. - * + * Removes any redundant relation entries from a list of rel nodes + * 'rel-list'. + * + * Returns the resulting list. + * */ -List *geqo_prune_rels(List *rel_list) +List * +geqo_prune_rels(List * rel_list) { - List *temp_list = NIL; - - if (rel_list != NIL) { - temp_list = lcons(lfirst(rel_list), - geqo_prune_rels(geqo_prune_rel((Rel*)lfirst(rel_list), - lnext(rel_list)))); - } - return(temp_list); + List *temp_list = NIL; + + if (rel_list != NIL) + { + temp_list = lcons(lfirst(rel_list), + geqo_prune_rels(geqo_prune_rel((Rel *) lfirst(rel_list), + lnext(rel_list)))); + } + return (temp_list); } -/* +/* * geqo-prune-rel-- - * Prunes those relations from 'other-rels' that are redundant with - * 'rel'. A relation is redundant if it is built up of the same - * relations as 'rel'. Paths for the redundant relation are merged into - * the pathlist of 'rel'. - * + * Prunes those relations from 'other-rels' that are redundant with + * 'rel'. A relation is redundant if it is built up of the same + * relations as 'rel'. Paths for the redundant relation are merged into + * the pathlist of 'rel'. + * * Returns a list of non-redundant relations, and sets the pathlist field * of 'rel' appropriately. - * + * */ -static List * -geqo_prune_rel(Rel *rel, List *other_rels) +static List * +geqo_prune_rel(Rel * rel, List * other_rels) { - List *i = NIL; - List *t_list = NIL; - List *temp_node = NIL; - Rel *other_rel = (Rel *)NULL; - - foreach(i, other_rels) { - other_rel = (Rel*)lfirst(i); - if(same(rel->relids, other_rel->relids)) { - rel->pathlist = add_pathlist(rel, - rel->pathlist, - other_rel->pathlist); - t_list = nconc(t_list, NIL); /* XXX is this right ? */ - } else { - temp_node = lcons(other_rel, NIL); - t_list = nconc(t_list,temp_node); - } - } - return(t_list); + List *i = NIL; + List *t_list = NIL; + List *temp_node = NIL; + Rel *other_rel = (Rel *) NULL; + + foreach(i, other_rels) + { + other_rel = (Rel *) lfirst(i); + if (same(rel->relids, other_rel->relids)) + { + rel->pathlist = add_pathlist(rel, + rel->pathlist, + other_rel->pathlist); + t_list = nconc(t_list, NIL); /* XXX is this right ? */ + } + else + { + temp_node = lcons(other_rel, NIL); + t_list = nconc(t_list, temp_node); + } + } + return (t_list); } -/* +/* * geqo-rel-paths-- - * For a relation 'rel' (which corresponds to a join - * relation), set pointers to the unordered path and cheapest paths - * (if the unordered path isn't the cheapest, it is pruned), and - * reset the relation's size field to reflect the join. - * + * For a relation 'rel' (which corresponds to a join + * relation), set pointers to the unordered path and cheapest paths + * (if the unordered path isn't the cheapest, it is pruned), and + * reset the relation's size field to reflect the join. + * * Returns nothing of interest. - * + * */ void -geqo_rel_paths(Rel *rel) +geqo_rel_paths(Rel * rel) { - List *y = NIL; - Path *path = (Path*)NULL; - JoinPath *cheapest = (JoinPath*)NULL; - - rel->size = 0; - foreach(y, rel->pathlist) - { - path = (Path*)lfirst(y); - - if(!path->p_ordering.ord.sortop) + List *y = NIL; + Path *path = (Path *) NULL; + JoinPath *cheapest = (JoinPath *) NULL; + + rel->size = 0; + foreach(y, rel->pathlist) + { + path = (Path *) lfirst(y); + + if (!path->p_ordering.ord.sortop) break; - } + } - cheapest = (JoinPath*)set_paths(rel, path); - if ( IsA_JoinPath (cheapest) ) - rel->size = compute_joinrel_size(cheapest); + cheapest = (JoinPath *) set_paths(rel, path); + if (IsA_JoinPath(cheapest)) + rel->size = compute_joinrel_size(cheapest); } -/* +/* * set-path-- - * Compares the unordered path for a relation with the cheapest path. If - * the unordered path is not cheapest, it is pruned. - * - * Resets the pointers in 'rel' for unordered and cheapest paths. - * + * Compares the unordered path for a relation with the cheapest path. If + * the unordered path is not cheapest, it is pruned. + * + * Resets the pointers in 'rel' for unordered and cheapest paths. + * * Returns the cheapest path. - * + * */ -static Path * -set_paths(Rel *rel, Path *unorderedpath) +static Path * +set_paths(Rel * rel, Path * unorderedpath) { - Path *cheapest = set_cheapest(rel, rel->pathlist); - - /* don't prune if not pruneable -- JMH, 11/23/92 */ - if(unorderedpath != cheapest - && rel->pruneable) { - - rel->unorderedpath = (Path *)NULL; - rel->pathlist = lremove(unorderedpath, rel->pathlist); - } else { - rel->unorderedpath = (Path *)unorderedpath; - } - - return(cheapest); + Path *cheapest = set_cheapest(rel, rel->pathlist); + + /* don't prune if not pruneable -- JMH, 11/23/92 */ + if (unorderedpath != cheapest + && rel->pruneable) + { + + rel->unorderedpath = (Path *) NULL; + rel->pathlist = lremove(unorderedpath, rel->pathlist); + } + else + { + rel->unorderedpath = (Path *) unorderedpath; + } + + return (cheapest); } - diff --git a/src/backend/optimizer/geqo/geqo_pmx.c b/src/backend/optimizer/geqo/geqo_pmx.c index c6e699cfa9f..c9187fec54b 100644 --- a/src/backend/optimizer/geqo/geqo_pmx.c +++ b/src/backend/optimizer/geqo/geqo_pmx.c @@ -2,35 +2,35 @@ * * geqo_pmx.c-- * -* partially matched crossover [PMX] routines; -* PMX operator according to Goldberg & Lingle -* (Proc Int'l Conf on GA's) +* partially matched crossover [PMX] routines; +* PMX operator according to Goldberg & Lingle +* (Proc Int'l Conf on GA's) * -* $Id: geqo_pmx.c,v 1.1 1997/02/19 12:57:28 scrappy Exp $ +* $Id: geqo_pmx.c,v 1.2 1997/09/07 04:43:18 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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" @@ -56,155 +56,182 @@ /* pmx-- * - * partially matched crossover + * partially matched crossover */ void -pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene) +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)); - int *indx = (int *) palloc ((num_gene+1)*sizeof(int)); - int *check_list = (int *) palloc ((num_gene+1)*sizeof(int)); + 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; - 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; - } - + for (k = 0; k < num_gene; k++) + { + failed[k] = -1; + from[k] = -1; + check_list[k + 1] = 0; + } + /* locate crossover points */ - left = geqo_randint(num_gene-1, 0); - right = geqo_randint(num_gene-1, 0); + left = geqo_randint(num_gene - 1, 0); + right = geqo_randint(num_gene - 1, 0); - if (left > right) { - temp = left; - left = right; - right = temp; - } + 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]]++; - } - + 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]]++; - } + 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; + 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 */ + for (k = left; k <= right; k++) + { /* for all elements in the tour1-2 */ - else { - found = 0; /* substitute elements */ + if (tour1[k] == tour2[k]) + found = 1; /* find match in tour2 */ - j = 0; - while ( !(found) && (j < num_gene) ) { - if ( (offspring[j] == tour1[k]) && (from[j] == DAD) ) { + else + { + found = 0; /* substitute elements */ - check_list[offspring[j]]--; - offspring[j] = tour2[k]; - found = 1; - check_list[tour2[k]]++; - } + j = 0; + while (!(found) && (j < num_gene)) + { + if ((offspring[j] == tour1[k]) && (from[j] == DAD)) + { - j++; - } + 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; + if (!(found)) + { /* failed to replace gene */ + failed[mx_fail] = (int) tour1[k]; + indx[mx_fail] = k; + mx_fail++; + } - for (k = 0; k < mx_hold; k++) { - found = 0; + } /* ... for */ - 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--; - } +/* STEP 2 */ - j++; - } + /* see if any genes could not be replaced */ + if (mx_fail > 0) + { + mx_hold = mx_fail; - } /* ... for */ + for (k = 0; k < mx_hold; k++) + { + found = 0; - } /* ... if */ - + j = 0; + while (!(found) && (j < num_gene)) + { -/* STEP 3 */ + if ((failed[k] == (int) offspring[j]) && (from[j] == DAD)) + { + check_list[offspring[j]]--; + offspring[j] = tour2[indx[k]]; + check_list[tour2[indx[k]]]++; - for (k = 1; k <= num_gene; k++) { + found = 1; + failed[k] = -1; + mx_fail--; + } - if (check_list[k] > 1) { - i = 0; + j++; + } - while (i < num_gene) { - if ( (offspring[i] == (Gene) k) && (from[i] == DAD) ) { - j = 1; + } /* ... for */ - 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; - } + } /* ... if */ - j++; - } - } /* ... if */ - - i++; - } /* end while */ +/* STEP 3 */ - } - } /* ... for */ - - pfree(failed); - pfree(from); - pfree(indx); - pfree(check_list); + 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); } diff --git a/src/backend/optimizer/geqo/geqo_pool.c b/src/backend/optimizer/geqo/geqo_pool.c index 98a1a6e2a06..89c945d4ef4 100644 --- a/src/backend/optimizer/geqo/geqo_pool.c +++ b/src/backend/optimizer/geqo/geqo_pool.c @@ -1,20 +1,20 @@ /*------------------------------------------------------------------------ * * geqo_pool.c-- - * Genetic Algorithm (GA) pool stuff + * Genetic Algorithm (GA) pool stuff * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_pool.c,v 1.1 1997/02/19 12:57:31 scrappy Exp $ + * $Id: geqo_pool.c,v 1.2 1997/09/07 04:43:19 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ @@ -44,205 +44,220 @@ #include "optimizer/geqo_recombination.h" -static int compare(void *arg1, void *arg2); +static int compare(void *arg1, void *arg2); /* * alloc-pool-- - * allocates memory for GA pool + * allocates memory for GA pool */ -Pool * +Pool * alloc_pool(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)); + 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); + return (new_pool); } /* * free-pool-- - * deallocates memory for GA pool + * deallocates memory for GA pool */ void -free_pool (Pool *pool) +free_pool(Pool * pool) { - Chromosome *chromo; - int i; + 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 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); + /* all chromosome */ + pfree(pool->data); - /* pool */ - pfree (pool); + /* pool */ + pfree(pool); } /* * random-init-pool-- - * initialize genetic pool + * initialize genetic pool */ void -random_init_pool (Query *root, Pool *pool, int strt, int stp) +random_init_pool(Query * root, Pool * pool, int strt, int stp) { - Chromosome *chromo = (Chromosome *) pool->data; - int i; + Chromosome *chromo = (Chromosome *) pool->data; + int i; - for (i=strt; i<stp; i++) { - init_tour(chromo[i].string, pool->string_length); /* from "geqo_recombination.c" */ + for (i = strt; i < stp; i++) + { + init_tour(chromo[i].string, pool->string_length); /* from + * "geqo_recombination.c" + * */ - pool->data[i].worth = - geqo_eval(root, chromo[i].string, pool->string_length); /* "from geqo_eval.c" */ + pool->data[i].worth = + geqo_eval(root, chromo[i].string, pool->string_length); /* "from geqo_eval.c" */ } } /* * sort-pool-- - * sorts input pool according to worth, from smallest to largest + * sorts input pool according to worth, from smallest to largest * - * maybe you have to change compare() for different ordering ... + * maybe you have to change compare() for different ordering ... */ void -sort_pool(Pool *pool) -{ - pg_qsort(pool->data, pool->size, sizeof(Chromosome), compare); +sort_pool(Pool * pool) +{ + pg_qsort(pool->data, pool->size, sizeof(Chromosome), compare); } /* * compare-- - * static input function for pg_sort + * static input function for pg_sort * - * return values for sort from smallest to largest are prooved! - * don't change them! + * return values for sort from smallest to largest are prooved! + * don't change them! */ static int compare(void *arg1, void *arg2) { - Chromosome chromo1 = *(Chromosome *) arg1; - Chromosome chromo2 = *(Chromosome *) arg2; - - if (chromo1.worth == chromo2.worth) - return(0); - else if (chromo1.worth > chromo2.worth) - return(1); - else - return(-1); + Chromosome chromo1 = *(Chromosome *) arg1; + Chromosome chromo2 = *(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 + * allocates a chromosome and string space */ -Chromosome * -alloc_chromo (int string_length) +Chromosome * +alloc_chromo(int string_length) { - Chromosome *chromo; + Chromosome *chromo; + + chromo = (Chromosome *) palloc(sizeof(Chromosome)); + chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene)); - chromo = (Chromosome *) palloc (sizeof(Chromosome)); - chromo->string = (Gene *) palloc ((string_length+1)*sizeof(Gene)); - - return (chromo); + return (chromo); } /* free_chromo-- - * deallocates a chromosome and string space + * deallocates a chromosome and string space */ void -free_chromo (Chromosome *chromo) +free_chromo(Chromosome * chromo) { - pfree(chromo->string); - pfree(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 + * inserts a new chromosome into the pool, displacing worst gene in pool + * assumes best->worst = smallest->largest */ void -spread_chromo (Chromosome *chromo, Pool *pool) +spread_chromo(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 (&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; - } + 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(&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 index f060561b516..71aa2415b55 100644 --- a/src/backend/optimizer/geqo/geqo_px.c +++ b/src/backend/optimizer/geqo/geqo_px.c @@ -2,35 +2,35 @@ * * geqo_px.c-- * -* position crossover [PX] routines; -* PX operator according to Syswerda -* (The Genetic Algorithms Handbook, L Davis, ed) +* position crossover [PX] routines; +* PX operator according to Syswerda +* (The Genetic Algorithms Handbook, L Davis, ed) * -* $Id: geqo_px.c,v 1.1 1997/02/19 12:57:37 scrappy Exp $ +* $Id: geqo_px.c,v 1.2 1997/09/07 04:43:20 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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" @@ -56,61 +56,70 @@ /* px-- * - * position crossover + * position crossover */ void -px(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table) +px(Gene * tour1, Gene * tour2, Gene * offspring, int num_gene, City * city_table) { - int num_positions; - int i, pos, tour2_index, offspring_index; + 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; - } + /* 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 (2*num_gene/3, num_gene/3); + /* 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); + /* 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 */ - } + offspring[pos] = tour1[pos]; /* transfer cities to child */ + city_table[(int) tour1[pos]].used = 1; /* mark city used */ + } - tour2_index = 0; - offspring_index = 0; + tour2_index = 0; + offspring_index = 0; - /* px main part */ + /* px main part */ - while (offspring_index < num_gene) { + while (offspring_index < num_gene) + { - /* next position in offspring filled */ - if (!city_table[(int) tour1[offspring_index]].used) { + /* 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) { + /* next city in tour1 not used */ + if (!city_table[(int) tour2[tour2_index]].used) + { - /* inherit from tour1 */ - offspring[offspring_index] = tour2[tour2_index]; + /* inherit from tour1 */ + offspring[offspring_index] = tour2[tour2_index]; - tour2_index++; - offspring_index++; - } - else { /* next city in tour2 has been used */ - 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++; - } + } + else + { /* next position in offspring is filled */ + offspring_index++; + } - } - - } + } +} diff --git a/src/backend/optimizer/geqo/geqo_recombination.c b/src/backend/optimizer/geqo/geqo_recombination.c index df175dcb866..53803079819 100644 --- a/src/backend/optimizer/geqo/geqo_recombination.c +++ b/src/backend/optimizer/geqo/geqo_recombination.c @@ -1,18 +1,18 @@ /*------------------------------------------------------------------------ * * geqo_recombination.c-- -* misc recombination procedures +* misc recombination procedures * -* $Id: geqo_recombination.c,v 1.1 1997/02/19 12:57:42 scrappy Exp $ +* $Id: geqo_recombination.c,v 1.2 1997/09/07 04:43:21 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ @@ -42,65 +42,70 @@ /* * init_tour-- * - * Randomly generates a legal "traveling salesman" tour - * (i.e. where each point is visited only once.) - * Essentially, this routine fills an array with all possible - * points on the tour and randomly chooses the 'next' city from - * this array. When a city is chosen, the array is shortened - * and the procedure repeated. + * Randomly generates a legal "traveling salesman" tour + * (i.e. where each point is visited only once.) + * Essentially, this routine fills an array with all possible + * points on the tour and randomly chooses the 'next' city from + * this array. When a city is chosen, the array is shortened + * and the procedure repeated. * */ void -init_tour(Gene *tour, int num_gene) +init_tour(Gene * tour, int num_gene) { -Gene *tmp; -int remainder; -int next, i; + Gene *tmp; + int remainder; + int next, + i; -tmp = (Gene *) palloc (num_gene*sizeof(Gene)); - -for(i = 0; i < num_gene; i++) { - tmp[i] = (Gene) i+1; /* builds tours "1 - 2 - 3" etc. */ - } + tmp = (Gene *) palloc(num_gene * sizeof(Gene)); -remainder = num_gene - 1; + for (i = 0; i < num_gene; i++) + { + tmp[i] = (Gene) i + 1; /* builds tours "1 - 2 - 3" etc. */ + } -for(i = 0; i < num_gene; i++) { - next = (int) geqo_randint(remainder, 0); /* choose city between 0 and remainder */ - tour[i] = tmp[next]; - tmp[next] = tmp[remainder]; - remainder--; - } + remainder = num_gene - 1; -pfree(tmp); -} + for (i = 0; i < num_gene; i++) + { + next = (int) geqo_randint(remainder, 0); /* choose city between 0 + * and remainder */ + tour[i] = tmp[next]; + tmp[next] = tmp[remainder]; + remainder--; + } + + pfree(tmp); +} /* alloc_city_table-- * - * allocate memory for city table + * allocate memory for city table * */ -City * +City * alloc_city_table(int num_gene) { - City *city_table; + City *city_table; - /* palloc one extra location so that nodes numbered - 1..n can be indexed directly; 0 will not be used */ + /* + * 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)); + city_table = (City *) palloc((num_gene + 1) * sizeof(City)); - return (city_table); - } + return (city_table); +} /* free_city_table-- * - * deallocate memory of city table + * deallocate memory of city table * */ - void - free_city_table(City *city_table) - { - pfree(city_table); - } - +void +free_city_table(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 0c6502003bd..820de485fe4 100644 --- a/src/backend/optimizer/geqo/geqo_selection.c +++ b/src/backend/optimizer/geqo/geqo_selection.c @@ -1,36 +1,36 @@ /*------------------------------------------------------------------------- * * geqo_selection.c-- - * linear selection scheme for the genetic query optimizer + * linear selection scheme for the genetic query optimizer * * Copyright (c) 1994, Regents of the University of California * - * $Id: geqo_selection.c,v 1.1 1997/02/19 12:57:46 scrappy Exp $ + * $Id: geqo_selection.c,v 1.2 1997/09/07 04:43:24 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 * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ /* 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. */ -/* */ +/* */ +/* 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 <math.h> @@ -55,49 +55,51 @@ #include "optimizer/geqo_copy.h" #include "optimizer/geqo_random.h" -static int linear(int max, double bias); +static int linear(int max, double bias); /* geqo_selection-- * - * according to bias described by input parameters, - * second genes are selected from the pool + * according to bias described by input parameters, + * second genes are selected from the pool */ void -geqo_selection (Chromosome *momma, Chromosome *daddy, Pool *pool, double bias) +geqo_selection(Chromosome * momma, Chromosome * daddy, Pool * pool, double bias) { - int first, second; - - first = (int) linear(pool->size, bias); - second = (int) linear(pool->size, bias); - - if (pool->size > 1) { - while(first==second) - second = (int) linear(pool->size, bias); - } - - geqo_copy (momma, &pool->data[first], pool->string_length); - geqo_copy (daddy, &pool->data[second], pool->string_length); + int first, + second; + + first = (int) linear(pool->size, bias); + second = (int) linear(pool->size, bias); + + if (pool->size > 1) + { + while (first == second) + second = (int) linear(pool->size, bias); + } + + geqo_copy(momma, &pool->data[first], pool->string_length); + geqo_copy(daddy, &pool->data[second], pool->string_length); } /* linear-- - * generates random integer between 0 and input max number - * using input linear bias + * generates random integer between 0 and input max number + * using input linear bias * - * probability distribution function is: f(x) = bias - 2(bias - 1)x - * bias = (prob of first rule) / (prob of middle rule) + * probability distribution function is: f(x) = bias - 2(bias - 1)x + * bias = (prob of first rule) / (prob of middle rule) * */ static int -linear(int pool_size, double bias) /* bias is y-intercept of linear distribution */ +linear(int pool_size, double bias) /* bias is y-intercept of linear + * distribution */ { - double index; /* index between 0 and pop_size */ - double max = (double) pool_size; + double index; /* index between 0 and pop_size */ + double max = (double) pool_size; - index = - max*( bias - sqrt ( (bias*bias) - 4.0*(bias-1.0)*geqo_rand() ) ) - / 2.0 / (bias-1.0); + index = + max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand())) + / 2.0 / (bias - 1.0); - return((int) index); + return ((int) index); } - diff --git a/src/backend/optimizer/geqo/minspantree.c b/src/backend/optimizer/geqo/minspantree.c index 4e4c2ad11b4..1fcc2569478 100644 --- a/src/backend/optimizer/geqo/minspantree.c +++ b/src/backend/optimizer/geqo/minspantree.c @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------ * * minspantree.c-- -* routine to sort a join graph which is including cycles +* routine to sort a join graph which is including cycles * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION -* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/Attic/minspantree.c,v 1.1 1997/02/19 12:57:50 scrappy Exp $ +* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/Attic/minspantree.c,v 1.2 1997/09/07 04:43:25 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -33,166 +33,181 @@ /* * minspantree-- - * The function minspantree computes the minimum spanning tree - * for a given number of nodes and a given distance function. - * For each pair of nodes found to be connected, a given - * function is called. Nodes are denoted by the integer numbers - * 1 .. number_of_joins, where number_of_joins is the number of nodes. + * The function minspantree computes the minimum spanning tree + * for a given number of nodes and a given distance function. + * For each pair of nodes found to be connected, a given + * function is called. Nodes are denoted by the integer numbers + * 1 .. number_of_joins, where number_of_joins is the number of nodes. */ void -minspantree(Query *root, List *join_rels, Rel *garel) +minspantree(Query * root, List * join_rels, Rel * garel) { - int number_of_rels = length(root->base_relation_list_); - int number_of_joins = length(join_rels); - int *connectto; - /* connectto[i] = 0, if node i is already connected */ - /* to the tree, otherwise connectto[i] is the node */ - /* nearest to i, which is already connected. */ - - Cost *disttoconnect; /* disttoconnect[i]: distance between i and connectto[i] */ - - Cost dist, /* temporary */ - mindist; /* minimal distance between connected and unconnected node */ - - Cost mstlength = 0.0; /* the total length of the minimum spanning tree */ - - int count; - int n, /* newly attached node */ - nextn, /* next node to be attached */ - tempn; - - int i, id1, id2; - List *r = NIL; - Rel *joinrel = NULL; - Rel **tmprel_array; - - - /* allocate memory for matrix tmprel_array[x][y] */ - tmprel_array = (Rel **) palloc((number_of_rels+1)*sizeof(Rel *)); - for (i=0; i<=number_of_rels; i++) - (tmprel_array[i] = (Rel *) palloc ((number_of_rels+1)*sizeof(Rel))); - - /* read relations of join-relations into tmprel_array */ - - foreach(r, join_rels) { - joinrel = (Rel *)lfirst(r); - id1 = (int)lfirst(joinrel->relids); - id2 = (int)lsecond(joinrel->relids); - - if (id1 > id2) { - tmprel_array[id2][id1] = *(Rel *)joinrel; - } - else { - tmprel_array[id1][id2] = *(Rel *)joinrel; /* ever reached? */ - } - } - - /* Trivial special cases handled first */ - /* garel is global in "tsp.h" */ - - if (number_of_joins <= 2) - { - i=1; - foreach(r, join_rels) { - garel[i] = *(Rel *)lfirst(r); - i++; - } - } - - - else if (number_of_joins == 3) - { - Rel *rel12 = (Rel *) &tmprel_array[1][2]; - Rel *rel13 = (Rel *) &tmprel_array[1][3]; - Rel *rel23 = (Rel *) &tmprel_array[2][3]; - if (rel12->cheapestpath->path_cost > rel13->cheapestpath->path_cost) - { - garel[1] = tmprel_array[1][3]; - if (rel12->cheapestpath->path_cost > rel23->cheapestpath->path_cost) + int number_of_rels = length(root->base_relation_list_); + int number_of_joins = length(join_rels); + int *connectto; + + /* connectto[i] = 0, if node i is already connected */ + /* to the tree, otherwise connectto[i] is the node */ + /* nearest to i, which is already connected. */ + + Cost *disttoconnect; /* disttoconnect[i]: distance + * between i and connectto[i] */ + + Cost dist, /* temporary */ + mindist; /* minimal distance between connected and + * unconnected node */ + + Cost mstlength = 0.0; /* the total length of the minimum + * spanning tree */ + + int count; + int n, /* newly attached node */ + nextn, /* next node to be attached */ + tempn; + + int i, + id1, + id2; + List *r = NIL; + Rel *joinrel = NULL; + Rel **tmprel_array; + + + /* allocate memory for matrix tmprel_array[x][y] */ + tmprel_array = (Rel **) palloc((number_of_rels + 1) * sizeof(Rel *)); + for (i = 0; i <= number_of_rels; i++) + (tmprel_array[i] = (Rel *) palloc((number_of_rels + 1) * sizeof(Rel))); + + /* read relations of join-relations into tmprel_array */ + + foreach(r, join_rels) { - garel[2] = tmprel_array[2][3]; + joinrel = (Rel *) lfirst(r); + id1 = (int) lfirst(joinrel->relids); + id2 = (int) lsecond(joinrel->relids); + + if (id1 > id2) + { + tmprel_array[id2][id1] = *(Rel *) joinrel; + } + else + { + tmprel_array[id1][id2] = *(Rel *) joinrel; /* ever reached? */ + } } - else + + /* Trivial special cases handled first */ + /* garel is global in "tsp.h" */ + + if (number_of_joins <= 2) { - garel[2] = tmprel_array[1][2]; + i = 1; + foreach(r, join_rels) + { + garel[i] = *(Rel *) lfirst(r); + i++; + } } - } - else - { - garel[1] = tmprel_array[1][2]; - if (rel13->cheapestpath->path_cost > rel23->cheapestpath->path_cost) + + + else if (number_of_joins == 3) { - garel[2] = tmprel_array[2][3]; + Rel *rel12 = (Rel *) & tmprel_array[1][2]; + Rel *rel13 = (Rel *) & tmprel_array[1][3]; + Rel *rel23 = (Rel *) & tmprel_array[2][3]; + + if (rel12->cheapestpath->path_cost > rel13->cheapestpath->path_cost) + { + garel[1] = tmprel_array[1][3]; + if (rel12->cheapestpath->path_cost > rel23->cheapestpath->path_cost) + { + garel[2] = tmprel_array[2][3]; + } + else + { + garel[2] = tmprel_array[1][2]; + } + } + else + { + garel[1] = tmprel_array[1][2]; + if (rel13->cheapestpath->path_cost > rel23->cheapestpath->path_cost) + { + garel[2] = tmprel_array[2][3]; + } + else + { + garel[2] = tmprel_array[1][3]; + } + } } + + + /* now the general case */ else { - garel[2] = tmprel_array[1][3]; - } - } - } - - - /* now the general case */ - else - { - connectto = (int *) palloc((number_of_rels+1)*sizeof(int)); - disttoconnect = (Cost *) palloc((number_of_rels+1)*sizeof(Cost)); - - nextn = 2; - for (tempn = 2; tempn <= number_of_rels; tempn++ ) - { - connectto[tempn] = 1; - disttoconnect[tempn] = (Cost) MAXFLOAT; - } - - joinrel = NULL; - n = 1; - i = 1; - for (count = 2; count <= number_of_rels; count++ ) - { - connectto[n] = 0; - mindist = (Cost) MAXFLOAT; - for (tempn = 2; tempn <= number_of_rels; tempn++ ) - { - if (connectto[tempn] != 0) - { - if (n > tempn) { - joinrel = (Rel *) &tmprel_array[tempn][n]; - } - else { - joinrel = (Rel *) &tmprel_array[n][tempn]; - } - dist = joinrel->cheapestpath->path_cost; - - if (dist < disttoconnect[tempn]) - { - disttoconnect[tempn] = dist; - connectto[tempn] = n; - } - if (disttoconnect[tempn] < mindist) - { - mindist = disttoconnect[tempn]; - nextn = tempn; + connectto = (int *) palloc((number_of_rels + 1) * sizeof(int)); + disttoconnect = (Cost *) palloc((number_of_rels + 1) * sizeof(Cost)); + + nextn = 2; + for (tempn = 2; tempn <= number_of_rels; tempn++) + { + connectto[tempn] = 1; + disttoconnect[tempn] = (Cost) MAXFLOAT; + } + + joinrel = NULL; + n = 1; + i = 1; + for (count = 2; count <= number_of_rels; count++) + { + connectto[n] = 0; + mindist = (Cost) MAXFLOAT; + for (tempn = 2; tempn <= number_of_rels; tempn++) + { + if (connectto[tempn] != 0) + { + if (n > tempn) + { + joinrel = (Rel *) & tmprel_array[tempn][n]; + } + else + { + joinrel = (Rel *) & tmprel_array[n][tempn]; + } + dist = joinrel->cheapestpath->path_cost; + + if (dist < disttoconnect[tempn]) + { + disttoconnect[tempn] = dist; + connectto[tempn] = n; + } + if (disttoconnect[tempn] < mindist) + { + mindist = disttoconnect[tempn]; + nextn = tempn; + } + } + } + n = nextn; + if (n > connectto[n]) + { + garel[i] = tmprel_array[connectto[n]][n]; + } + else + { + garel[i] = tmprel_array[n][connectto[n]]; + } + i++; + } + + pfree(connectto); + pfree(disttoconnect); + } - } - } - n = nextn; - if (n > connectto[n]) { - garel[i] = tmprel_array[connectto[n]][n]; - } - else { - garel[i] = tmprel_array[n][connectto[n]]; - } - i++; - } - - pfree(connectto); - pfree(disttoconnect); - - } - - for (i=0; i<=number_of_rels; i++) pfree(tmprel_array[i]); - pfree(tmprel_array); -} + for (i = 0; i <= number_of_rels; i++) + pfree(tmprel_array[i]); + pfree(tmprel_array); +} |