Re: WITH RECURSIVE patch V0.1

On Sun, 2008-05-18 at 22:17 -0700, David Fetter wrote:
> On Mon, May 19, 2008 at 12:21:20AM -0400, Gregory Stark wrote:
> > "Zoltan Boszormenyi" <zb(at)cybertec(dot)at> writes:
> > > Also, it seems there are no infinite recursion detection:
> > >
> > > # with recursive x(level, parent, child) as (
> > > select 1::integer, * from test_connect_by where parent is null
> > > union all
> > > select x.level + 1, base.* from test_connect_by as base, x where base.child
> > > = x.child
> > > ) select * from x;
> > > ... it waits and waits and waits ...
> >
> > Well, psql might wait and wait but it's actually receiving rows. A
> > cleverer client should be able to deal with infinite streams of
> > records.
>
> That would be a very good thing for libpq (and its descendants) to
> have :)
>
> > I think DB2 does produce a warning if there is no clause it can
> > determine will bound the results. But that's not actually reliable.
>
> I'd think not, as it's (in some sense) a Halting Problem.
>
> > It's quite possible to have clauses which will limit the output but
> > not in a way the database can determine. Consider for example a
> > tree-traversal for a binary tree stored in a recursive table
> > reference. The DBA might know that the data contains no loops but
> > the database doesn't.
>
> I seem to recall Oracle's implementation can do this traversal on
> write operations, but maybe that's just their marketing.

It may be possible to solve at least some of it by doing something
similar to hash version of DISTINCT by having an hashtable of tuples
already returned and not descending branches where you have already
been.

> Cheers,
> David.
> --
> David Fetter <david(at)fetter(dot)org> http://fetter.org/
> Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
> Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
>
> Remember to vote!
> Consider donating to Postgres: http://www.postgresql.org/about/donate
>