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/
