Re: PostGreSQL and recursive queries...

_________________________________________________
Ce message et les éventuels documents joints peuvent contenir des informations confidentielles.
Au cas où il ne vous serait pas destiné, nous vous remercions de bien vouloir le supprimer et en aviser immédiatement l'expéditeur. Toute utilisation de ce message non conforme à sa destination, toute diffusion ou publication, totale ou partielle et quel qu'en soit le moyen est formellement interdite.
Les communications sur internet n'étant pas sécurisées, l'intégrité de ce message n'est pas assurée et la société émettrice ne peut être tenue pour responsable de son contenu.

"Hubert FONGARNAND" <informatique(dot)internet(at)fiducial(dot)fr> writes:

> Ce message et les éventuels documents joints peuvent contenir des
> informations confidentielles. Au cas où il ne vous serait pas destiné, nous
> vous remercions de bien vouloir le supprimer et en aviser immédiatement
> l'expéditeur. Toute utilisation de ce message non conforme à sa destination,
> toute diffusion ou publication, totale ou partielle et quel qu'en soit le
> moyen est formellement interdite. Les communications sur internet n'étant
> pas sécurisées, l'intégrité de ce message n'est pas assurée et la société
> émettrice ne peut être tenue pour responsable de son contenu.

I started working on WITH RECURSIVE a while back and still intend to get back
to it. But there's no guarantee that what I turn up will be to the liking of
everyone else.

I also think the connectby() patch should be possible to port forward but I
haven't looked too much into it. I know it's a big patch, just the sheer
amount of code that has to be gone through carefully to port it forward might
make it kind of hard.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's PostGIS support!

> "Hubert FONGARNAND" <informatique(dot)internet(at)fiducial(dot)fr> writes:
>
> > Ce message et les éventuels documents joints peuvent contenir des
> > informations confidentielles. Au cas où il ne vous serait pas destiné, nous
> > vous remercions de bien vouloir le supprimer et en aviser immédiatement
> > l'expéditeur. Toute utilisation de ce message non conforme à sa destination,
> > toute diffusion ou publication, totale ou partielle et quel qu'en soit le
> > moyen est formellement interdite. Les communications sur internet n'étant
> > pas sécurisées, l'intégrité de ce message n'est pas assurée et la société
> > émettrice ne peut être tenue pour responsable de son contenu.
>
> I started working on WITH RECURSIVE a while back and still intend to get back
> to it. But there's no guarantee that what I turn up will be to the liking of
> everyone else.
>
> I also think the connectby() patch should be possible to port forward but I
> haven't looked too much into it. I know it's a big patch, just the sheer
> amount of code that has to be gone through carefully to port it forward might
> make it kind of hard.

Hi,

We decided to start working on WITH RECURSIVE too. Currently one of
our engineers is about to start to look at what has been done and what
is remaining. We hope to work together with you!
--
Tatsuo Ishii
SRA OSS, Inc. Japan

"Tatsuo Ishii" <ishii(at)postgresql(dot)org> writes:

> We decided to start working on WITH RECURSIVE too. Currently one of
> our engineers is about to start to look at what has been done and what
> is remaining. We hope to work together with you!

Here's the original message where I posted what I think we need in the
executor to make this work:

http://archives.postgresql.org/pgsql-hackers/2007-01/msg01495.php

Here's another thread where we discussed some further issues:

http://archives.postgresql.org/pgsql-hackers/2007-02/msg01229.php

This is all about the executor though, which I've since learned not to expect
to be the source of the headaches. The planner is infinitely more complex and
subtle.

Hopefully at the cte call sites we'll be able to gin up enough information to
fill in the subquery information enough for the planner above to work with it.
I could imagine problems the planner would have to deal with though, such as
what type is "bogon" in this query?

WITH RECURSIVE x(bogon) AS (select bogon from x) select * from x;

what about something like:

WITH RECURSIVE x(bogon) AS (select bogon+1 from x) select * from x;

note that the usual case is something like:

WITH RECURSIVE x(bogon)
AS (SELECT 1
UNION ALL
SELECT bogon+1
FROM x)
SELECT *
FROM x
WHERE bogon < ?

