granicus.if.org Git - postgresql/blob - doc/src/sgml/geqo.sgml

   1 <!--
   2 $Header: /cvsroot/pgsql/doc/src/sgml/geqo.sgml,v 1.25 2003/11/24 19:08:02 petere Exp $
   3 Genetic Optimizer
   4 -->
   5
   6  <chapter id="geqo">
   7   <chapterinfo>
   8    <author>
   9     <firstname>Martin</firstname>
  10     <surname>Utesch</surname>
  11     <affiliation>
  12      <orgname>
  13       University of Mining and Technology
  14      </orgname>
  15      <orgdiv>
  16       Institute of Automatic Control
  17      </orgdiv>
  18      <address>
  19       <city>
  20        Freiberg
  21       </city>
  22       <country>
  23        Germany
  24       </country>
  25      </address>
  26     </affiliation>
  27    </author>
  28    <date>1997-10-02</date>
  29   </chapterinfo>
  30
  31   <title id="geqo-title">Genetic Query Optimizer</title>
  32
  33   <para>
  34    <note>
  35     <title>Author</title>
  36     <para>
  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.
  39     </para>
  40    </note>
  41   </para>
  42
  43   <sect1 id="geqo-intro">
  44    <title>Query Handling as a Complex Optimization Problem</title>
  45
  46    <para>
  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
  56     paths for relations.
  57    </para>
  58
  59    <para>
  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 database application domains that involve the
  69     need for extensive queries, such as artificial intelligence.
  70    </para>
  71
  72    <para>
  73     The Institute of Automatic Control at the University of Mining and
  74     Technology, in Freiberg, Germany, encountered the described problems as its
  75     folks wanted to take the <productname>PostgreSQL</productname> DBMS as the backend for a decision
  76     support knowledge based system for the maintenance of an electrical
  77     power grid. The DBMS needed to handle large join queries for the
  78     inference machine of the knowledge based system.
  79    </para>
  80
  81    <para>
  82     Performance difficulties in exploring the space of possible query
  83     plans created the demand for a new optimization technique to be developed.
  84    </para>
  85
  86    <para>
  87     In the following we describe the implementation of a
  88     <firstterm>Genetic Algorithm</firstterm> to solve the join
  89     ordering problem in a manner that is efficient for queries
  90     involving large numbers of joins.
  91    </para>
  92   </sect1>
  93
  94   <sect1 id="geqo-intro2">
  95    <title>Genetic Algorithms</title>
  96
  97    <para>
  98     The genetic algorithm (<acronym>GA</acronym>) is a heuristic optimization method which
  99     operates through
 100     determined, randomized search. The set of possible solutions for the
 101     optimization problem is considered as a
 102     <firstterm>population</firstterm> of <firstterm>individuals</firstterm>.
 103     The degree of adaptation of an individual to its environment is specified
 104     by its <firstterm>fitness</firstterm>.
 105    </para>
 106
 107    <para>
 108     The coordinates of an individual in the search space are represented
 109     by <firstterm>chromosomes</firstterm>, in essence a set of character
 110     strings. A <firstterm>gene</firstterm> is a
 111     subsection of a chromosome which encodes the value of a single parameter
 112     being optimized. Typical encodings for a gene could be <firstterm>binary</firstterm> or
 113     <firstterm>integer</firstterm>.
 114    </para>
 115
 116    <para>
 117     Through simulation of the evolutionary operations <firstterm>recombination</firstterm>,
 118     <firstterm>mutation</firstterm>, and
 119     <firstterm>selection</firstterm> new generations of search points are found
 120     that show a higher average fitness than their ancestors.
 121    </para>
 122
 123    <para>
 124     According to the <systemitem class="resource">comp.ai.genetic</> <acronym>FAQ</acronym> it cannot be stressed too
 125     strongly that a <acronym>GA</acronym> is not a pure random search for a solution to a
 126     problem. A <acronym>GA</acronym> uses stochastic processes, but the result is distinctly
 127     non-random (better than random).
 128    </para>
 129
 130    <figure id="geqo-diagram">
 131     <title>Structured Diagram of a Genetic Algorithm</title>
 132
 133     <informaltable frame="none">
 134      <tgroup cols="2">
 135       <tbody>
 136        <row>
 137         <entry>P(t)</entry>
 138         <entry>generation of ancestors at a time t</entry>
 139        </row>
 140
 141        <row>
 142         <entry>P''(t)</entry>
 143         <entry>generation of descendants at a time t</entry>
 144        </row>
 145       </tbody>
 146      </tgroup>
 147     </informaltable>
 148
 149 <literallayout class="monospaced">
 150 +=========================================+
 151 |>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
 152 +=========================================+
 153 | INITIALIZE t := 0                       |
 154 +=========================================+
 155 | INITIALIZE P(t)                         |
 156 +=========================================+
 157 | evaluate FITNESS of P(t)                |
 158 +=========================================+
 159 | while not STOPPING CRITERION do         |
 160 |   +-------------------------------------+
 161 |   | P'(t)  := RECOMBINATION{P(t)}       |
 162 |   +-------------------------------------+
 163 |   | P''(t) := MUTATION{P'(t)}           |
 164 |   +-------------------------------------+
 165 |   | P(t+1) := SELECTION{P''(t) + P(t)}  |
 166 |   +-------------------------------------+
 167 |   | evaluate FITNESS of P''(t)          |
 168 |   +-------------------------------------+
 169 |   | t := t + 1                          |
 170 +===+=====================================+
 171 </literallayout>
 172    </figure>
 173   </sect1>
 174
 175   <sect1 id="geqo-pg-intro">
 176    <title>Genetic Query Optimization (<acronym>GEQO</acronym>) in PostgreSQL</title>
 177
 178    <para>
 179     The <acronym>GEQO</acronym> module is intended for the solution of the query
 180     optimization problem similar to a traveling salesman 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     E. g., the query tree
 184 <literallayout class="monospaced">
 185    /\
 186   /\ 2
 187  /\ 3
 188 4  1
 189 </literallayout>
 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.
 194    </para>
 195
 196    <para>
 197     Parts of the <acronym>GEQO</acronym> module are adapted from D. Whitley's Genitor
 198     algorithm.
 199    </para>
 200
 201    <para>
 202     Specific characteristics of the <acronym>GEQO</acronym>
 203     implementation in <productname>PostgreSQL</productname>
 204     are:
 205
 206     <itemizedlist spacing="compact" mark="bullet">
 207      <listitem>
 208       <para>
 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;
 213       </para>
 214      </listitem>
 215
 216      <listitem>
 217       <para>
 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>;
 222       </para>
 223      </listitem>
 224
 225      <listitem>
 226       <para>
 227        Mutation as genetic operator is deprecated so that no repair
 228        mechanisms are needed to generate legal <acronym>TSP</acronym> tours.
 229       </para>
 230      </listitem>
 231     </itemizedlist>
 232    </para>
 233
 234    <para>
 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.
 239    </para>
 240
 241   <sect2 id="geqo-future">
 242    <title>Future Implementation Tasks for
 243     <productname>PostgreSQL</> <acronym>GEQO</acronym></title>
 244
 245      <para>
 246       Work is still needed to improve the genetic algorithm parameter
 247       settings.
 248       In file <filename>backend/optimizer/geqo/geqo_params.c</filename>, routines
 249       <function>gimme_pool_size</function> and <function>gimme_number_generations</function>,
 250       we have to find a compromise for the parameter settings
 251       to satisfy two competing demands:
 252       <itemizedlist spacing="compact">
 253        <listitem>
 254         <para>
 255          Optimality of the query plan
 256         </para>
 257        </listitem>
 258        <listitem>
 259         <para>
 260          Computing time
 261         </para>
 262        </listitem>
 263       </itemizedlist>
 264      </para>
 265
 266    </sect2>
 267   </sect1>
 268
 269  <sect1 id="geqo-biblio">
 270   <title>Further Readings</title>
 271
 272   <para>
 273    The following resources contain additional information about
 274    genetic algorithms:
 275
 276    <itemizedlist>
 277     <listitem>
 278      <para>
 279       <ulink url="http://surf.de.uu.net/encore/www/">The Hitch-Hiker's
 280       Guide to Evolutionary Computation</ulink> (FAQ for <ulink
 281       url="news://comp.ai.genetic">comp.ai.genetic</ulink>)
 282      </para>
 283     </listitem>
 284
 285     <listitem>
 286      <para>
 287       <ulink url="http://www.red3d.com/cwr/evolve.html">Evolutionary
 288        Computation and its application to art and design</ulink> by
 289       Craig Reynolds
 290      </para>
 291     </listitem>
 292
 293     <listitem>
 294      <para>
 295       <xref linkend="ELMA99">
 296      </para>
 297     </listitem>
 298
 299     <listitem>
 300      <para>
 301       <xref linkend="FONG">
 302      </para>
 303     </listitem>
 304    </itemizedlist>
 305   </para>
 306
 307  </sect1>
 308 </chapter>
 309
 310 <!-- Keep this comment at the end of the file
 311 Local variables:
 312 mode:sgml
 313 sgml-omittag:nil
 314 sgml-shorttag:t
 315 sgml-minimize-attributes:nil
 316 sgml-always-quote-attributes:t
 317 sgml-indent-step:1
 318 sgml-indent-data:t
 319 sgml-parent-document:nil
 320 sgml-default-dtd-file:"./reference.ced"
 321 sgml-exposed-tags:nil
 322 sgml-local-catalogs:("/usr/lib/sgml/catalog")
 323 sgml-local-ecat-files:nil
 324 End:
 325 -->