Re: About method of PostgreSQL's Optimizer

Pryscila B Guttoski wrote:
> 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.

pgsql-hackers might be more appropriate.

> 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.

Right, the main query planner uses a nearly-exhaustive search. For
queries with many joins (when the cost of an exhaustive search would be
prohibitive), "GEQO" is used, which uses a genetic algorithm to avoid an
exhaustive search of the solution space.

> Does anyone know why this method was choosen?

As far as I know, the main planner algorithm is fairly standard and is
mainly different from System R's canonical algorithm in the details,
like whether non-left-deep plans are pruned.

> Are there any papers or researches about it?

There are many papers on the System R algorithm and similar techniques,
which should explain the basic motivations for the design. I'm not aware
of any papers specifically on the PostgreSQL query optimizer, although
there have been a few presentations on it:

http://neilc.treehou.se/optimizer.pdf
http://conferences.oreillynet.com/presentations/os2003/lane_tom.pdf

-Neil