Re: About connectby()

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