Re: About method of PostgreSQL's Optimizer

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(dot)lista(at)gmail(dot)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/