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 A0386D8D36 for ; Tue, 13 Sep 2005 21:40:49 -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 28826-03 for ; Wed, 14 Sep 2005 00:40:44 +0000 (GMT) Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.193]) by svr1.postgresql.org (Postfix) with ESMTP id 4E15DD8377 for ; Tue, 13 Sep 2005 21:40:45 -0300 (ADT) Received: by xproxy.gmail.com with SMTP id i27so24021wxd for ; Tue, 13 Sep 2005 17:40:45 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:in-reply-to:mime-version:content-type:references; b=ETv7eoCpj13gWbN5SfSGoFRzae0sbc8vbbtY0XgyVO0nuGsWuV+HtxqXG1YwH7d+y9u62vQpEt0JIw6AYinIv8QhdggLJKcbQqpoEUuAT4JfPpDfbJe/bcIIFGV/gWJLk0ydBgwc9q/O3rt5ZgJHtYYCQIi2P9z/mn8XJ6bgGrs= Received: by 10.70.21.12 with SMTP id 12mr5830wxu; Tue, 13 Sep 2005 17:40:45 -0700 (PDT) Received: by 10.70.18.3 with HTTP; Tue, 13 Sep 2005 17:40:45 -0700 (PDT) Message-ID: Date: Tue, 13 Sep 2005 21:40:45 -0300 From: Pryscila B Guttoski Reply-To: pryscila.lista@gmail.com To: pgsql-performance@postgresql.org Subject: Re: About method of PostgreSQL's Optimizer In-Reply-To: <43275DCA.7040006@samurai.com> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_28539_30568457.1126658445096" References: <43275DCA.7040006@samurai.com> X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=1.262 required=5 tests=[AWL=0.733, HTML_20_30=0.504, HTML_MESSAGE=0.001, RCVD_BY_IP=0.024] X-Spam-Level: * X-Archive-Number: 200509/181 X-Sequence-Number: 14489 ------=_Part_28539_30568457.1126658445096 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Thank's guys! I'll send to pgsql-hackers... []'s Pryscila On 9/13/05, Neil Conway wrote: >=20 > 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=20 > this > > question. >=20 > pgsql-hackers might be more appropriate. >=20 > > PostgreSQL generates all possible plans of executing the query (using a= n > > almost exhaustive search), then gives a cost to each plan and finally= =20 > the > > cheapest one is selected for execution. > > There are other methods for query optimization, one of them is based on= =20 > plan > > transformations (for example, using A-Star algorithm) instead of plan > > constructions used by PostgreSQL. >=20 > 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. >=20 > > Does anyone know why this method was choosen? >=20 > 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. >=20 > > Are there any papers or researches about it? >=20 > 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: >=20 > http://neilc.treehou.se/optimizer.pdf > http://conferences.oreillynet.com/presentations/os2003/lane_tom.pdf >=20 > -Neil > ------=_Part_28539_30568457.1126658445096 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Thank's guys!
I'll send to pgsql-hackers...

[]'s
Pryscila

On 9/13/05, Neil Conway <ne= ilc@samurai.com> wrote:
Pryscila B Guttoski wrote:
> On my master course, I'm studying the Po= stgreSQL's optimizer.
> I don't know if anyone in this list have been= participated from the
> PostgreSQL's Optimizer development, but mayb= e someone can help me on this
> question.

pgsql-hackers might be more appropriate.

&= gt; PostgreSQL generates all possible plans of executing the query (using a= n
> almost exhaustive search), then gives a cost to each plan and fin= ally the
> cheapest one is selected for execution.
> There are other me= thods for query optimization, one of them is based on plan
> transfor= mations (for example, using A-Star algorithm) instead of plan
> const= ructions used by PostgreSQL.

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

> Does anyone know w= hy this method was choosen?

As far as I know, the main planner algor= ithm is fairly standard and is
mainly different from System R's canonica= l 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 motiva= tions for the design. I'm not aware
of any papers specifically on the PostgreSQL query optimizer, although<= br>there have been a few presentations on it:

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

-Neil

------=_Part_28539_30568457.1126658445096--