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

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