From: Pryscila B Guttoski <pryscila.lista@gmail.com>
To: jonah.harris@gmail.com
Cc: pgsql-hackers@postgresql.org
Subject: Re: About method of PostgreSQL's Optimizer
Date: Wed, 14 Sep 2005 12:52:50 -0300
Message-ID: <cf0868bd050914085233eae603@mail.gmail.com> (raw)
In-Reply-To: <36e6829205091320085993ceba@mail.gmail.com>
References: <cf0868bd05091315503024742@mail.gmail.com>
<cf0868bd05091317412310c490@mail.gmail.com>
<36e6829205091320085993ceba@mail.gmail.com>
Hi Jonah,
Thank's for your email, I really appreciate your opinions.
Is it interesting to use both techniques? For example:
Given a query, an optimizer:
1. Generates one of the possible execution plans.
2. Does transformations on the original plan, based on rules and
heuristics, resulting in new alternative plans.
3. Evaluates the cost of generated plans by using statistics.
4. Keeps plans that have lower cost than the original plan
5. Repeat 2-4 over the new alternative plans.
What do you think about it? Are there any restrictions that I haven't seen?
About other method...
Have you heard about using PDDL ("Planning Domain Definition
Language") for query optimization?
[]'s
Pryscila
On 9/14/05, Jonah H. Harris <jonah.harris@gmail.com> wrote:
> Pryscila,
>
> While I haven't been too involved in the open source PostgreSQL optimizer,
> I have done some work on it and optimizers in other database systems.
>
> Based on my work, it is my opinion that PostgreSQL, as-well-as other
> databases which use a cost-based optimizer, prefer a breadth-first algorithm
> because one cannot determine the "real" cost of each node at run-time
> without systematically examining all possibilities through calculation.
> This is the opposite of a rule-based optimizer which defines heuristics
> which can be evaulated by a best-first algorithm such as A*.
>
> In a cost-based optimizer, the system must calculate the "cost" of each
> path based on data that changes during run-time including indexing,
> cardinality, tuple size, available memory, CPU usage, disk access times,
> etc. To a cost-based optimizer, every query is unique and therefore cannot
> follow a weighted path in the same fashion. I can certainly see A* being
> used in a rule-based optimizer but not in a real-time cost-based optimizer.
>
> Perhaps Tom, Bruce, et al have more specifics on PostgreSQL's
> implementation.
>
> -Jonah
>
>
>
>
> On 9/13/05, Pryscila B Guttoski <pryscila.lista@gmail.com> 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?
> >
> > Thank's a lot,
> > Pryscila.
> >
>
>
>
> --
> Respectfully,
>
> Jonah H. Harris, Database Internals Architect
> EnterpriseDB Corporation
> http://www.enterprisedb.com/
>
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: pryscila.lista@gmail.com, jonah.harris@gmail.com, pgsql-hackers@postgresql.org
Subject: Re: About method of PostgreSQL's Optimizer
In-Reply-To: <cf0868bd050914085233eae603@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox