Re: [HACKERS] About connectby() - Mailing list pgsql-patches

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);
          }
      }