<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <HTML ><HEAD ><TITLE >Genetic Query Optimizer</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="Internals" HREF="internals.html"><LINK REL="PREVIOUS" TITLE="Writing A Procedural Language Handler" HREF="plhandler.html"><LINK REL="NEXT" TITLE="Genetic Algorithms" HREF="geqo-intro2.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="CHAPTER" ><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="plhandler.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="plhandler.html" >Fast Backward</A ></TD ><TD WIDTH="60%" ALIGN="center" VALIGN="bottom" ></TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="indexcost.html" >Fast Forward</A ></TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="geqo-intro2.html" ACCESSKEY="N" >Next</A ></TD ></TR ></TABLE ><HR ALIGN="LEFT" WIDTH="100%"></DIV ><DIV CLASS="CHAPTER" ><H1 ><A NAME="GEQO" ></A >Chapter 46. Genetic Query Optimizer</H1 ><DIV CLASS="TOC" ><DL ><DT ><B >Table of Contents</B ></DT ><DT >46.1. <A HREF="geqo.html#GEQO-INTRO" >Query Handling as a Complex Optimization Problem</A ></DT ><DT >46.2. <A HREF="geqo-intro2.html" >Genetic Algorithms</A ></DT ><DT >46.3. <A HREF="geqo-pg-intro.html" >Genetic Query Optimization (<ACRONYM CLASS="ACRONYM" >GEQO</ACRONYM >) in PostgreSQL</A ></DT ><DT >46.4. <A HREF="geqo-biblio.html" >Further Reading</A ></DT ></DL ></DIV ><P > </P><DIV CLASS="NOTE" ><BLOCKQUOTE CLASS="NOTE" ><P ><B >Author: </B > Written by Martin Utesch (<CODE CLASS="EMAIL" ><<A HREF="mailto:utesch@aut.tu-freiberg.de" >utesch@aut.tu-freiberg.de</A >></CODE >) for the Institute of Automatic Control at the University of Mining and Technology in Freiberg, Germany. </P ></BLOCKQUOTE ></DIV ><P> </P ><DIV CLASS="SECT1" ><H1 CLASS="SECT1" ><A NAME="GEQO-INTRO" >46.1. Query Handling as a Complex Optimization Problem</A ></H1 ><P > Among all relational operators the most difficult one to process and optimize is the <I CLASS="FIRSTTERM" >join</I >. The number of alternative plans to answer a query grows exponentially with the number of joins included in it. Further optimization effort is caused by the support of a variety of <I CLASS="FIRSTTERM" >join methods</I > (e.g., nested loop, hash join, merge join in <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN >) to process individual joins and a diversity of <I CLASS="FIRSTTERM" >indexes</I > (e.g., R-tree, B-tree, hash in <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN >) as access paths for relations. </P ><P > The current <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > optimizer implementation performs a <I CLASS="FIRSTTERM" >near-exhaustive search</I > over the space of alternative strategies. This algorithm, first introduced in the <SPAN CLASS="QUOTE" >"System R"</SPAN > database, produces a near-optimal join order, but can take an enormous amount of time and memory space when the number of joins in the query grows large. This makes the ordinary <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > query optimizer inappropriate for queries that join a large number of tables. </P ><P > The Institute of Automatic Control at the University of Mining and Technology, in Freiberg, Germany, encountered the described problems as its folks wanted to take the <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN > DBMS as the backend for a decision support knowledge based system for the maintenance of an electrical power grid. The DBMS needed to handle large join queries for the inference machine of the knowledge based system. </P ><P > Performance difficulties in exploring the space of possible query plans created the demand for a new optimization technique to be developed. </P ><P > In the following we describe the implementation of a <I CLASS="FIRSTTERM" >Genetic Algorithm</I > to solve the join ordering problem in a manner that is efficient for queries involving large numbers of joins. </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="plhandler.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-intro2.html" ACCESSKEY="N" >Next</A ></TD ></TR ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" >Writing A Procedural Language Handler</TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="internals.html" ACCESSKEY="U" >Up</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" >Genetic Algorithms</TD ></TR ></TABLE ></DIV ></BODY ></HTML >