Thread: About method of PostgreSQL's Optimizer

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.

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

Pryscila B Guttoski 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?

You may want to pass this question over to pgsql-hackers.

Sincerely,

Joshua D. Drake


>
> Thank's a lot,
> Pryscila.


--
Your PostgreSQL solutions company - Command Prompt, Inc. 1.800.492.2240
PostgreSQL Replication, Consulting, Custom Programming, 24x7 support
Managed Services, Shared and Dedicated Hosting
Co-Authors: plPHP, plPerlNG - http://www.commandprompt.com/

----- Original Message -----

From: Pryscila B Guttoski

To: pgsql-performance@postgresql.org

Sent: Tuesday, September 13, 2005 4:50 PM

Subject: [PERFORM] About method of PostgreSQL's Optimizer

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.

Thank's guys!
I'll send to pgsql-hackers...

[]'s
Pryscila

Cristian Prieto wrote:
> Anyway, do you know where could I get more info and theory about
> database optimizer plan? (in general)

Personally I like this survey paper on query optimization:

     http://citeseer.csail.mit.edu/371707.html

The paper also cites a lot of other papers that cover specific
techniques in more detail.

-Neil

Neil Conway <neilc@samurai.com> writes:
> 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.

AFAIK the basic code goes back to Berkeley days.  Elein might possibly
remember something about it, but no one else that's on the project now
was involved then.  The right place to look would be in the Berkeley
project's publications:

http://db.cs.berkeley.edu//papers/

I agree with Neil's point that it's a spiritual descendant of System R
and there's plenty of material about that in the general database
literature.

            regards, tom lane

Hi guys,

I really appreciate your suggestions abouts papers, specially this one: http://citeseer.csail.mit.edu/371707.html

I found some answers on it, like this:

Q: Why the main query planner uses a nearly-exhaustive search?
A: (Page 20 - 4.2.2) ... up to about ten joins, dynamic programming is preferred over the randomized algorithms because it is faster and it guarantees finding the optimal plan. For larger queries, the situation is reversed, and despite the probabilistic nature of the randomized algorithms, their efficiency makes them the algorithms of choice.

Also in this paper, there is something about the A* algorithm very interesting for my research.

I have one more question, sorry for doing it on this list, but only here I had answers...
Does anybody hear anything about using PDDL ("Planning Domain Definition Language") for query optimization?

[]'s,
Pryscila