|
Server : Apache/2.2.2 (Fedora) System : Linux App1.pathumtani.go.th 2.6.20-1.2320.fc5smp #1 SMP Tue Jun 12 19:40:16 EDT 2007 i686 User : apache ( 48) PHP Version : 5.2.9 Disable Function : NONE Directory : /proc/self/root/usr/share/doc/postgresql-8.1.9/html/ |
Upload File : |
<!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.1.9 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-04-20T04:40:08"></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.1.9 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="indexam.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 47. Genetic Query Optimizer</H1
><DIV
CLASS="TOC"
><DL
><DT
><B
>Table of Contents</B
></DT
><DT
>47.1. <A
HREF="geqo.html#GEQO-INTRO"
>Query Handling as a Complex Optimization Problem</A
></DT
><DT
>47.2. <A
HREF="geqo-intro2.html"
>Genetic Algorithms</A
></DT
><DT
>47.3. <A
HREF="geqo-pg-intro.html"
>Genetic Query Optimization (<ACRONYM
CLASS="ACRONYM"
>GEQO</ACRONYM
>) in PostgreSQL</A
></DT
><DT
>47.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"
>47.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
>