2 $PostgreSQL: pgsql/doc/src/sgml/geqo.sgml,v 1.29 2005/02/21 02:21:00 neilc Exp $
9 <firstname>Martin</firstname>
10 <surname>Utesch</surname>
13 University of Mining and Technology
16 Institute of Automatic Control
28 <date>1997-10-02</date>
31 <title id="geqo-title">Genetic Query Optimizer</title>
37 Written by Martin Utesch (<email>utesch@aut.tu-freiberg.de</email>)
38 for the Institute of Automatic Control at the University of Mining and Technology in Freiberg, Germany.
43 <sect1 id="geqo-intro">
44 <title>Query Handling as a Complex Optimization Problem</title>
47 Among all relational operators the most difficult one to process
48 and optimize is the <firstterm>join</firstterm>. The number of
49 alternative plans to answer a query grows exponentially with the
50 number of joins included in it. Further optimization effort is
51 caused by the support of a variety of <firstterm>join
52 methods</firstterm> (e.g., nested loop, hash join, merge join in
53 <productname>PostgreSQL</productname>) to process individual joins
54 and a diversity of <firstterm>indexes</firstterm> (e.g., R-tree,
55 B-tree, hash in <productname>PostgreSQL</productname>) as access
60 The current <productname>PostgreSQL</productname> optimizer
61 implementation performs a <firstterm>near-exhaustive
62 search</firstterm> over the space of alternative strategies. This
63 algorithm, first introduced in the <quote>System R</quote>
64 database, produces a near-optimal join order, but can take an
65 enormous amount of time and memory space when the number of joins
66 in the query grows large. This makes the ordinary
67 <productname>PostgreSQL</productname> query optimizer
68 inappropriate for queries that join a large number of tables.
72 The Institute of Automatic Control at the University of Mining and
73 Technology, in Freiberg, Germany, encountered the described problems as its
74 folks wanted to take the <productname>PostgreSQL</productname> DBMS as the backend for a decision
75 support knowledge based system for the maintenance of an electrical
76 power grid. The DBMS needed to handle large join queries for the
77 inference machine of the knowledge based system.
81 Performance difficulties in exploring the space of possible query
82 plans created the demand for a new optimization technique to be developed.
86 In the following we describe the implementation of a
87 <firstterm>Genetic Algorithm</firstterm> to solve the join
88 ordering problem in a manner that is efficient for queries
89 involving large numbers of joins.
93 <sect1 id="geqo-intro2">
94 <title>Genetic Algorithms</title>
97 The genetic algorithm (<acronym>GA</acronym>) is a heuristic optimization method which
99 nondeterministic, randomized search. The set of possible solutions for the
100 optimization problem is considered as a
101 <firstterm>population</firstterm> of <firstterm>individuals</firstterm>.
102 The degree of adaptation of an individual to its environment is specified
103 by its <firstterm>fitness</firstterm>.
107 The coordinates of an individual in the search space are represented
108 by <firstterm>chromosomes</firstterm>, in essence a set of character
109 strings. A <firstterm>gene</firstterm> is a
110 subsection of a chromosome which encodes the value of a single parameter
111 being optimized. Typical encodings for a gene could be <firstterm>binary</firstterm> or
112 <firstterm>integer</firstterm>.
116 Through simulation of the evolutionary operations <firstterm>recombination</firstterm>,
117 <firstterm>mutation</firstterm>, and
118 <firstterm>selection</firstterm> new generations of search points are found
119 that show a higher average fitness than their ancestors.
123 According to the <systemitem class="resource">comp.ai.genetic</> <acronym>FAQ</acronym> it cannot be stressed too
124 strongly that a <acronym>GA</acronym> is not a pure random search for a solution to a
125 problem. A <acronym>GA</acronym> uses stochastic processes, but the result is distinctly
126 non-random (better than random).
129 <figure id="geqo-diagram">
130 <title>Structured Diagram of a Genetic Algorithm</title>
132 <informaltable frame="none">
137 <entry>generation of ancestors at a time t</entry>
141 <entry>P''(t)</entry>
142 <entry>generation of descendants at a time t</entry>
148 <literallayout class="monospaced">
149 +=========================================+
150 |>>>>>>>>>>> Algorithm GA <<<<<<<<<<<<<<|
151 +=========================================+
152 | INITIALIZE t := 0 |
153 +=========================================+
155 +=========================================+
156 | evaluate FITNESS of P(t) |
157 +=========================================+
158 | while not STOPPING CRITERION do |
159 | +-------------------------------------+
160 | | P'(t) := RECOMBINATION{P(t)} |
161 | +-------------------------------------+
162 | | P''(t) := MUTATION{P'(t)} |
163 | +-------------------------------------+
164 | | P(t+1) := SELECTION{P''(t) + P(t)} |
165 | +-------------------------------------+
166 | | evaluate FITNESS of P''(t) |
167 | +-------------------------------------+
169 +===+=====================================+
174 <sect1 id="geqo-pg-intro">
175 <title>Genetic Query Optimization (<acronym>GEQO</acronym>) in PostgreSQL</title>
178 The <acronym>GEQO</acronym> module approaches the query
179 optimization problem as though it were the well-known traveling salesman
180 problem (<acronym>TSP</acronym>).
181 Possible query plans are encoded as integer strings. Each string
182 represents the join order from one relation of the query to the next.
183 For example, the join tree
184 <literallayout class="monospaced">
190 is encoded by the integer string '4-1-3-2',
191 which means, first join relation '4' and '1', then '3', and
192 then '2', where 1, 2, 3, 4 are relation IDs within the
193 <productname>PostgreSQL</productname> optimizer.
197 Parts of the <acronym>GEQO</acronym> module are adapted from D. Whitley's Genitor
202 Specific characteristics of the <acronym>GEQO</acronym>
203 implementation in <productname>PostgreSQL</productname>
206 <itemizedlist spacing="compact" mark="bullet">
209 Usage of a <firstterm>steady state</firstterm> <acronym>GA</acronym> (replacement of the least fit
210 individuals in a population, not whole-generational replacement)
211 allows fast convergence towards improved query plans. This is
212 essential for query handling with reasonable time;
218 Usage of <firstterm>edge recombination crossover</firstterm>
219 which is especially suited to keep edge losses low for the
220 solution of the <acronym>TSP</acronym> by means of a
221 <acronym>GA</acronym>;
227 Mutation as genetic operator is deprecated so that no repair
228 mechanisms are needed to generate legal <acronym>TSP</acronym> tours.
235 The <acronym>GEQO</acronym> module allows
236 the <productname>PostgreSQL</productname> query optimizer to
237 support large join queries effectively through
238 non-exhaustive search.
241 <sect2 id="geqo-future">
242 <title>Future Implementation Tasks for
243 <productname>PostgreSQL</> <acronym>GEQO</acronym></title>
246 Work is still needed to improve the genetic algorithm parameter
248 In file <filename>src/backend/optimizer/geqo/geqo_main.c</filename>,
250 <function>gimme_pool_size</function> and <function>gimme_number_generations</function>,
251 we have to find a compromise for the parameter settings
252 to satisfy two competing demands:
253 <itemizedlist spacing="compact">
256 Optimality of the query plan
268 At a more basic level, it is not clear that solving query optimization
269 with a GA algorithm designed for TSP is appropriate. In the TSP case,
270 the cost associated with any substring (partial tour) is independent
271 of the rest of the tour, but this is certainly not true for query
272 optimization. Thus it is questionable whether edge recombination
273 crossover is the most effective mutation procedure.
279 <sect1 id="geqo-biblio">
280 <title>Further Reading</title>
283 The following resources contain additional information about
289 <ulink url="http://surf.de.uu.net/encore/www/">The Hitch-Hiker's
290 Guide to Evolutionary Computation</ulink> (FAQ for <ulink
291 url="news://comp.ai.genetic">comp.ai.genetic</ulink>)
297 <ulink url="http://www.red3d.com/cwr/evolve.html">Evolutionary
298 Computation and its application to art and design</ulink> by
305 <xref linkend="ELMA04">
311 <xref linkend="FONG">
320 <!-- Keep this comment at the end of the file
325 sgml-minimize-attributes:nil
326 sgml-always-quote-attributes:t
329 sgml-parent-document:nil
330 sgml-default-dtd-file:"./reference.ced"
331 sgml-exposed-tags:nil
332 sgml-local-catalogs:("/usr/lib/sgml/catalog")
333 sgml-local-ecat-files:nil