X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id AA28CD8DAA for ; Tue, 13 Sep 2005 20:16:37 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 06452-06 for ; Tue, 13 Sep 2005 23:16:27 +0000 (GMT) Received: from mailbox.samurai.com (mailbox.samurai.com [205.207.28.82]) by svr1.postgresql.org (Postfix) with ESMTP id 014EBD8AC5 for ; Tue, 13 Sep 2005 20:16:28 -0300 (ADT) Received: from localhost (mailbox.samurai.com [205.207.28.82]) by mailbox.samurai.com (Postfix) with ESMTP id B350D2396AB; Tue, 13 Sep 2005 19:16:30 -0400 (EDT) Received: from mailbox.samurai.com ([205.207.28.82]) by localhost (mailbox.samurai.com [205.207.28.82]) (amavisd-new, port 10024) with LMTP id 92674-01-9; Tue, 13 Sep 2005 19:16:27 -0400 (EDT) Received: from [192.168.1.101] (d226-86-55.home.cgocable.net [24.226.86.55]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mailbox.samurai.com (Postfix) with ESMTP id 2F9A923968A; Tue, 13 Sep 2005 19:16:27 -0400 (EDT) Message-ID: <43275DCA.7040006@samurai.com> Date: Tue, 13 Sep 2005 19:16:26 -0400 From: Neil Conway User-Agent: Mozilla Thunderbird 1.0.2 (Macintosh/20050317) X-Accept-Language: en-us, en MIME-Version: 1.0 To: pryscila.lista@gmail.com Cc: pgsql-performance@postgresql.org Subject: Re: About method of PostgreSQL's Optimizer References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at mailbox.samurai.com X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0 required=5 tests=[none] X-Spam-Level: X-Archive-Number: 200509/177 X-Sequence-Number: 14485 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