Re: About connectby() - Mailing list pgsql-hackers

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