On Sat, 07 Sep 2002 10:21:21 -0700
Joe Conway <mail@joeconway.com> wrote:

> 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%.


The previous patch fixed an infinite recursion bug in 
contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
seems to occur even if a table has commonplace tree data(see below).


I would think the patch, ancestor check, should be

  if (strstr(branch_delim || branchstr->data || branch_delim,
                       branch_delim || current_key || branch_delim))

This is my image, not a real code. However, if branchstr->data includes
branch_delim, my image will not be perfect.




-- test connectby with int based hierarchy
DROP TABLE connectby_tree;
CREATE TABLE connectby_tree(keyid int, parent_keyid int);

INSERT INTO connectby_tree VALUES(11,NULL);
INSERT INTO connectby_tree VALUES(10,11);
INSERT INTO connectby_tree VALUES(111,11);
INSERT INTO connectby_tree VALUES(1,111);

SELECT * FROM connectby('connectby_tree', 'keyid', 'parent_keyid', '11', 0, '-')
   AS t(keyid int, parent_keyid int, level int, branch text)

ERROR:  infinite recursion detected



Regards,
Masaru Sugawara



Fri, 27 Sep 2002 02:02:49 +0900
Masaru Sugawara <rk73@sea.plala.or.jp>
About connectby()  again
On Fri, 27 Sep 2002 02:02:49 +0900
I wrote <rk73@sea.plala.or.jp> wrote:


> On Sat, 07 Sep 2002 10:21:21 -0700
> Joe Conway <mail@joeconway.com> wrote:
> 
> > 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%.
> 
> 
> The previous patch fixed an infinite recursion bug in 
> contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
> seems to occur even if a table has commonplace tree data(see below).
> 
> 
> I would think the patch, ancestor check, should be
> 
>   if (strstr(branch_delim || branchstr->data || branch_delim,
>                        branch_delim || current_key || branch_delim))
> 
> This is my image, not a real code. However, if branchstr->data includes
                                                       ^^^^^^^^^^^^^^^^^^^^^^^^^
                                                       keyid or parent_keyid

> branch_delim, my image will not be perfect.
> 
> 
> 
> 
> -- test connectby with int based hierarchy
> DROP TABLE connectby_tree;
> CREATE TABLE connectby_tree(keyid int, parent_keyid int);
> 
> INSERT INTO connectby_tree VALUES(11,NULL);
> INSERT INTO connectby_tree VALUES(10,11);
> INSERT INTO connectby_tree VALUES(111,11);
> INSERT INTO connectby_tree VALUES(1,111);
> 
> SELECT * FROM connectby('connectby_tree', 'keyid', 'parent_keyid', '11', 0, '-')
>    AS t(keyid int, parent_keyid int, level int, branch text)
> 
> ERROR:  infinite recursion detected
> 
> 
> 
> Regards,
> Masaru Sugawara
> 
> 
> 
> ---------------------------(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



Regards,
Masaru Sugawara



Fri, 27 Sep 2002 02:27:05 +0900
Masaru Sugawara <rk73@sea.plala.or.jp>
Re: About connectby()  again
Masaru Sugawara wrote:
> The previous patch fixed an infinite recursion bug in 
> contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
> seems to occur even if a table has commonplace tree data(see below).
> 
> I would think the patch, ancestor check, should be
> 
>   if (strstr(branch_delim || branchstr->data || branch_delim,
>                        branch_delim || current_key || branch_delim))
> 
> This is my image, not a real code. However, if branchstr->data includes
> branch_delim, my image will not be perfect.

Good point. Thank you Masaru for the suggested fix.

Attached is a patch to fix the bug found by Masaru. His example now produces:

regression=# SELECT * FROM connectby('connectby_tree', 'keyid', 
'parent_keyid', '11', 0, '-') AS t(keyid int, parent_keyid int, level int, 
branch text);
  keyid | parent_keyid | level |  branch