So the we can't refuse just anything where the types are recursively
dependent. We might have to do something weird like make the types of a
recursive call "unknown" until it's planned then go back and replan recursive
queries making use of the new information to catch things like:

create function foo(int) returns text ...
create function foo(text) returns int ...

with recursive x(bogon)
as (select 1 union all select foo(bogon) from x)
select * from x

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's Slony Replication support!

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> I could imagine problems the planner would have to deal with though, such as
> what type is "bogon" in this query?

> WITH RECURSIVE x(bogon) AS (select bogon from x) select * from x;

Just a note --- that's not the planner's problem, either. Semantic
interpretation of the meaning of a query is supposed to be completed
during parse analysis.

regards, tom lane

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Gregory Stark <stark(at)enterprisedb(dot)com> writes:
>> I could imagine problems the planner would have to deal with though, such as
>> what type is "bogon" in this query?
>
>> WITH RECURSIVE x(bogon) AS (select bogon from x) select * from x;
>
> Just a note --- that's not the planner's problem, either. Semantic
> interpretation of the meaning of a query is supposed to be completed
> during parse analysis.

I was being sloppy. I just mean as opposed to the executor. Ie, that the code
to build the plan is harder than actually running it.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's RemoteDBA services!

[ I'm not very sure of my WITH RECURSIVE syntax, so please excuse any
mistakes ]

On Fri, Nov 30, 2007 at 01:00:27PM +0000, Gregory Stark wrote:
> Hopefully at the cte call sites we'll be able to gin up enough information to
> fill in the subquery information enough for the planner above to work with it.
> I could imagine problems the planner would have to deal with though, such as
> what type is "bogon" in this query?
>
> WITH RECURSIVE x(bogon) AS (select bogon from x) select * from x;

That shouldn't be allowed, no types could be deduced. The following
would be allowed though:

WITH RECURSIVE x(bogon) AS (select bogon from x)
select * from x WHERE bogon < 1;

The WHERE clause will constrain bogon to be an INTEGER which can be
unified with everything else, allowing the query to run.

> what about something like:
>
> WITH RECURSIVE x(bogon) AS (select bogon+1 from x) select * from x;

As above, that'll return an integer.

> note that the usual case is something like:
>
> WITH RECURSIVE x(bogon)
> AS (SELECT 1
> UNION ALL
> SELECT bogon+1
> FROM x)
> SELECT *
> FROM x
> WHERE bogon < ?
>
> So the we can't refuse just anything where the types are recursively
> dependent.

Sounds as though you need some sort of type inference algorithm. There
are quite a few decidable ones around, the one by Hindley-Milner being
very popular/common. Decidable means you get the correct answer out in
a reasonable amount of time or it fails, and, barring implementation
bugs, it'll never get stuck trying to figure out what you meant.

> We might have to do something weird like make the types of a
> recursive call "unknown" until it's planned then go back and replan recursive
> queries making use of the new information to catch things like:
>
> create function foo(int) returns text ...
> create function foo(text) returns int ...
>
> with recursive x(bogon)
> as (select 1 union all select foo(bogon) from x)
> select * from x

When would something like the above actually be used in practise?

Supporting things like that would open up a whole bag of undecidable
nastiness (+ associated confusion for the user, when it all goes wrong)
for what I would think is a small increase in expressiveness.

Sam

Sam Mason <sam(at)samason(dot)me(dot)uk> writes:
> Sounds as though you need some sort of type inference algorithm. There
> are quite a few decidable ones around, the one by Hindley-Milner being
> very popular/common. Decidable means you get the correct answer out in
> a reasonable amount of time or it fails, and, barring implementation
> bugs, it'll never get stuck trying to figure out what you meant.

I think some closer reading of the SQL spec might be called for.
I'm pretty sure the spec authors did not intend to require any
especially abstruse algorithm to infer the types involved in a recursive
query. In fact, if they have not completely abandoned their duty as
spec writers, the spec itself should spell out any algorithms required
to determine the meaning of a query. (As distinct from algorithms
needed to produce an efficient implementation, which is a topic outside
the purview of the spec. But "what type is this result column" is
surely something the spec is required to define.)

regards, tom lane