From 0c2629efaa4222b81309a558e66c6f9214ce7333 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 16 Dec 2000 22:44:47 +0000 Subject: [PATCH] Update some obsolete info about GEQO. --- doc/src/sgml/geqo.sgml | 89 ++++++++++-------------------------------- 1 file changed, 21 insertions(+), 68 deletions(-) diff --git a/doc/src/sgml/geqo.sgml b/doc/src/sgml/geqo.sgml index 0f12b3db3c3..546a864901b 100644 --- a/doc/src/sgml/geqo.sgml +++ b/doc/src/sgml/geqo.sgml @@ -1,5 +1,5 @@ @@ -49,7 +49,7 @@ Genetic Optimizer grows exponentially with the number of joins included in it. Further optimization effort is caused by the support of a variety of join methods - (e.g., nested loop, index scan, merge join in Postgres) to + (e.g., nested loop, hash join, merge join in Postgres) to process individual joins and a diversity of indices (e.g., r-tree, b-tree, hash in Postgres) as access paths for relations. @@ -57,8 +57,8 @@ Genetic Optimizer The current Postgres optimizer - implementation performs a near- - exhaustive search over the space of alternative strategies. This query + implementation performs a near-exhaustive search + over the space of alternative strategies. This query optimization technique is inadequate to support database application domains that involve the need for extensive queries, such as artificial intelligence. @@ -74,8 +74,8 @@ Genetic Optimizer - Performance difficulties within exploring the space of possible query - plans arose the demand for a new optimization technique being developed. + Performance difficulties in exploring the space of possible query + plans created the demand for a new optimization technique being developed. @@ -88,10 +88,11 @@ Genetic Optimizer Genetic Algorithms (<acronym>GA</acronym>) - The GA is a heuristic optimization method which operates through + The GA is a heuristic optimization method which + operates through determined, randomized search. The set of possible solutions for the optimization problem is considered as a - erm>populaerm> of individuals. + population of individuals. The degree of adaption of an individual to its environment is specified by its fitness. @@ -167,7 +168,8 @@ P''(t) generation of descendants at a time t is encoded by the integer string '4-1-3-2', which means, first join relation '4' and '1', then '3', and - then '2', where 1, 2, 3, 4 are relids in Postgres. + then '2', where 1, 2, 3, 4 are relids within the + Postgres optimizer. @@ -192,9 +194,10 @@ P''(t) generation of descendants at a time t - Usage of edge recombination crossover which is especially suited + Usage of edge recombination crossover which is + especially suited to keep edge losses low for the solution of the - crocronym> by means of a GA; + TSP by means of a GA; @@ -208,40 +211,19 @@ P''(t) generation of descendants at a time t - The GEQO module gives the following benefits to - the Postgres DBMS - compared to the Postgres query optimizer implementation: - - - - - Handling of large join queries through non-exhaustive search; - - - - - - Improved cost size approximation of query plans since no longer - plan merging is needed (the GEQO module evaluates the cost for a - query plan as an individual). - - - + The GEQO module allows + the Postgres query optimizer to + support large join queries effectively through + non-exhaustive search. - - - + Future Implementation Tasks for <productname>PostgreSQL</> <acronym>GEQO</acronym> - - Basic Improvements - - - Improve genetic algorithm parameter settings - + Work is still needed to improve the genetic algorithm parameter + settings. In file backend/optimizer/geqo/geqo_params.c, routines gimme_pool_size and gimme_number_generations, we have to find a compromise for the parameter settings @@ -259,38 +241,9 @@ P''(t) generation of descendants at a time t - - - - Find better solution for integer overflow - - - In file backend/optimizer/geqo/geqo_eval.c, routine - geqo_joinrel_size, - the present hack for MAXINT overflow is to set the Postgres integer - value of rel->size to its logarithm. - Modifications of Rel in backend/nodes/relation.h will - surely have severe impacts on the whole Postgres implementation. - - - - - Find solution for exhausted memory - - Memory exhaustion may occur with more than 10 relations involved in a query. - In file backend/optimizer/geqo/geqo_eval.c, routine - gimme_tree is recursively called. - Maybe I forgot something to be freed correctly, but I dunno what. - Of course the rel data structure of the - join keeps growing and - growing the more relations are packed into it. - Suggestions are welcome :-( - - - References -- 2.39.5