-------+--------------+-------+----------
     11 |              |     0 | 11
     10 |           11 |     1 | 11-10
    111 |           11 |     1 | 11-111
      1 |          111 |     2 | 11-111-1
(4 rows)

While making the patch I also realized that the "no show branch" form of the 
function was not going to work very well for recursion detection. Therefore 
there is now a default branch delimiter ('~') that is used internally, for 
that case, to enable recursion detection to work. If you need a different 
delimiter for your specific data, you will have to use the "show branch" form 
of the function.

If there are no objections, please apply. Thanks,

Joe
Thu, 26 Sep 2002 16:32:08 -0700
Joe Conway <mail@joeconway.com>
Re: About connectby()  again
On Thu, 26 Sep 2002 16:32:08 -0700
Joe Conway <mail@joeconway.com> wrote:


> Masaru Sugawara wrote:
> > The previous patch fixed an infinite recursion bug in 
> > contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
> > seems to occur even if a table has commonplace tree data(see below).
> > 
> > I would think the patch, ancestor check, should be
> > 
> >   if (strstr(branch_delim || branchstr->data || branch_delim,
> >                        branch_delim || current_key || branch_delim))
> > 
> > This is my image, not a real code. However, if branchstr->data includes
> > branch_delim, my image will not be perfect.
> 
> Good point. Thank you Masaru for the suggested fix.
> 
> Attached is a patch to fix the bug found by Masaru. His example now produces:
> 
> regression=# SELECT * FROM connectby('connectby_tree', 'keyid', 
> 'parent_keyid', '11', 0, '-') AS t(keyid int, parent_keyid int, level int, 
> branch text);
>   keyid | parent_keyid | level |  branch
> -------+--------------+-------+----------
>      11 |              |     0 | 11
>      10 |           11 |     1 | 11-10
>     111 |           11 |     1 | 11-111
>       1 |          111 |     2 | 11-111-1
> (4 rows)
> 
> While making the patch I also realized that the "no show branch" form of the 
> function was not going to work very well for recursion detection. Therefore 
> there is now a default branch delimiter ('~') that is used internally, for 
> that case, to enable recursion detection to work. If you need a different 
> delimiter for your specific data, you will have to use the "show branch" form 
> of the function.
> 
> If there are no objections, please apply. Thanks,


 I have no objection to your internally adding strings to detect a recursion.
And I agree with your definition--the default delimiter is a tilde.
Thanks a lot.



Regards,
Masaru Sugawara



Fri, 27 Sep 2002 23:53:04 +0900
Masaru Sugawara <rk73@sea.plala.or.jp>
Re: About connectby()  again

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:
> > The previous patch fixed an infinite recursion bug in 
> > contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
> > seems to occur even if a table has commonplace tree data(see below).
> > 
> > I would think the patch, ancestor check, should be
> > 
> >   if (strstr(branch_delim || branchstr->data || branch_delim,
> >                        branch_delim || current_key || branch_delim))
> > 
> > This is my image, not a real code. However, if branchstr->data includes
> > branch_delim, my image will not be perfect.
> 
> Good point. Thank you Masaru for the suggested fix.
> 
> Attached is a patch to fix the bug found by Masaru. His example now produces:
> 
> regression=# SELECT * FROM connectby('connectby_tree', 'keyid', 
> 'parent_keyid', '11', 0, '-') AS t(keyid int, parent_keyid int, level int, 
> branch text);
>   keyid | parent_keyid | level |  branch
> -------+--------------+-------+----------
>      11 |              |     0 | 11
>      10 |           11 |     1 | 11-10
>     111 |           11 |     1 | 11-111
>       1 |          111 |     2 | 11-111-1
> (4 rows)
> 
> While making the patch I also realized that the "no show branch" form of the 
> function was not going to work very well for recursion detection. Therefore 
> there is now a default branch delimiter ('~') that is used internally, for 
> that case, to enable recursion detection to work. If you need a different 
> delimiter for your specific data, you will have to use the "show branch" form 
> of the function.
> 
> If there are no objections, please apply. Thanks,
> 
> Joe

