DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:references;
	b=nVkTPe6uS7TgyhVEMPw5fe6H7397Bxr7KhALPjNcmEOy3YAf+N4GK1IwdiqJrobTst3T6wKIDiTq4fWpZimpJQWJtE2+9SjouesdVPbyJhEgerBAz++9gp0oJ2ucrz1npj0IfseE3/PlnLTf1SC8D6M5qERgY38N8kNAFAY6nQU=
Message-ID: <36e6829205091320085993ceba@mail.gmail.com>
Date: Tue, 13 Sep 2005 23:08:31 -0400
From: "Jonah H. Harris" <jonah.harris@gmail.com>
Reply-To: jonah.harris@gmail.com
To: pryscila.lista@gmail.com
Subject: Re: About method of PostgreSQL's Optimizer
Cc: pgsql-hackers@postgresql.org
In-Reply-To: <cf0868bd05091317412310c490@mail.gmail.com>
Mime-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_5829_7451872.1126667311980"
References: <cf0868bd05091315503024742@mail.gmail.com>
	<cf0868bd05091317412310c490@mail.gmail.com>

------=_Part_5829_7451872.1126667311980
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Pryscila,

While I haven't been too involved in the open source PostgreSQL optimizer, =
I=20
have done some work on it and optimizers in other database systems.

Based on my work, it is my opinion that PostgreSQL, as-well-as other=20
databases which use a cost-based optimizer, prefer a breadth-first algorith=
m=20
because one cannot determine the "real" cost of each node at run-time=20
without systematically examining all possibilities through calculation. Thi=
s=20
is the opposite of a rule-based optimizer which defines heuristics which ca=
n=20
be evaulated by a best-first algorithm such as A*.

In a cost-based optimizer, the system must calculate the "cost" of each pat=
h=20
based on data that changes during run-time including indexing, cardinality,=
=20
tuple size, available memory, CPU usage, disk access times, etc. To a=20
cost-based optimizer, every query is unique and therefore cannot follow a=
=20
weighted path in the same fashion. I can certainly see A* being used in a=
=20
rule-based optimizer but not in a real-time cost-based optimizer.

Perhaps Tom, Bruce, et al have more specifics on PostgreSQL's=20
implementation.

-Jonah


On 9/13/05, Pryscila B Guttoski <pryscila.lista@gmail.com> wrote:
>=20
> Hello all!
>=20
> On my master course, I'm studying the PostgreSQL's optimizer.
> I don't know if anyone in this list have been participated from the=20
> PostgreSQL's Optimizer development, but maybe someone can help me on this=
=20
> question.
> PostgreSQL generates all possible plans of executing the query (using an=
=20
> almost exhaustive search), then gives a cost to each plan and finally the=
=20
> cheapest one is selected for execution.
> There are other methods for query optimization, one of them is based on=
=20
> plan transformations (for example, using A-Star algorithm) instead of pla=
n=20
> constructions used by PostgreSQL.=20
> Does anyone know why this method was choosen? Are there any papers or=20
> researches about it?
>=20
> Thank's a lot,
> Pryscila.
> =20


--=20
Respectfully,

Jonah H. Harris, Database Internals Architect
EnterpriseDB Corporation
http://www.enterprisedb.com/

------=_Part_5829_7451872.1126667311980
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Pryscila,<br>
<br>
While I haven't been too involved in the open source PostgreSQL
optimizer, I have done some work on it and optimizers in other database
systems.<br>
<br>
Based on my work, it is my opinion that PostgreSQL, as-well-as other
databases which use a cost-based optimizer, prefer a breadth-first
algorithm because one cannot determine the &quot;real&quot; cost of each no=
de at
run-time without systematically examining all possibilities through
calculation.&nbsp; This is the opposite of a rule-based optimizer which
defines heuristics which can be evaulated by a best-first algorithm
such as A*.<br>
<br>
In a cost-based optimizer, the system must calculate the &quot;cost&quot; o=
f each
path based on data that changes during run-time including indexing,
cardinality, tuple size, available memory, CPU usage, disk access
times, etc.&nbsp; To a cost-based optimizer, every query is unique and
therefore cannot follow a weighted path in the same fashion.&nbsp; I
can certainly see A* being used in a rule-based optimizer but not in a
real-time cost-based optimizer.<br>
<br>
Perhaps Tom, Bruce, et al have more specifics on PostgreSQL's implementatio=
n.<br>
<br>
-Jonah<br>
<br>
<br>
<br><div><span class=3D"gmail_quote">On 9/13/05, <b class=3D"gmail_senderna=
me">Pryscila B Guttoski</b> &lt;<a href=3D"mailto:pryscila.lista@gmail.com"=
>pryscila.lista@gmail.com</a>&gt; wrote:</span><blockquote class=3D"gmail_q=
uote" style=3D"border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0=
pt 0.8ex; padding-left: 1ex;">
Hello all!<br>
<br>
On my master course, I'm studying the PostgreSQL's optimizer.<br>
I don't know if anyone in this list have been participated from the
PostgreSQL's Optimizer development, but maybe someone can help me on
this question.<br>
PostgreSQL generates all possible plans of executing the query (using
an almost exhaustive search), then gives a cost to each plan and
finally the cheapest one is selected for execution.<br>
There are other methods for query optimization, one of them is based on
plan transformations (for example, using A-Star algorithm) instead of
plan constructions used by PostgreSQL. <br>
Does anyone know why this method was choosen? Are there any papers or resea=
rches about it?<br>
<br>
Thank's a lot,<br><span class=3D"sg"><span>
Pryscila.<br>


</span>

</span></blockquote></div><br><br clear=3D"all"><br>-- <br>Respectfully,<br=
><br>Jonah H. Harris, Database Internals Architect<br>EnterpriseDB Corporat=
ion<br><a href=3D"http://www.enterprisedb.com/">http://www.enterprisedb.com=
/
</a><br>

------=_Part_5829_7451872.1126667311980--