Обсуждение: About connectby()
Now I'm testing connectby() in the /contrib/tablefunc in 7.3b1, which would be a useful function for many users. However, I found the fact that if connectby_tree has the following data, connectby() tries to search the end of roots without knowing that the relations are infinite(-5-9-10-11-9-10-11-) . I hope connectby() supports a check routine to find infinite relations. CREATE TABLE connectby_tree(keyid int, parent_keyid int); INSERT INTO connectby_tree VALUES(1,NULL); INSERT INTO connectby_tree VALUES(2,1); INSERT INTO connectby_tree VALUES(3,1); INSERT INTO connectby_tree VALUES(4,2); INSERT INTO connectby_tree VALUES(5,2); INSERT INTO connectby_tree VALUES(6,4); INSERT INTO connectby_tree VALUES(7,3); INSERT INTO connectby_tree VALUES(8,6); INSERT INTO connectby_tree VALUES(9,5); INSERT INTO connectby_tree VALUES(10,9); INSERT INTO connectby_tree VALUES(11,10); INSERT INTO connectby_tree VALUES(9,11); <-- infinite Regards, Masaru Sugawara
Masaru Sugawara wrote: > Now I'm testing connectby() in the /contrib/tablefunc in 7.3b1, which would > be a useful function for many users. However, I found the fact that > if connectby_tree has the following data, connectby() tries to search the end > of roots without knowing that the relations are infinite(-5-9-10-11-9-10-11-) . > I hope connectby() supports a check routine to find infinite relations. > > > CREATE TABLE connectby_tree(keyid int, parent_keyid int); > INSERT INTO connectby_tree VALUES(1,NULL); > INSERT INTO connectby_tree VALUES(2,1); > INSERT INTO connectby_tree VALUES(3,1); > INSERT INTO connectby_tree VALUES(4,2); > INSERT INTO connectby_tree VALUES(5,2); > INSERT INTO connectby_tree VALUES(6,4); > INSERT INTO connectby_tree VALUES(7,3); > INSERT INTO connectby_tree VALUES(8,6); > INSERT INTO connectby_tree VALUES(9,5); > > INSERT INTO connectby_tree VALUES(10,9); > INSERT INTO connectby_tree VALUES(11,10); > INSERT INTO connectby_tree VALUES(9,11); <-- infinite Hmm, good point. I can think of two ways to deal with this: 1. impose an arbitrary absolute limit on recursion depth 2. perform a relatively expensive ancestor check I didn't really want to do #1. You can already use max_depth to cap off infinite recursion: test=# SELECT * FROM connectby('connectby_tree', 'keyid', 'parent_keyid', '2', 8, '~') AS t(keyid int, parent_keyid int, level int, branch text); keyid | parent_keyid | level | branch -------+--------------+-------+----------------------- 2 | | 0 | 2 4 | 2 | 1 | 2~4 6 | 4 | 2 | 2~4~6 8 | 6 | 3 | 2~4~6~8 5 | 2 | 1 | 2~5 9 | 5 | 2 | 2~5~9 10 | 9 | 3 | 2~5~9~10 11 | 10 | 4 | 2~5~9~10~11 9 | 11 | 5 | 2~5~9~10~11~9 10 | 9 | 6 | 2~5~9~10~11~9~10 11 | 10 | 7 | 2~5~9~10~11~9~10~11 9 | 11 | 8 | 2~5~9~10~11~9~10~11~9 (12 rows) I guess it would be better to look for repeating values in branch and bail out there. I'm just a bit worried about the added processing overhead. It also means branch will have to be built, even if it is not returned, eliminating the efficiency gain of using the function without returning branch. Any other suggestions? Thanks, Joe
I prefer the max depth method. Every tree I am aware of has a maximum usable depth. This should never be a problem in trees where keyid is unique. On Saturday 07 September 2002 10:35 am, (Via wrote: > Masaru Sugawara wrote: > > Now I'm testing connectby() in the /contrib/tablefunc in 7.3b1, which > > would be a useful function for many users. However, I found the fact > > that if connectby_tree has the following data, connectby() tries to > > search the end of roots without knowing that the relations are > > infinite(-5-9-10-11-9-10-11-) . I hope connectby() supports a check > > routine to find infinite relations. > > > > > > CREATE TABLE connectby_tree(keyid int, parent_keyid int); > > INSERT INTO connectby_tree VALUES(1,NULL); > > INSERT INTO connectby_tree VALUES(2,1); > > INSERT INTO connectby_tree VALUES(3,1); > > INSERT INTO connectby_tree VALUES(4,2); > > INSERT INTO connectby_tree VALUES(5,2); > > INSERT INTO connectby_tree VALUES(6,4); > > INSERT INTO connectby_tree VALUES(7,3); > > INSERT INTO connectby_tree VALUES(8,6); > > INSERT INTO connectby_tree VALUES(9,5); > > > > INSERT INTO connectby_tree VALUES(10,9); > > INSERT INTO connectby_tree VALUES(11,10); > > INSERT INTO connectby_tree VALUES(9,11); <-- infinite > > Hmm, good point. I can think of two ways to deal with this: > 1. impose an arbitrary absolute limit on recursion depth > 2. perform a relatively expensive ancestor check > > I didn't really want to do #1. You can already use max_depth to cap off > infinite recursion: > > test=# SELECT * FROM connectby('connectby_tree', 'keyid', > 'parent_keyid', '2', 8, '~') AS t(keyid int, parent_keyid int, level > int, branch text); > keyid | parent_keyid | level | branch > -------+--------------+-------+----------------------- > 2 | | 0 | 2 > 4 | 2 | 1 | 2~4 > 6 | 4 | 2 | 2~4~6 > 8 | 6 | 3 | 2~4~6~8 > 5 | 2 | 1 | 2~5 > 9 | 5 | 2 | 2~5~9 > 10 | 9 | 3 | 2~5~9~10 > 11 | 10 | 4 | 2~5~9~10~11 > 9 | 11 | 5 | 2~5~9~10~11~9 > 10 | 9 | 6 | 2~5~9~10~11~9~10 > 11 | 10 | 7 | 2~5~9~10~11~9~10~11 > 9 | 11 | 8 | 2~5~9~10~11~9~10~11~9 > (12 rows) > > I guess it would be better to look for repeating values in branch and > bail out there. I'm just a bit worried about the added processing > overhead. It also means branch will have to be built, even if it is not > returned, eliminating the efficiency gain of using the function without > returning branch. > > Any other suggestions? > > Thanks, > > Joe > > > ---------------------------(end of broadcast)--------------------------- > TIP 4: Don't 'kill -9' the postmaster
Masaru Sugawara wrote: > Now I'm testing connectby() in the /contrib/tablefunc in 7.3b1, which would > be a useful function for many users. However, I found the fact that > if connectby_tree has the following data, connectby() tries to search the end > of roots without knowing that the relations are infinite(-5-9-10-11-9-10-11-) . > I hope connectby() supports a check routine to find infinite relations. > > > CREATE TABLE connectby_tree(keyid int, parent_keyid int); > INSERT INTO connectby_tree VALUES(1,NULL); > INSERT INTO connectby_tree VALUES(2,1); > INSERT INTO connectby_tree VALUES(3,1); > INSERT INTO connectby_tree VALUES(4,2); > INSERT INTO connectby_tree VALUES(5,2); > INSERT INTO connectby_tree VALUES(6,4); > INSERT INTO connectby_tree VALUES(7,3); > INSERT INTO connectby_tree VALUES(8,6); > INSERT INTO connectby_tree VALUES(9,5); > > INSERT INTO connectby_tree VALUES(10,9); > INSERT INTO connectby_tree VALUES(11,10); > INSERT INTO connectby_tree VALUES(9,11); <-- infinite > OK -- patch submitted to fix this. Once the patch is applied, this case gives: test=# SELECT * FROM connectby('connectby_tree', 'keyid', 'parent_keyid', '2', 0, '~') AS t(keyid int, parent_keyid int, level int, branch text); ERROR: infinite recursion detected If you specifically limit the depth to less than where the repeated key is hit, everything works as before: test=# SELECT * FROM connectby('connectby_tree', 'keyid', 'parent_keyid', '2', 4, '~') AS t(keyid int, parent_keyid int, level int, branch text); keyid | parent_keyid | level | branch -------+--------------+-------+------------- 2 | | 0 | 2 4 | 2 | 1 | 2~4 6 | 4 | 2 | 2~4~6 8 | 6 | 3 | 2~4~6~8 5 | 2 | 1 | 2~5 9 | 5 | 2 | 2~5~9 10 | 9 | 3 | 2~5~9~10 11 | 10 | 4 | 2~5~9~10~11 (8 rows) Thanks for the feedback! Joe
David Walker wrote: > I prefer the max depth method. Every tree I am aware of has a maximum usable > depth. > > This should never be a problem in trees where keyid is unique. > I just sent in a patch using the ancestor check method. It turned out that the performance hit was pretty small on a moderate sized tree. My test case was a 220000 record bill-of-material table. The tree built was 9 levels deep with about 3800 nodes. The performance hit was only about 1%. Are there cases where infinite recursion to some max depth *should* be allowed? I couldn't think of any. If a max depth was imposed, what should it be? Joe
On Sat, 07 Sep 2002 10:26:36 -0700 Joe Conway <mail@joeconway.com> wrote: > > OK -- patch submitted to fix this. Once the patch is applied, this case > gives: > > test=# SELECT * FROM connectby('connectby_tree', 'keyid', > 'parent_keyid', '2', 0, '~') AS t(keyid int, parent_keyid int, level > int, branch text); > ERROR: infinite recursion detected Thank you for your patch. > > If you specifically limit the depth to less than where the repeated key > is hit, everything works as before: And I also think this approach is reasonable. > > test=# SELECT * FROM connectby('connectby_tree', 'keyid', > 'parent_keyid', '2', 4, '~') AS t(keyid int, parent_keyid int, level > int, branch text); > keyid | parent_keyid | level | branch > -------+--------------+-------+------------- > 2 | | 0 | 2 > 4 | 2 | 1 | 2~4 > 6 | 4 | 2 | 2~4~6 > 8 | 6 | 3 | 2~4~6~8 > 5 | 2 | 1 | 2~5 > 9 | 5 | 2 | 2~5~9 > 10 | 9 | 3 | 2~5~9~10 > 11 | 10 | 4 | 2~5~9~10~11 > (8 rows) > > Thanks for the feedback! > > Joe > > Regards, Masaru Sugawara