> Index: contrib/tablefunc/README.tablefunc
> ===================================================================
> RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/README.tablefunc,v
> retrieving revision 1.3
> diff -c -r1.3 README.tablefunc
> *** contrib/tablefunc/README.tablefunc	2 Sep 2002 05:44:04 -0000	1.3
> --- contrib/tablefunc/README.tablefunc	26 Sep 2002 22:57:27 -0000
> ***************
> *** 365,371 ****
>   
>     branch_delim
>   
> !     if optional branch value is desired, this string is used as the delimiter
>   
>   Outputs
>   
> --- 365,373 ----
>   
>     branch_delim
>   
> !     If optional branch value is desired, this string is used as the delimiter.
> !     When not provided, a default value of '~' is used for internal 
> !     recursion detection only, and no "branch" field is returned.
>   
>   Outputs
>   
> ***************
> *** 388,394 ****
>        the level value output
>   
>     3. If the branch field is not desired, omit both the branch_delim input
> !      parameter *and* the branch field in the query column definition
>   
>     4. If the branch field is desired, it must be the forth column in the query
>        column definition, and it must be type TEXT
> --- 390,399 ----
>        the level value output
>   
>     3. If the branch field is not desired, omit both the branch_delim input
> !      parameter *and* the branch field in the query column definition. Note
> !      that when branch_delim is not provided, a default value of '~' is used
> !      for branch_delim for internal recursion detection, even though the branch
> !      field is not returned.
>   
>     4. If the branch field is desired, it must be the forth column in the query
>        column definition, and it must be type TEXT
> Index: contrib/tablefunc/tablefunc.c
> ===================================================================
> RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/tablefunc.c,v
> retrieving revision 1.9
> diff -c -r1.9 tablefunc.c
> *** contrib/tablefunc/tablefunc.c	14 Sep 2002 19:32:54 -0000	1.9
> --- contrib/tablefunc/tablefunc.c	26 Sep 2002 23:09:27 -0000
> ***************
> *** 652,657 ****
> --- 652,660 ----
>   		branch_delim = GET_STR(PG_GETARG_TEXT_P(5));
>   		show_branch = true;
>   	}
> + 	else
> + 		/* default is no show, tilde for the delimiter */
> + 		branch_delim = pstrdup("~");
>   
>   	per_query_ctx = rsinfo->econtext->ecxt_per_query_memory;
>   	oldcontext = MemoryContextSwitchTo(per_query_ctx);
> ***************
> *** 798,807 ****
> --- 801,816 ----
>   		char	   *current_branch;
>   		char	  **values;
>   		StringInfo	branchstr = NULL;
> + 		StringInfo	chk_branchstr = NULL;
> + 		StringInfo	chk_current_key = NULL;
>   
>   		/* start a new branch */
>   		branchstr = makeStringInfo();
>   
> + 		/* need these to check for recursion */
> + 		chk_branchstr = makeStringInfo();
> + 		chk_current_key = makeStringInfo();
> + 
>   		if (show_branch)
>   			values = (char **) palloc(CONNECTBY_NCOLS * sizeof(char *));
>   		else
> ***************
> *** 854,875 ****
>   		{
>   			/* initialize branch for this pass */
>   			appendStringInfo(branchstr, "%s", branch);
>   
>   			/* get the next sql result tuple */
>   			spi_tuple = tuptable->vals[i];
>   
>   			/* get the current key and parent */
>   			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;
>   
> --- 863,886 ----
>   		{
>   			/* initialize branch for this pass */
>   			appendStringInfo(branchstr, "%s", branch);
> + 			appendStringInfo(chk_branchstr, "%s%s%s", branch_delim, branch, branch_delim);
>   
>   			/* get the next sql result tuple */
>   			spi_tuple = tuptable->vals[i];
>   
>   			/* get the current key and parent */
>   			current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
> + 			appendStringInfo(chk_current_key, "%s%s%s", branch_delim, current_key, branch_delim);
>   			current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));
>   
>   			/* get the current level */
>   			sprintf(current_level, "%d", level);
>   
> ! 			/* check to see if this key is also an ancestor */
> ! 			if (strstr(chk_branchstr->data, chk_current_key->data))
> ! 				elog(ERROR, "infinite recursion detected");
> ! 
> ! 			/* OK, extend the branch */
>   			appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
>   			current_branch = branchstr->data;
>   
> ***************
> *** 913,918 ****
> --- 924,935 ----
>   			/* reset branch for next pass */
>   			xpfree(branchstr->data);
>   			initStringInfo(branchstr);
> + 
> + 			xpfree(chk_branchstr->data);
> + 			initStringInfo(chk_branchstr);
> + 
> + 			xpfree(chk_current_key->data);
> + 			initStringInfo(chk_current_key);
>   		}
>   	}
>   

> 
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Don't 'kill -9' the postmaster

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

Sun, 29 Sep 2002 00:21:15 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: About connectby()  again

Patch applied.  Thanks.

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


Joe Conway wrote:
> Masaru Sugawara wrote:
> > The previous patch fixed an infinite recursion bug in 
> > contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
> > seems to occur even if a table has commonplace tree data(see below).
> > 
> > I would think the patch, ancestor check, should be
> > 
> >   if (strstr(branch_delim || branchstr->data || branch_delim,
> >                        branch_delim || current_key || branch_delim))
> > 
> > This is my image, not a real code. However, if branchstr->data includes
> > branch_delim, my image will not be perfect.
> 
> Good point. Thank you Masaru for the suggested fix.
> 
> Attached is a patch to fix the bug found by Masaru. His example now produces:
> 
> regression=# SELECT * FROM connectby('connectby_tree', 'keyid', 
> 'parent_keyid', '11', 0, '-') AS t(keyid int, parent_keyid int, level int, 
> branch text);
>   keyid | parent_keyid | level |  branch
> -------+--------------+-------+----------
>      11 |              |     0 | 11
>      10 |           11 |     1 | 11-10
>     111 |           11 |     1 | 11-111
>       1 |          111 |     2 | 11-111-1
> (4 rows)
> 
> While making the patch I also realized that the "no show branch" form of the 
> function was not going to work very well for recursion detection. Therefore 
> there is now a default branch delimiter ('~') that is used internally, for 
> that case, to enable recursion detection to work. If you need a different 
> delimiter for your specific data, you will have to use the "show branch" form 
> of the function.
> 
> If there are no objections, please apply. Thanks,
> 
> Joe

> Index: contrib/tablefunc/README.tablefunc
> ===================================================================
> RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/README.tablefunc,v
> retrieving revision 1.3
> diff -c -r1.3 README.tablefunc
> *** contrib/tablefunc/README.tablefunc	2 Sep 2002 05:44:04 -0000	1.3
> --- contrib/tablefunc/README.tablefunc	26 Sep 2002 22:57:27 -0000
> ***************
> *** 365,371 ****
>   
>     branch_delim
>   
> !     if optional branch value is desired, this string is used as the delimiter
>   
>   Outputs
>   
> --- 365,373 ----
>   
>     branch_delim
>   
> !     If optional branch value is desired, this string is used as the delimiter.
> !     When not provided, a default value of '~' is used for internal 
> !     recursion detection only, and no "branch" field is returned.
>   
>   Outputs
>   
> ***************
> *** 388,394 ****
>        the level value output
>   
>     3. If the branch field is not desired, omit both the branch_delim input
> !      parameter *and* the branch field in the query column definition
>   
>     4. If the branch field is desired, it must be the forth column in the query
>        column definition, and it must be type TEXT
> --- 390,399 ----
>        the level value output
>   
>     3. If the branch field is not desired, omit both the branch_delim input
> !      parameter *and* the branch field in the query column definition. Note
> !      that when branch_delim is not provided, a default value of '~' is used
> !      for branch_delim for internal recursion detection, even though the branch
> !      field is not returned.
>   
>     4. If the branch field is desired, it must be the forth column in the query
>        column definition, and it must be type TEXT
> Index: contrib/tablefunc/tablefunc.c
> ===================================================================
> RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/tablefunc.c,v
> retrieving revision 1.9
> diff -c -r1.9 tablefunc.c
> *** contrib/tablefunc/tablefunc.c	14 Sep 2002 19:32:54 -0000	1.9
> --- contrib/tablefunc/tablefunc.c	26 Sep 2002 23:09:27 -0000
> ***************
> *** 652,657 ****
> --- 652,660 ----
>   		branch_delim = GET_STR(PG_GETARG_TEXT_P(5));
>   		show_branch = true;
>   	}
> + 	else
> + 		/* default is no show, tilde for the delimiter */
> + 		branch_delim = pstrdup("~");
>   
>   	per_query_ctx = rsinfo->econtext->ecxt_per_query_memory;
>   	oldcontext = MemoryContextSwitchTo(per_query_ctx);
> ***************
> *** 798,807 ****
> --- 801,816 ----
>   		char	   *current_branch;
>   		char	  **values;
>   		StringInfo	branchstr = NULL;
> + 		StringInfo	chk_branchstr = NULL;
> + 		StringInfo	chk_current_key = NULL;
>   
>   		/* start a new branch */
>   		branchstr = makeStringInfo();
>   
> + 		/* need these to check for recursion */
> + 		chk_branchstr = makeStringInfo();
> + 		chk_current_key = makeStringInfo();
> + 
>   		if (show_branch)
>   			values = (char **) palloc(CONNECTBY_NCOLS * sizeof(char *));
>   		else
> ***************
> *** 854,875 ****
>   		{
>   			/* initialize branch for this pass */
>   			appendStringInfo(branchstr, "%s", branch);
>   
>   			/* get the next sql result tuple */
>   			spi_tuple = tuptable->vals[i];
>   
>   			/* get the current key and parent */
>   			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;
>   
> --- 863,886 ----
>   		{
>   			/* initialize branch for this pass */
>   			appendStringInfo(branchstr, "%s", branch);
> + 			appendStringInfo(chk_branchstr, "%s%s%s", branch_delim, branch, branch_delim);
>   
>   			/* get the next sql result tuple */
>   			spi_tuple = tuptable->vals[i];
>   
>   			/* get the current key and parent */
>   			current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
> + 			appendStringInfo(chk_current_key, "%s%s%s", branch_delim, current_key, branch_delim);
>   			current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));
>   
>   			/* get the current level */
>   			sprintf(current_level, "%d", level);
>   
> ! 			/* check to see if this key is also an ancestor */
> ! 			if (strstr(chk_branchstr->data, chk_current_key->data))
> ! 				elog(ERROR, "infinite recursion detected");
> ! 
> ! 			/* OK, extend the branch */
>   			appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
>   			current_branch = branchstr->data;
>   
> ***************
> *** 913,918 ****
> --- 924,935 ----
>   			/* reset branch for next pass */
>   			xpfree(branchstr->data);
>   			initStringInfo(branchstr);
> + 
> + 			xpfree(chk_branchstr->data);
> + 			initStringInfo(chk_branchstr);
> + 
> + 			xpfree(chk_current_key->data);
> + 			initStringInfo(chk_current_key);
>   		}
>   	}
>   

> 
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Don't 'kill -9' the postmaster

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

Thu, 3 Oct 2002 13:11:08 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: About connectby()  again