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

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

The attached patch fixes the infinite recursion bug in
contrib/tablefunc/tablefunc.c:connectby found by Masaru Sugawara.

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)

test=# SELECT * FROM connectby('connectby_tree', 'keyid',
'parent_keyid', '2', 5, '~') AS t(keyid int, parent_keyid int, level
int, branch text);
ERROR: infinite recursion detected

I implemented it by checking the branch string for repeated keys
(whether or not the branch is returned). The performance hit was pretty
minimal -- about 1% for a moderately complex test case (220000 record
table, 9 level tree with 3800 members).

Please apply.

Thanks,

Joe

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

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.

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

Your patch has been added to the PostgreSQL unapplied patches list at:

http://candle.pha.pa.us/cgi-bin/pgpatches

I will try to apply it within the next 48 hours.

---------------------------------------------------------------------------

Joe Conway 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

The attached patch fixes the infinite recursion bug in
contrib/tablefunc/tablefunc.c:connectby found by Masaru Sugawara.

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)

test=# SELECT * FROM connectby('connectby_tree', 'keyid',
'parent_keyid', '2', 5, '~') AS t(keyid int, parent_keyid int, level
int, branch text);
ERROR: infinite recursion detected

I implemented it by checking the branch string for repeated keys
(whether or not the branch is returned). The performance hit was pretty
minimal -- about 1% for a moderately complex test case (220000 record
table, 9 level tree with 3800 members).

Please apply.

Thanks,

Joe

Index: contrib/tablefunc/tablefunc.c
===================================================================
RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/tablefunc.c,v
retrieving revision 1.7
diff -c -r1.7 tablefunc.c
*** contrib/tablefunc/tablefunc.c	5 Sep 2002 00:43:06 -0000	1.7
--- contrib/tablefunc/tablefunc.c	7 Sep 2002 16:28:50 -0000
***************
*** 801,806 ****
--- 801,810 ----
char		current_level[INT32_STRLEN];
char	   *current_branch;
char	  **values;
+ 		StringInfo	branchstr = NULL;
+ 
+ 		/* start a new branch */
+ 		branchstr = makeStringInfo();

if (show_branch)
values = (char **) palloc(CONNECTBY_NCOLS * sizeof(char *));
***************
*** 852,865 ****

for (i = 0; i < proc; i++)
{
! StringInfo branchstr = NULL;
!
! /* start a new branch */
! if (show_branch)
! {
! branchstr = makeStringInfo();
! appendStringInfo(branchstr, "%s", branch);
! }

/* get the next sql result tuple */
spi_tuple = tuptable->vals[i];
--- 856,863 ----

for (i = 0; i < proc; i++)
{
! /* initialize branch for this pass */
! appendStringInfo(branchstr, "%s", branch);

/* get the next sql result tuple */
spi_tuple = tuptable->vals[i];
***************
*** 868,884 ****
current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));

/* get the current level */
sprintf(current_level, "%d", level);

/* extend the branch */
! if (show_branch)
! {
! appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
! current_branch = branchstr->data;
! }
! else
! current_branch = NULL;

/* build a tuple */
values[0] = pstrdup(current_key);
--- 866,881 ----
current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));

+ 			/* check to see if this key is also an ancestor */
+ 			if (strstr(branchstr->data, current_key))
+ 				elog(ERROR, "infinite recursion detected");
+ 
/* get the current level */
sprintf(current_level, "%d", level);

/* extend the branch */
! appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
! current_branch = branchstr->data;

/* build a tuple */
values[0] = pstrdup(current_key);
***************
*** 916,921 ****
--- 913,922 ----
per_query_ctx,
attinmeta,
tupstore);
+ 
+ 			/* reset branch for next pass */
+ 			xpfree(branchstr->data);
+ 			initStringInfo(branchstr);
}
}

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Patch applied. Thanks.

---------------------------------------------------------------------------

Joe Conway 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

The attached patch fixes the infinite recursion bug in
contrib/tablefunc/tablefunc.c:connectby found by Masaru Sugawara.

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)

test=# SELECT * FROM connectby('connectby_tree', 'keyid',
'parent_keyid', '2', 5, '~') AS t(keyid int, parent_keyid int, level
int, branch text);
ERROR: infinite recursion detected

I implemented it by checking the branch string for repeated keys
(whether or not the branch is returned). The performance hit was pretty
minimal -- about 1% for a moderately complex test case (220000 record
table, 9 level tree with 3800 members).

Please apply.

Thanks,

Joe

Index: contrib/tablefunc/tablefunc.c
===================================================================
RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/tablefunc.c,v
retrieving revision 1.7
diff -c -r1.7 tablefunc.c
*** contrib/tablefunc/tablefunc.c	5 Sep 2002 00:43:06 -0000	1.7
--- contrib/tablefunc/tablefunc.c	7 Sep 2002 16:28:50 -0000
***************
*** 801,806 ****
--- 801,810 ----
char		current_level[INT32_STRLEN];
char	   *current_branch;
char	  **values;
+ 		StringInfo	branchstr = NULL;
+ 
+ 		/* start a new branch */
+ 		branchstr = makeStringInfo();

if (show_branch)
values = (char **) palloc(CONNECTBY_NCOLS * sizeof(char *));
***************
*** 852,865 ****

for (i = 0; i < proc; i++)
{
! StringInfo branchstr = NULL;
!
! /* start a new branch */
! if (show_branch)
! {
! branchstr = makeStringInfo();
! appendStringInfo(branchstr, "%s", branch);
! }

/* get the next sql result tuple */
spi_tuple = tuptable->vals[i];
--- 856,863 ----

for (i = 0; i < proc; i++)
{
! /* initialize branch for this pass */
! appendStringInfo(branchstr, "%s", branch);

/* get the next sql result tuple */
spi_tuple = tuptable->vals[i];
***************
*** 868,884 ****
current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));

/* get the current level */
sprintf(current_level, "%d", level);

/* extend the branch */
! if (show_branch)
! {
! appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
! current_branch = branchstr->data;
! }
! else
! current_branch = NULL;

/* build a tuple */
values[0] = pstrdup(current_key);
--- 866,881 ----
current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));

+ 			/* check to see if this key is also an ancestor */
+ 			if (strstr(branchstr->data, current_key))
+ 				elog(ERROR, "infinite recursion detected");
+ 
/* get the current level */
sprintf(current_level, "%d", level);

/* extend the branch */
! appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
! current_branch = branchstr->data;

/* build a tuple */
values[0] = pstrdup(current_key);
***************
*** 916,921 ****
--- 913,922 ----
per_query_ctx,
attinmeta,
tupstore);
+ 
+ 			/* reset branch for next pass */
+ 			xpfree(branchstr->data);
+ 			initStringInfo(branchstr);
}
}

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073