<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <HTML ><HEAD ><TITLE >Genetic Query Optimization (GEQO) in PostgreSQL</TITLE ><META NAME="GENERATOR" CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK REV="MADE" HREF="mailto:pgsql-docs@postgresql.org"><LINK REL="HOME" TITLE="PostgreSQL 8.0.11 Documentation" HREF="index.html"><LINK REL="UP" TITLE="Genetic Query Optimizer" HREF="geqo.html"><LINK REL="PREVIOUS" TITLE="Genetic Algorithms" HREF="geqo-intro2.html"><LINK REL="NEXT" TITLE="Further Reading" HREF="geqo-biblio.html"><LINK REL="STYLESHEET" TYPE="text/css" HREF="stylesheet.css"><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1"><META NAME="creation" CONTENT="2007-02-02T03:57:22"></HEAD ><BODY CLASS="SECT1" ><DIV CLASS="NAVHEADER" ><TABLE SUMMARY="Header navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TH COLSPAN="5" ALIGN="center" VALIGN="bottom" >PostgreSQL 8.0.11 Documentation</TH ></TR ><TR ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="geqo-intro2.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="geqo.html" >Fast Backward</A ></TD ><TD WIDTH="60%" ALIGN="center" VALIGN="bottom" >Chapter 46. Genetic Query Optimizer</TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="geqo.html" >Fast Forward</A ></TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="geqo-biblio.html" ACCESSKEY="N" >Next</A ></TD ></TR ></TABLE ><HR ALIGN="LEFT" WIDTH="100%"></DIV ><DIV CLASS="SECT1" ><H1 CLASS="SECT1" ><A NAME="GEQO-PG-INTRO" >46.3. Genetic Query Optimization (<ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM >) in PostgreSQL</A ></H1 ><P > The <ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM > module approaches the query optimization problem as though it were the well-known traveling salesman problem (<ACRONYM CLASS="ACRONYM" >TSP</ACRONYM >). Possible query plans are encoded as integer strings. Each string represents the join order from one relation of the query to the next. For example, the join tree </P><PRE CLASS="LITERALLAYOUT" > /\ /\ 2 /\ 3 4 1</PRE ><P> 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 relation IDs within the <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > optimizer. </P ><P > Parts of the <ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM > module are adapted from D. Whitley's Genitor algorithm. </P ><P > Specific characteristics of the <ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM > implementation in <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > are: <P ></P ></P><UL COMPACT="COMPACT" ><LI STYLE="list-style-type: disc" ><P > Usage of a <I CLASS="FIRSTTERM" >steady state</I > <ACRONYM CLASS="ACRONYM" >GA</ACRONYM > (replacement of the least fit individuals in a population, not whole-generational replacement) allows fast convergence towards improved query plans. This is essential for query handling with reasonable time; </P ></LI ><LI STYLE="list-style-type: disc" ><P > Usage of <I CLASS="FIRSTTERM" >edge recombination crossover</I > which is especially suited to keep edge losses low for the solution of the <ACRONYM CLASS="ACRONYM" >TSP</ACRONYM > by means of a <ACRONYM CLASS="ACRONYM" >GA</ACRONYM >; </P ></LI ><LI STYLE="list-style-type: disc" ><P > Mutation as genetic operator is deprecated so that no repair mechanisms are needed to generate legal <ACRONYM CLASS="ACRONYM" >TSP</ACRONYM > tours. </P ></LI ></UL ><P> </P ><P > The <ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM > module allows the <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > query optimizer to support large join queries effectively through non-exhaustive search. </P ><DIV CLASS="SECT2" ><H2 CLASS="SECT2" ><A NAME="GEQO-FUTURE" >46.3.1. Future Implementation Tasks for <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > <ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM ></A ></H2 ><P > Work is still needed to improve the genetic algorithm parameter settings. In file <TT CLASS="FILENAME" >src/backend/optimizer/geqo/geqo_main.c</TT >, routines <CODE CLASS="FUNCTION" >gimme_pool_size</CODE > and <CODE CLASS="FUNCTION" >gimme_number_generations</CODE >, we have to find a compromise for the parameter settings to satisfy two competing demands: <P ></P ></P><UL COMPACT="COMPACT" ><LI ><P > Optimality of the query plan </P ></LI ><LI ><P > Computing time </P ></LI ></UL ><P> </P ><P > At a more basic level, it is not clear that solving query optimization with a GA algorithm designed for TSP is appropriate. In the TSP case, the cost associated with any substring (partial tour) is independent of the rest of the tour, but this is certainly not true for query optimization. Thus it is questionable whether edge recombination crossover is the most effective mutation procedure. </P ></DIV ></DIV ><DIV CLASS="NAVFOOTER" ><HR ALIGN="LEFT" WIDTH="100%"><TABLE SUMMARY="Footer navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" ><A HREF="geqo-intro2.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="index.html" ACCESSKEY="H" >Home</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" ><A HREF="geqo-biblio.html" ACCESSKEY="N" >Next</A ></TD ></TR ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" >Genetic Algorithms</TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="geqo.html" ACCESSKEY="U" >Up</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" >Further Reading</TD ></TR ></TABLE ></DIV ></BODY ></HTML >