<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<HTML
><HEAD
><TITLE
>Planner/Optimizer</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
REV="MADE"
HREF="mailto:pgsql-docs@postgresql.org"><LINK
REL="HOME"
TITLE="PostgreSQL 7.4.1 Documentation"
HREF="index.html"><LINK
REL="UP"
TITLE="Overview of PostgreSQL Internals"
HREF="overview.html"><LINK
REL="PREVIOUS"
TITLE="The PostgreSQL Rule System"
HREF="rule-system.html"><LINK
REL="NEXT"
TITLE="Executor"
HREF="executor.html"><LINK
REL="STYLESHEET"
TYPE="text/css"
HREF="stylesheet.css"><META
NAME="creation"
CONTENT="2003-12-22T03:48:47"></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 7.4.1 Documentation</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
HREF="rule-system.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
HREF="overview.html"
>Fast Backward</A
></TD
><TD
WIDTH="60%"
ALIGN="center"
VALIGN="bottom"
>Chapter 42. Overview of PostgreSQL Internals</TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="top"
><A
HREF="overview.html"
>Fast Forward</A
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="top"
><A
HREF="executor.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="PLANNER-OPTIMIZER"
>42.5. Planner/Optimizer</A
></H1
><P
> The task of the <I
CLASS="FIRSTTERM"
>planner/optimizer</I
> is to
create an optimal execution plan. A given SQL query (and hence, a
query tree) can be actually executed in a wide variety of
different ways, each of which will produce the same set of
results. If it is computationally feasible, the query optimizer
will examine each of these possible execution plans, ultimately
selecting the execution plan that will run the fastest.
</P
><DIV
CLASS="NOTE"
><BLOCKQUOTE
CLASS="NOTE"
><P
><B
>Note: </B
> In some situations, examining each possible way in which a query
may be executed would take an excessive amount of time and memory
space. In particular, this occurs when executing queries
involving large numbers of join operations. In order to determine
a reasonable (not optimal) query plan in a reasonable amount of
time, <SPAN
CLASS="PRODUCTNAME"
>PostgreSQL</SPAN
> uses a <A
HREF="geqo.html"
><I
>Genetic Query Optimizer</I
></A
>.
</P
></BLOCKQUOTE
></DIV
><P
> After the cheapest path is determined, a <I
CLASS="FIRSTTERM"
>plan tree</I
>
is built to pass to the executor. This represents the desired
execution plan in sufficient detail for the executor to run it.
</P
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="AEN48624"
>42.5.1. Generating Possible Plans</A
></H2
><P
> The planner/optimizer decides which plans should be generated
based upon the types of indexes defined on the relations appearing in
a query. There is always the possibility of performing a
sequential scan on a relation, so a plan using only
sequential scans is always created. Assume an index is defined on a
relation (for example a B-tree index) and a query contains the
restriction
<TT
CLASS="LITERAL"
>relation.attribute OPR constant</TT
>. If
<TT
CLASS="LITERAL"
>relation.attribute</TT
> happens to match the key of the B-tree
index and <TT
CLASS="LITERAL"
>OPR</TT
> is one of the operators listed in
the index's <I
CLASS="FIRSTTERM"
>operator class</I
>, another plan is created using
the B-tree index to scan the relation. If there are further indexes
present and the restrictions in the query happen to match a key of an
index further plans will be considered.
</P
><P
> After all feasible plans have been found for scanning single relations,
plans for joining relations are created. The planner/optimizer
preferentially considers joins between any two relations for which there
exist a corresponding join clause in the <TT
CLASS="LITERAL"
>WHERE</TT
> qualification (i.e. for
which a restriction like <TT
CLASS="LITERAL"
>where rel1.attr1=rel2.attr2</TT
>
exists). Join pairs with no join clause are considered only when there
is no other choice, that is, a particular relation has no available
join clauses to any other relation. All possible plans are generated for
every join pair considered
by the planner/optimizer. The three possible join strategies are:
<P
></P
></P><UL
><LI
><P
> <I
CLASS="FIRSTTERM"
>nested loop join</I
>: The right relation is scanned
once for every row found in the left relation. This strategy
is easy to implement but can be very time consuming. (However,
if the right relation can be scanned with an index scan, this can
be a good strategy. It is possible to use values from the current
row of the left relation as keys for the index scan of the right.)
</P
></LI
><LI
><P
> <I
CLASS="FIRSTTERM"
>merge sort join</I
>: Each relation is sorted on the join
attributes before the join starts. Then the two relations are
merged together taking into account that both relations are
ordered on the join attributes. This kind of join is more
attractive because each relation has to be scanned only once.
</P
></LI
><LI
><P
> <I
CLASS="FIRSTTERM"
>hash join</I
>: the right relation is first scanned
and loaded into a hash table, using its join attributes as hash keys.
Next the left relation is scanned and the
appropriate values of every row found are used as hash keys to
locate the matching rows in the table.
</P
></LI
></UL
><P>
</P
><P
> The finished plan tree consists of sequential or index scans of
the base relations, plus nested-loop, merge, or hash join nodes as
needed, plus any auxiliary steps needed, such as sort nodes or
aggregate-function calculation nodes. Most of these plan node
types have the additional ability to do <I
CLASS="FIRSTTERM"
>selection</I
>
(discarding rows that do not meet a specified boolean condition)
and <I
CLASS="FIRSTTERM"
>projection</I
> (computation of a derived column set
based on given column values, that is, evaluation of scalar
expressions where needed). One of the responsibilities of the
planner is to attach selection conditions from the
<TT
CLASS="LITERAL"
>WHERE</TT
> clause and computation of required
output expressions to the most appropriate nodes of the plan
tree.
</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="rule-system.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="executor.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>The <SPAN
CLASS="PRODUCTNAME"
>PostgreSQL</SPAN
> Rule System</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="overview.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Executor</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
