> Now I'm testing connectby() in the /contrib/tablefunc in 7.3b1, which would

bmomjian · bmomjian · commit f490dbe59460 · 2002-09-12T00:19:44.000Z
&gt; be a useful function for many users.   However, I found the fact that
&gt; if connectby_tree has the following data, connectby() tries to search the end
&gt; of roots without knowing that the relations are infinite(-5-9-10-11-9-10-11-)
.
&gt; I hope connectby() supports a check routine to find infinite relations.
&gt;
&gt;
&gt; CREATE TABLE connectby_tree(keyid int, parent_keyid int);
&gt; INSERT INTO connectby_tree VALUES(1,NULL);
&gt; INSERT INTO connectby_tree VALUES(2,1);
&gt; INSERT INTO connectby_tree VALUES(3,1);
&gt; INSERT INTO connectby_tree VALUES(4,2);
&gt; INSERT INTO connectby_tree VALUES(5,2);
&gt; INSERT INTO connectby_tree VALUES(6,4);
&gt; INSERT INTO connectby_tree VALUES(7,3);
&gt; INSERT INTO connectby_tree VALUES(8,6);
&gt; INSERT INTO connectby_tree VALUES(9,5);
&gt;
&gt; INSERT INTO connectby_tree VALUES(10,9);
&gt; INSERT INTO connectby_tree VALUES(11,10);
&gt; INSERT INTO connectby_tree VALUES(9,11);    &lt;-- infinite
&gt;

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

Joe Conway
diff --git a/contrib/tablefunc/tablefunc.c b/contrib/tablefunc/tablefunc.c
@@ -801,6 +801,10 @@ build_tuplestore_recursively(char *key_fld,
 		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,14 +856,8 @@ build_tuplestore_recursively(char *key_fld,
 
 		for (i = 0; i < proc; i++)
 		{
-			StringInfo	branchstr = NULL;
-
-			/* start a new branch */
-			if (show_branch)
-			{
-				branchstr = makeStringInfo();
-				appendStringInfo(branchstr, "%s", branch);
-			}
+			/* initialize branch for this pass */
+			appendStringInfo(branchstr, "%s", branch);
 
 			/* get the next sql result tuple */
 			spi_tuple = tuptable->vals[i];
@@ -868,17 +866,16 @@ build_tuplestore_recursively(char *key_fld,
 			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 */
-			if (show_branch)
-			{
-				appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
-				current_branch = branchstr->data;
-			}
-			else
-				current_branch = NULL;
+			appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
+			current_branch = branchstr->data;
 
 			/* build a tuple */
 			values[0] = pstrdup(current_key);
@@ -916,6 +913,10 @@ build_tuplestore_recursively(char *key_fld,
 													per_query_ctx,
 													attinmeta,
 													tupstore);
+
+			/* reset branch for next pass */
+			xpfree(branchstr->data);
+			initStringInfo(branchstr);
 		}
 	}
 
