Postgres Pro
Downloads
Home   >   mailing lists

Thread: About connectby()

About connectby()

From
Masaru Sugawara
Date:
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

Re: About connectby()

From
Joe Conway
Date:
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

Re: About connectby()

From
David Walker
Date:
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

Re: About connectby()

From
Joe Conway
Date:
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

Re: About connectby()

From
Joe Conway
Date:
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

Re: About connectby()

From
Masaru Sugawara
Date:
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