From: Jonah H. Harris <jonah.harris@gmail.com>
To: pryscila.lista@gmail.com
Cc: pgsql-hackers@postgresql.org
Subject: Re: About method of PostgreSQL's Optimizer
Date: Tue, 13 Sep 2005 23:08:31 -0400
Message-ID: <36e6829205091320085993ceba@mail.gmail.com> (raw)
In-Reply-To: <cf0868bd05091317412310c490@mail.gmail.com>
References: <cf0868bd05091315503024742@mail.gmail.com>
<cf0868bd05091317412310c490@mail.gmail.com>
Pryscila,
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.
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 "real" cost of each node at run-time
without systematically examining all possibilities through calculation. This
is the opposite of a rule-based optimizer which defines heuristics which can
be evaulated by a best-first algorithm such as A*.
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 cannot 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 optimizer.
Perhaps Tom, Bruce, et al have more specifics on PostgreSQL's
implementation.
-Jonah
On 9/13/05, Pryscila B Guttoski <pryscila.lista@gmail.com> wrote:
>
> Hello all!
>
> 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 an
> 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 plan
> constructions used by PostgreSQL.
> Does anyone know why this method was choosen? Are there any papers or
> researches about it?
>
> Thank's a lot,
> Pryscila.
>
--
Respectfully,
Jonah H. Harris, Database Internals Architect
EnterpriseDB Corporation
http://www.enterprisedb.com/
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: jonah.harris@gmail.com, pryscila.lista@gmail.com, pgsql-hackers@postgresql.org
Subject: Re: About method of PostgreSQL's Optimizer
In-Reply-To: <36e6829205091320085993ceba@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox