Re: [PERFORM] About method of PostgreSQL's Optimizer
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
On 9/13/05, Tom Lane <[EMAIL PROTECTED]> wrote:
Neil Conway <[EMAIL PROTECTED]> 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 nowwas involved then. The right place to look would be in the Berkeleyproject's publications:
http://db.cs.berkeley.edu//papers/I agree with Neil's point that it's a spiritual descendant of System Rand there's plenty of material about that in the general databaseliterature.regards,
tom lane
Re: [PERFORM] About method of PostgreSQL's Optimizer
Neil Conway <[EMAIL PROTECTED]> 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 ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [PERFORM] About method of PostgreSQL's Optimizer
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 ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [PERFORM] About method of PostgreSQL's Optimizer
Thank's guys! I'll send to pgsql-hackers... []'s PryscilaOn 9/13/05, Neil Conway <[EMAIL PROTECTED]> wrote: 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. Forqueries with many joins (when the cost of an exhaustive search would beprohibitive), "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 ismainly 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, althoughthere have been a few presentations on it:http://neilc.treehou.se/optimizer.pdf http://conferences.oreillynet.com/presentations/os2003/lane_tom.pdf-Neil
Re: [PERFORM] About method of PostgreSQL's Optimizer
I know you almost had read this, but I think it is a good paper to start with... http://lca2005.linux.org.au/Papers/Neil%20Conway/Inside%20the%20PostgreSQL%20Query%20Optimizer/pg_query_optimizer.pdf Anyway, do you know where could I get more info and theory about database optimizer plan? (in general) I like that topic, thanks a lot man! - 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.
Re: [PERFORM] About method of PostgreSQL's Optimizer
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/ ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [PERFORM] 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 ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
[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.
