I386LINUX/util/I386LINUX/doc/postgresql/html/geqo-pg-intro.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <HTML
   3 ><HEAD
   4 ><TITLE
   5 >Genetic Query Optimization (GEQO) in PostgreSQL</TITLE
   6 ><META
   7 NAME="GENERATOR"
   8 CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
   9 REV="MADE"
  10 HREF="mailto:pgsql-docs@postgresql.org"><LINK
  11 REL="HOME"
  12 TITLE="PostgreSQL 7.4.1 Documentation"
  13 HREF="index.html"><LINK
  14 REL="UP"
  15 TITLE="Genetic Query Optimizer"
  16 HREF="geqo.html"><LINK
  17 REL="PREVIOUS"
  18 TITLE="Genetic Algorithms"
  19 HREF="geqo-intro2.html"><LINK
  20 REL="NEXT"
  21 TITLE="Further Readings"
  22 HREF="geqo-biblio.html"><LINK
  23 REL="STYLESHEET"
  24 TYPE="text/css"
  25 HREF="stylesheet.css"><META
  26 NAME="creation"
  27 CONTENT="2003-12-22T03:48:47"></HEAD
  28 ><BODY
  29 CLASS="SECT1"
  30 ><DIV
  31 CLASS="NAVHEADER"
  32 ><TABLE
  33 SUMMARY="Header navigation table"
  34 WIDTH="100%"
  35 BORDER="0"
  36 CELLPADDING="0"
  37 CELLSPACING="0"
  38 ><TR
  39 ><TH
  40 COLSPAN="5"
  41 ALIGN="center"
  42 VALIGN="bottom"
  43 >PostgreSQL 7.4.1 Documentation</TH
  44 ></TR
  45 ><TR
  46 ><TD
  47 WIDTH="10%"
  48 ALIGN="left"
  49 VALIGN="top"
  50 ><A
  51 HREF="geqo-intro2.html"
  52 ACCESSKEY="P"
  53 >Prev</A
  54 ></TD
  55 ><TD
  56 WIDTH="10%"
  57 ALIGN="left"
  58 VALIGN="top"
  59 ><A
  60 HREF="geqo.html"
  61 >Fast Backward</A
  62 ></TD
  63 ><TD
  64 WIDTH="60%"
  65 ALIGN="center"
  66 VALIGN="bottom"
  67 >Chapter 48. Genetic Query Optimizer</TD
  68 ><TD
  69 WIDTH="10%"
  70 ALIGN="right"
  71 VALIGN="top"
  72 ><A
  73 HREF="geqo.html"
  74 >Fast Forward</A
  75 ></TD
  76 ><TD
  77 WIDTH="10%"
  78 ALIGN="right"
  79 VALIGN="top"
  80 ><A
  81 HREF="geqo-biblio.html"
  82 ACCESSKEY="N"
  83 >Next</A
  84 ></TD
  85 ></TR
  86 ></TABLE
  87 ><HR
  88 ALIGN="LEFT"
  89 WIDTH="100%"></DIV
  90 ><DIV
  91 CLASS="SECT1"
  92 ><H1
  93 CLASS="SECT1"
  94 ><A
  95 NAME="GEQO-PG-INTRO"
  96 >48.3. Genetic Query Optimization (<ACRONYM
  97 CLASS="ACRONYM"
  98 >GEQO</ACRONYM
  99 >) in PostgreSQL</A
 100 ></H1
 101 ><P
 102 >    The <ACRONYM
 103 CLASS="ACRONYM"
 104 >GEQO</ACRONYM
 105 > module is intended for the solution of the query
 106     optimization problem similar to a traveling salesman problem (<ACRONYM
 107 CLASS="ACRONYM"
 108 >TSP</ACRONYM
 109 >).
 110     Possible query plans are encoded as integer strings. Each string
 111     represents the join order from one relation of the query to the next.
 112     E. g., the query tree
 113 </P><PRE
 114 CLASS="LITERALLAYOUT"
 115 >   /\
 116   /\ 2
 117  /\ 3
 118 4  1</PRE
 119 ><P>
 120     is encoded by the integer string '4-1-3-2',
 121     which means, first join relation '4' and '1', then '3', and
 122     then '2', where 1, 2, 3, 4 are relation IDs within the
 123     <SPAN
 124 CLASS="PRODUCTNAME"
 125 >PostgreSQL</SPAN
 126 > optimizer.
 127    </P
 128 ><P
 129 >    Parts of the <ACRONYM
 130 CLASS="ACRONYM"
 131 >GEQO</ACRONYM
 132 > module are adapted from D. Whitley's Genitor
 133     algorithm.
 134    </P
 135 ><P
 136 >    Specific characteristics of the <ACRONYM
 137 CLASS="ACRONYM"
 138 >GEQO</ACRONYM
 139 >
 140     implementation in <SPAN
 141 CLASS="PRODUCTNAME"
 142 >PostgreSQL</SPAN
 143 >
 144     are:
 145
 146     <P
 147 ></P
 148 ></P><UL
 149 COMPACT="COMPACT"
 150 ><LI
 151 STYLE="list-style-type: disc"
 152 ><P
 153 >       Usage of a <I
 154 CLASS="FIRSTTERM"
 155 >steady state</I
 156 > <ACRONYM
 157 CLASS="ACRONYM"
 158 >GA</ACRONYM
 159 > (replacement of the least fit
 160        individuals in a population, not whole-generational replacement)
 161        allows fast convergence towards improved query plans. This is
 162        essential for query handling with reasonable time;
 163       </P
 164 ></LI
 165 ><LI
 166 STYLE="list-style-type: disc"
 167 ><P
 168 >       Usage of <I
 169 CLASS="FIRSTTERM"
 170 >edge recombination crossover</I
 171 >
 172        which is especially suited to keep edge losses low for the
 173        solution of the <ACRONYM
 174 CLASS="ACRONYM"
 175 >TSP</ACRONYM
 176 > by means of a
 177        <ACRONYM
 178 CLASS="ACRONYM"
 179 >GA</ACRONYM
 180 >;
 181       </P
 182 ></LI
 183 ><LI
 184 STYLE="list-style-type: disc"
 185 ><P
 186 >       Mutation as genetic operator is deprecated so that no repair
 187        mechanisms are needed to generate legal <ACRONYM
 188 CLASS="ACRONYM"
 189 >TSP</ACRONYM
 190 > tours.
 191       </P
 192 ></LI
 193 ></UL
 194 ><P>
 195    </P
 196 ><P
 197 >    The <ACRONYM
 198 CLASS="ACRONYM"
 199 >GEQO</ACRONYM
 200 > module allows
 201     the <SPAN
 202 CLASS="PRODUCTNAME"
 203 >PostgreSQL</SPAN
 204 > query optimizer to
 205     support large join queries effectively through
 206     non-exhaustive search.
 207    </P
 208 ><DIV
 209 CLASS="SECT2"
 210 ><H2
 211 CLASS="SECT2"
 212 ><A
 213 NAME="GEQO-FUTURE"
 214 >48.3.1. Future Implementation Tasks for
 215     <SPAN
 216 CLASS="PRODUCTNAME"
 217 >PostgreSQL</SPAN
 218 > <ACRONYM
 219 CLASS="ACRONYM"
 220 >GEQO</ACRONYM
 221 ></A
 222 ></H2
 223 ><P
 224 >      Work is still needed to improve the genetic algorithm parameter
 225       settings.
 226       In file <TT
 227 CLASS="FILENAME"
 228 >backend/optimizer/geqo/geqo_params.c</TT
 229 >, routines
 230       <CODE
 231 CLASS="FUNCTION"
 232 >gimme_pool_size</CODE
 233 > and <CODE
 234 CLASS="FUNCTION"
 235 >gimme_number_generations</CODE
 236 >,
 237       we have to find a compromise for the parameter settings
 238       to satisfy two competing demands:
 239       <P
 240 ></P
 241 ></P><UL
 242 COMPACT="COMPACT"
 243 ><LI
 244 ><P
 245 >        Optimality of the query plan
 246         </P
 247 ></LI
 248 ><LI
 249 ><P
 250 >        Computing time
 251         </P
 252 ></LI
 253 ></UL
 254 ><P>
 255      </P
 256 ></DIV
 257 ></DIV
 258 ><DIV
 259 CLASS="NAVFOOTER"
 260 ><HR
 261 ALIGN="LEFT"
 262 WIDTH="100%"><TABLE
 263 SUMMARY="Footer navigation table"
 264 WIDTH="100%"
 265 BORDER="0"
 266 CELLPADDING="0"
 267 CELLSPACING="0"
 268 ><TR
 269 ><TD
 270 WIDTH="33%"
 271 ALIGN="left"
 272 VALIGN="top"
 273 ><A
 274 HREF="geqo-intro2.html"
 275 ACCESSKEY="P"
 276 >Prev</A
 277 ></TD
 278 ><TD
 279 WIDTH="34%"
 280 ALIGN="center"
 281 VALIGN="top"
 282 ><A
 283 HREF="index.html"
 284 ACCESSKEY="H"
 285 >Home</A
 286 ></TD
 287 ><TD
 288 WIDTH="33%"
 289 ALIGN="right"
 290 VALIGN="top"
 291 ><A
 292 HREF="geqo-biblio.html"
 293 ACCESSKEY="N"
 294 >Next</A
 295 ></TD
 296 ></TR
 297 ><TR
 298 ><TD
 299 WIDTH="33%"
 300 ALIGN="left"
 301 VALIGN="top"
 302 >Genetic Algorithms</TD
 303 ><TD
 304 WIDTH="34%"
 305 ALIGN="center"
 306 VALIGN="top"
 307 ><A
 308 HREF="geqo.html"
 309 ACCESSKEY="U"
 310 >Up</A
 311 ></TD
 312 ><TD
 313 WIDTH="33%"
 314 ALIGN="right"
 315 VALIGN="top"
 316 >Further Readings</TD
 317 ></TR
 318 ></TABLE
 319 ></DIV
 320 ></BODY
 321 ></HTML
 322 >