Thread: WITH RECUSIVE patches 0717
Hi,
Here is the lastest WITH RECURSIVE patches against CVS HEAD created by
Yoshiyuki Asaba and minor corrections by Tatsuo Ishii. (David Fetter's
psql help patches are not included. It seems his git repository has
gone).
This version implements:
- detect certain queries those are not valid acroding to the standard
I also include erroneous query examples created by Yoshiyuki (probably
will become part of regression tests).
Remaining problmes are:
1) sort query names acording to the dependency
2) planner always estimate 0 cost for recursion plans
3) add regression tests
For 1), I have proposed we limit query names to 1, in another word do
not allow mutually recursive queries. For 2) there's no good idea to
solve it, so I suggest leave it as it is now.
For 3) I will generate regression tests as soon as possible.
So the patches seem to be almost ready to commit IMO.
--
Tatsuo Ishii
SRA OSS, Inc. Japan
-- UNION
WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x)
SELECT * FROM x;
-- INTERSECT
WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x)
SELECT * FROM x;
WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x)
SELECT * FROM x;
-- EXCEPT
WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x)
SELECT * FROM x;
WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x)
SELECT * FROM x;
-- 再帰項なし
WITH RECURSIVE x(n) AS (SELECT n FROM x)
SELECT * FROM x;
-- 左側に再帰項がある
WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1)
SELECT * FROM x;
CREATE TEMP TABLE y (a int);
INSERT INTO y SELECT generate_series(1, 10);
-- LEFT JOIN
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 UNION ALL SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a where n <
10)
SELECT * FROM x;
-- RIGHT JOIN
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 UNION ALL SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a where n <
10)
SELECT * FROM x;
-- FULL JOIN
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 UNION ALL SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a where n <
10)
SELECT * FROM x;
-- subquery
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x
WHERE n IN (SELECT * FROM x))
SELECT * FROM x;
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x
WHERE n = 1 AND n IN (SELECT * FROM x))
SELECT * FROM x;
-- GROUP BY
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x GROUP BY n)
SELECT * FROM x;
-- HAVING
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x HAVING n < 10)
SELECT * FROM x;
-- 集約関数
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x)
SELECT * FROM x;
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(*) FROM x)
SELECT * FROM x;
On Thu, Jul 17, 2008 at 06:40:25PM +0900, Tatsuo Ishii wrote: > Hi, > > Here is the lastest WITH RECURSIVE patches against CVS HEAD created by > Yoshiyuki Asaba and minor corrections by Tatsuo Ishii. I tried this patch vs. CVS HEAD used my usual configure option with only --with-prefix set, then tried to make, and got: make[3]: *** No rule to make target `parse_cte.o', needed by `objfiles.txt'. Stop. make[3]: Leaving directory `/home/shackle/pgsql/src/backend/parser' make[2]: *** [parser-recursive] Error 2 make[2]: Leaving directory `/home/shackle/pgsql/src/backend' make[1]: *** [all] Error 2 make[1]: Leaving directory `/home/shackle/pgsql/src' make: *** [all] Error 2 Is there something missing? > (David Fetter's psql help patches are not included. It seems his git > repository has gone). I apologize for that. I rearranged it last night because the name was not scalable, but delayed sending this out until today. It can now be found at <http://git.postgresql.org/?p=~davidfetter/with_recursive/.git;a=summary> To pull from the new location, in your .git/config, change URL from something like the following: url = git://davidfetter@git.postgresql.org/git/~davidfetter/postgresql/.git to url = git://davidfetter@git.postgresql.org/git/~davidfetter/with_recursive/.git > This version implements: > > - detect certain queries those are not valid acroding to the standard Great :) > I also include erroneous query examples created by Yoshiyuki (probably > will become part of regression tests). > > Remaining problmes are: > > 1) sort query names acording to the dependency This can be done at query time already using arrays per Asaba-san's suggestion. I'll add some examples to the documentation. > 2) planner always estimate 0 cost for recursion plans > 3) add regression tests > > For 1), I have proposed we limit query names to 1, in another word do > not allow mutually recursive queries. For 2) there's no good idea to > solve it, so I suggest leave it as it is now. > > For 3) I will generate regression tests as soon as possible. > > So the patches seem to be almost ready to commit IMO. Wonderful! Cheers, David. -- David Fetter <david@fetter.org> http://fetter.org/ Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter Skype: davidfetter XMPP: david.fetter@gmail.com Remember to vote! Consider donating to Postgres: http://www.postgresql.org/about/donate
> > Here is the lastest WITH RECURSIVE patches against CVS HEAD created by > > Yoshiyuki Asaba and minor corrections by Tatsuo Ishii. > > I tried this patch vs. CVS HEAD used my usual configure option with > only --with-prefix set, then tried to make, and got: > > make[3]: *** No rule to make target `parse_cte.o', needed by `objfiles.txt'. Stop. > make[3]: Leaving directory `/home/shackle/pgsql/src/backend/parser' > make[2]: *** [parser-recursive] Error 2 > make[2]: Leaving directory `/home/shackle/pgsql/src/backend' > make[1]: *** [all] Error 2 > make[1]: Leaving directory `/home/shackle/pgsql/src' > make: *** [all] Error 2 > > Is there something missing? Oops. I forgot to include patches against newly added files. Please try included patches. > > (David Fetter's psql help patches are not included. It seems his git > > repository has gone). > > I apologize for that. I rearranged it last night because the name was > not scalable, but delayed sending this out until today. It can now be > found at > > <http://git.postgresql.org/?p=~davidfetter/with_recursive/.git;a=summary> > > To pull from the new location, in your .git/config, change URL from something > like the following: > > url = git://davidfetter@git.postgresql.org/git/~davidfetter/postgresql/.git > > to > > url = git://davidfetter@git.postgresql.org/git/~davidfetter/with_recursive/.git Let me try later. > > This version implements: > > > > - detect certain queries those are not valid acroding to the standard > > Great :) > > > I also include erroneous query examples created by Yoshiyuki (probably > > will become part of regression tests). > > > > Remaining problmes are: > > > > 1) sort query names acording to the dependency > > This can be done at query time already using arrays per Asaba-san's > suggestion. I'll add some examples to the documentation. 1) refers to mutually recursive queres. > > 2) planner always estimate 0 cost for recursion plans > > 3) add regression tests > > > > For 1), I have proposed we limit query names to 1, in another word do > > not allow mutually recursive queries. For 2) there's no good idea to > > solve it, so I suggest leave it as it is now. > > > > For 3) I will generate regression tests as soon as possible. > > > > So the patches seem to be almost ready to commit IMO. > > Wonderful! > > Cheers, > David. > -- > David Fetter <david@fetter.org> http://fetter.org/ > Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter > Skype: davidfetter XMPP: david.fetter@gmail.com > > Remember to vote! > Consider donating to Postgres: http://www.postgresql.org/about/donate
Attachment
On Fri, Jul 18, 2008 at 10:41:20AM +0900, Tatsuo Ishii wrote:
> > > Here is the lastest WITH RECURSIVE patches against CVS HEAD created by
> > > Yoshiyuki Asaba and minor corrections by Tatsuo Ishii.
> >
> > I tried this patch vs. CVS HEAD used my usual configure option with
> > only --with-prefix set, then tried to make, and got:
> >
> > make[3]: *** No rule to make target `parse_cte.o', needed by `objfiles.txt'. Stop.
> > make[3]: Leaving directory `/home/shackle/pgsql/src/backend/parser'
> > make[2]: *** [parser-recursive] Error 2
> > make[2]: Leaving directory `/home/shackle/pgsql/src/backend'
> > make[1]: *** [all] Error 2
> > make[1]: Leaving directory `/home/shackle/pgsql/src'
> > make: *** [all] Error 2
> >
> > Is there something missing?
>
> Oops. I forgot to include patches against newly added files. Please
> try included patches.
This now compiles.
I have a test case that hangs and smashes.
WITH t(i) AS (
SELECT * FROM generate_series(1,5)
)
SELECT
t1.i,
2*t2.i
FROM
t AS t1
JOIN
t AS t2 USING(i);
server closed the connection unexpectedly
This probably means the server terminated abnormally
before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.
An equivalent query without RECURSIVE breaks in a different, in some
sense even more severe, way, as in it just hands out a wrong result
set:
WITH RECURSIVE t(i) AS (
VALUES(1::int)
UNION ALL
SELECT i+1 FROM t WHERE i < 5
)
SELECT
t1.i,
2*t2.i
FROM
t AS t1
JOIN
t AS t2 USING(i);
i | ?column?
---+----------
1 | 2
2 | 4
3 | 6
4 | 8
5 | 10
(5 rows)
While this case is trivial, others are not. For example, if someone
wishes to do a k-deep summary on a parts explosion n levels deep, n>k,
one way to do this would be to JOIN the k-deep part of the path
enumeration to the parts greater than k deep.
What would need to be fixed in order to make the above things work?
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
On Fri, Jul 18, 2008 at 07:56:09AM -0700, David Fetter wrote: > On Fri, Jul 18, 2008 at 10:41:20AM +0900, Tatsuo Ishii wrote: > > > > Here is the lastest WITH RECURSIVE patches against CVS HEAD created by > > > > Yoshiyuki Asaba and minor corrections by Tatsuo Ishii. > > > > > > I tried this patch vs. CVS HEAD used my usual configure option with > > > only --with-prefix set, then tried to make, and got: > > > > > > make[3]: *** No rule to make target `parse_cte.o', needed by `objfiles.txt'. Stop. > > > make[3]: Leaving directory `/home/shackle/pgsql/src/backend/parser' > > > make[2]: *** [parser-recursive] Error 2 > > > make[2]: Leaving directory `/home/shackle/pgsql/src/backend' > > > make[1]: *** [all] Error 2 > > > make[1]: Leaving directory `/home/shackle/pgsql/src' > > > make: *** [all] Error 2 > > > > > > Is there something missing? > > > > Oops. I forgot to include patches against newly added files. Please > > try included patches. > > This now compiles. > > I have a test case that hangs and smashes. > > WITH t(i) AS ( > SELECT * FROM generate_series(1,5) > ) > SELECT > t1.i, > 2*t2.i > FROM > t AS t1 > JOIN > t AS t2 USING(i); > > server closed the connection unexpectedly > This probably means the server terminated abnormally > before or while processing the request. > The connection to the server was lost. Attempting reset: Failed. > > An equivalent query without RECURSIVE breaks in a different, in some > sense even more severe, way, as in it just hands out a wrong result > set: D'oh! That's what I get for sending this before waking up. It works just fine. > While this case is trivial, others are not. For example, if someone > wishes to do a k-deep summary on a parts explosion n levels deep, > n>k, one way to do this would be to JOIN the k-deep part of the path > enumeration to the parts greater than k deep. > > What would need to be fixed in order to make the above things work? Cheers, David. -- David Fetter <david@fetter.org> http://fetter.org/ Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter Skype: davidfetter XMPP: david.fetter@gmail.com Remember to vote! Consider donating to Postgres: http://www.postgresql.org/about/donate