X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id C8EAAD8CD8 for ; Thu, 15 Sep 2005 02:29:23 -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 01880-04 for ; Thu, 15 Sep 2005 05:29:19 +0000 (GMT) Received: by svr1.postgresql.org (Postfix, from userid 1001) id 2A467D9104; Thu, 15 Sep 2005 03:38:53 -0300 (ADT) Received: from rproxy.gmail.com (rproxy.gmail.com [64.233.170.202]) by svr1.postgresql.org (Postfix) with ESMTP id 60652D816D for ; Thu, 15 Sep 2005 02:08:47 -0300 (ADT) Received: by rproxy.gmail.com with SMTP id 40so32616rnz for ; Wed, 14 Sep 2005 22:08:47 -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:cc:in-reply-to:mime-version:content-type:references; b=gw10thneX43j+nsj3w9dz8yuIXhEIhKlEz9NdoCW0izgsawj0O6E//KCkJn9prsc1I5I4LL3ghlM4dTkkTWaQFCP6a1ErVK+QKleQit5sSDmFOxKlrnEDOUKIJdpCnX4qYZ5s8HwSSR08Qf7g0PhsbtXIMTisdjODrpQnC2SAlU= Received: by 10.11.117.77 with SMTP id p77mr617cwc; Wed, 14 Sep 2005 22:08:47 -0700 (PDT) Received: by 10.11.119.38 with HTTP; Wed, 14 Sep 2005 22:08:47 -0700 (PDT) Message-ID: <36e682920509142208211344d5@mail.gmail.com> Date: Thu, 15 Sep 2005 01:08:47 -0400 From: "Jonah H. Harris" Reply-To: jonah.harris@gmail.com To: Tom Lane Subject: Re: About method of PostgreSQL's Optimizer Cc: pryscila.lista@gmail.com, pgsql-hackers@postgresql.org In-Reply-To: <36e6829205091421394fbb062a@mail.gmail.com> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_7375_13909730.1126760927459" References: <36e6829205091320085993ceba@mail.gmail.com> <36e6829205091409361035d32a@mail.gmail.com> <6127.1126720486@sss.pgh.pa.us> <36e6829205091421394fbb062a@mail.gmail.com> X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.309 required=5 tests=[AWL=0.228, HTML_30_40=0.056, HTML_MESSAGE=0.001, RCVD_BY_IP=0.024] X-Spam-Level: X-Archive-Number: 200509/683 X-Sequence-Number: 73080 ------=_Part_7375_13909730.1126760927459 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Pryscila, For research reference, you may want to look at the work done on the=20 Columbia Query Optimization Framework. As I recall, I think it (or its=20 predecessors) had both cost and rule-based optimization. If you need the=20 code to it, I can dig it up on one of my old systems. Albeit dated, another good reference for optimizer implementation is the=20 cascades query optimization framework. On 9/15/05, Jonah H. Harris wrote: >=20 > Tom, >=20 > I agree. There have been several occasions where GEQO has performed poorl= y=20 > for me. I'll search the archives for the past discussions. >=20 > sorry for sending this to you twice Tom... forgot to hit reply all :( >=20 > On 9/14/05, Tom Lane wrote: > >=20 > > "Jonah H. Harris" writes: > > > As for using both in the same optimizer, I could only see an algorith= m=20 > > such > > > as a customized-A* being used to planning *some* large queries. The= =20 > > reason I > > > say this is because the cost calculation, which would still need to b= e=20 > >=20 > > > breadth-first, could calculate and cache the cost of most nodes=20 > > thereby > > > allowing you to possibly perform transformations at the tail of=20 > > calculation. > >=20 > > We do already have two different plan search algorithms: the strict=20 > > bottom-up dynamic programming approach (System R style) and the GEQO > > optimizer, which we switch to when there are too many joins needed to > > allow exhaustive search. The GEQO code still depends on the normal > > plan cost estimation code, but it doesn't consider every possible plan.= =20 > >=20 > > I've never been very happy with the GEQO code: the random component of > > the algorithm means you get unpredictable (and sometimes awful) plans, > > and the particular variant that we are using is really designed to solv= e=20 > >=20 > > traveling-salesman problems. It's at best a poor fit to the join > > planning problem. > >=20 > > So it seems interesting to me to think about replacing GEQO with a > > rule-based optimizer for large join search spaces. > >=20 > > There are previous discussions about this in the archives, I believe. > >=20 > > regards, tom lane > >=20 >=20 >=20 >=20 > --=20 > Respectfully, >=20 > Jonah H. Harris, Database Internals Architect > EnterpriseDB Corporation > http://www.enterprisedb.com/=20 >=20 --=20 Respectfully, Jonah H. Harris, Database Internals Architect EnterpriseDB Corporation http://www.enterprisedb.com/ ------=_Part_7375_13909730.1126760927459 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Pryscila,

For research reference, you may want to look at the work done on the Columbia Query Optimization Framework.  As I recall, I think it (or its predecessors) had both cost and rule-based optimization.  If you need the code to it, I can dig it up on one of my old systems.

Albeit dated, another good reference for optimizer implementation is the ca= scades query optimization framework.


On 9/15/05, Jonah H. Harris <jonah= .harris@gmail.com> wrote:
Tom,

I agree.  There have been several occasions where GEQO has performed poorly for me.  I'll search the archives for the past discussions.

 sorry for sending this to you twice Tom... forgot to hit reply all :(
On 9/14/05, Tom Lane < tgl@sss.pgh.pa.us > wrote:
"Jonah H. H= arris" < jonah.harris@gmail.com > writes:
> As for using both in the same optimizer, I could o= nly see an algorithm such
> as a customized-A* being used to planning= *some* large queries. The reason I
> say this is because the cost ca= lculation, which would still need to be
> breadth-first, could calculate and cache the cost of most nodes th= ereby
> allowing you to possibly perform transformations at the tail = of calculation.

We do already have two different plan search algorit= hms: the strict
bottom-up dynamic programming approach (System R style) and the GEQOoptimizer, which we switch to when there are too many joins needed to
a= llow exhaustive search.  The GEQO code still depends on the norma= l
plan cost estimation code, but it doesn't consider every possible plan.

I've never been very happy with the GEQO code: the random component= of
the algorithm means you get unpredictable (and sometimes awful) plan= s,
and the particular variant that we are using is really designed to so= lve
traveling-salesman problems.  It's at best a poor fit to the = join
planning problem.

So it seems interesting to me to think abo= ut replacing GEQO with a
rule-based optimizer for large join search spac= es.

There are previous discussions about this in the archives, I believe.
           &nb= sp;            = regards, tom lane



--
Respectfully,

J= onah H. Harris, Database Internals Architect
EnterpriseDB Corporation http://www.enterprisedb.com/



--
Respectful= ly,

Jonah H. Harris, Database Internals Architect
EnterpriseDB Co= rporation
http://www.enterprise= db.com/
------=_Part_7375_13909730.1126760927459--