Thread: Re: [HACKERS] 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
>
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);
}
}
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