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:content-transfer-encoding:content-disposition:references;
	b=VSUuXya/hIb5dywlDzC9uJajAHXwfyHh4Ul+a+poSxJACkDYkub8acbzG2YIMkJAYPcay6JPj6EKTtJaHllxNXY9Ukox1pz2hiCTRrcK+xwd/QJ9QTEm6QH2hU6qFhaw2RUMG4REVHMzP6HRcFtoKEo75y3Ox268cI1O/ybCQH0=
Message-ID: <cf0868bd050914085233eae603@mail.gmail.com>
Date: Wed, 14 Sep 2005 12:52:50 -0300
From: Pryscila B Guttoski <pryscila.lista@gmail.com>
Reply-To: pryscila.lista@gmail.com
To: jonah.harris@gmail.com
Subject: Re: About method of PostgreSQL's Optimizer
Cc: pgsql-hackers@postgresql.org
In-Reply-To: <36e6829205091320085993ceba@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
References: <cf0868bd05091315503024742@mail.gmail.com>
	<cf0868bd05091317412310c490@mail.gmail.com>
	<36e6829205091320085993ceba@mail.gmail.com>

Hi Jonah,

Thank's for your email, I really appreciate your opinions.

Is it interesting to use both techniques? For example:
Given a query, an optimizer:
1. Generates one of the possible execution plans.
2. Does transformations on the original plan, based on rules and
heuristics, resulting in new alternative plans.
3. Evaluates the cost of generated plans by using statistics.
4. Keeps plans that have lower cost than the original plan
5. Repeat 2-4 over the new alternative plans.
What do you think about it? Are there any restrictions that I haven't seen?

About other method...
Have you heard about using PDDL ("Planning Domain Definition
Language") for query optimization?

[]'s
Pryscila


On 9/14/05, Jonah H. Harris <jonah.harris@gmail.com> wrote:
> Pryscila,
> =20
>  While I haven't been too involved in the open source PostgreSQL optimize=
r,
> I have done some work on it and optimizers in other database systems.
> =20
>  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 algori=
thm
> because one cannot determine the "real" cost of each node at run-time
> without systematically examining all possibilities through calculation.=
=20
> This is the opposite of a rule-based optimizer which defines heuristics
> which can be evaulated by a best-first algorithm such as A*.
> =20
>  In a cost-based optimizer, the system must calculate the "cost" of each
> path based on data that changes during run-time including indexing,
> cardinality, tuple size, available memory, CPU usage, disk access times,
> etc.  To a cost-based optimizer, every query is unique and therefore cann=
ot
> follow a weighted path in the same fashion.  I can certainly see A* being
> used in a rule-based optimizer but not in a real-time cost-based optimize=
r.
> =20
>  Perhaps Tom, Bruce, et al have more specifics on PostgreSQL's
> implementation.
> =20
>  -Jonah
>=20
> =20
> =20
> =20
> On 9/13/05, Pryscila B Guttoski <pryscila.lista@gmail.com> wrote:
> > 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
> PostgreSQL's Optimizer development, but maybe someone can help me on this
> question.
> > PostgreSQL generates all possible plans of executing the query (using a=
n
> almost exhaustive search), then gives a cost to each plan and finally the
> cheapest one is selected for execution.
> > There are other methods for query optimization, one of them is based on
> plan transformations (for example, using A-Star algorithm) instead of pla=
n
> constructions used by PostgreSQL.=20
> > Does anyone know why this method was choosen? Are there any papers or
> researches about it?
> >=20
> > Thank's a lot,
> > Pryscila.
> >=20
>=20
>=20
>=20
> --=20
> Respectfully,
>=20
> Jonah H. Harris, Database Internals Architect
> EnterpriseDB Corporation
> http://www.enterprisedb.com/=20
>