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

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