Обсуждение: PL/pgSQL graph enumeration function hangs

I have a table of organizations that has a many-to-many relationship
with itself via another table called relationships. The relationships
table has a serial id primary key and parent_id and child_id integer
fields. The organizations table has a couple thousand records and the
maximum depth is around 7 or 8 levels. The graph is directed and is (or
will be) reconvergent.

Using pseudocode from Celko's "SQL for Smarties" book, I wrote the
following function that builds a path enumeration table. I hope to
trigger this function on the rare occasions that the organizations table
is updated. But when I run this function, it hangs.

Can anyone spot the problem? If not, is there a better solution?

I am returning a trigger. There are no arguments. I'm using VOLATILE,
CALLED ON NULL INPUT, and SECURITY INVOKER.

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

DECLARE
   oldsize integer NOT NULL;
   newsize integer NOT NULL;

BEGIN

   -- recreate the empty path_enum table
   DROP TABLE IF EXISTS organizations_path_enum;
   CREATE TABLE organizations_path_enum (
       parent_id integer NOT NULL,
       child_id integer NOT NULL,
       depth integer NOT NULL,
       CONSTRAINT depth_not_negative CHECK( depth >= 0 )
   );
   CREATE INDEX ope_parent_idx ON organizations_path_enum(parent_id);
   CREATE INDEX ope_child_idx ON organizations_path_enum(child_id);
   CREATE INDEX ope_parent_child_idx ON
organizations_path_enum(parent_id, child_id);
   CREATE INDEX ope_child_parent_idx ON
organizations_path_enum(child_id, parent_id);
   CREATE UNIQUE INDEX ope_uniq_row_idx ON organizations_path_enum
(parent_id, child_id, depth);

   -- load path of node to itself
   INSERT INTO organizations_path_enum
       SELECT DISTINCT child_id, child_id, 0 FROM relationships;

   -- load paths of length = 1 into table
   INSERT INTO organizations_path_enum
       SELECT DISTINCT parent_id, child_id, 1 FROM relationships;

   -- insert rows only while table grows
   oldsize := 0;
   SELECT COUNT(*) INTO newsize FROM organizations_path_enum;

   WHILE oldsize < newsize LOOP
       INSERT INTO organizations_path_enum
           SELECT o1.parent_id, r1.child_id, (o1.depth + 1)
           FROM organizations_path_enum o1, relationships r1
               -- advance existing paths by one level
           WHERE EXISTS (SELECT * FROM organizations_path_enum AS o2
WHERE r1.parent_id = o2.child_id)
               -- insert only new rows into the table
           AND NOT EXISTS (SELECT * FROM organizations_path_enum AS o3
WHERE o1.parent_id = o3.parent_id AND r1.child_id = o3.child_id);

       oldsize := newsize;
       SELECT COUNT(*) INTO newsize FROM organizations_path_enum;
   END LOOP;
END;

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

Thanks!

Charles Munat
Seattle

"Charles F. Munat" <chas@munat.com> writes:
> Using pseudocode from Celko's "SQL for Smarties" book, I wrote the
> following function that builds a path enumeration table. I hope to
> trigger this function on the rare occasions that the organizations table
> is updated. But when I run this function, it hangs.

I think there might be something wrong with this query:

>        INSERT INTO organizations_path_enum
>            SELECT o1.parent_id, r1.child_id, (o1.depth + 1)
>            FROM organizations_path_enum o1, relationships r1
>                -- advance existing paths by one level
>            WHERE EXISTS (SELECT * FROM organizations_path_enum AS o2
> WHERE r1.parent_id = o2.child_id)
>                -- insert only new rows into the table
>            AND NOT EXISTS (SELECT * FROM organizations_path_enum AS o3
> WHERE o1.parent_id = o3.parent_id AND r1.child_id = o3.child_id);

I'm not totally clear on what this is supposed to accomplish, but
it seems like there should be some join clause between o1 and r1.

            regards, tom lane

Thanks, but the join clause is there, it's just buried in the subqueries.

If there is a problem, it is probably that the loop never ends.

Or it could be that the answer is exponential, and I just have too many
rows in the source table and too deep a graph.

I figured out how to do it in the application with one call to the
database and a simple recursive method in a class, though, so I'm not
going to use a stored function in the DB.

Thanks again for responding.

Chas.

Tom Lane wrote:
> "Charles F. Munat" <chas@munat.com> writes:
>> Using pseudocode from Celko's "SQL for Smarties" book, I wrote the
>> following function that builds a path enumeration table. I hope to
>> trigger this function on the rare occasions that the organizations table
>> is updated. But when I run this function, it hangs.
>
> I think there might be something wrong with this query:
>
>>        INSERT INTO organizations_path_enum
>>            SELECT o1.parent_id, r1.child_id, (o1.depth + 1)
>>            FROM organizations_path_enum o1, relationships r1
>>                -- advance existing paths by one level
>>            WHERE EXISTS (SELECT * FROM organizations_path_enum AS o2
>> WHERE r1.parent_id = o2.child_id)
>>                -- insert only new rows into the table
>>            AND NOT EXISTS (SELECT * FROM organizations_path_enum AS o3
>> WHERE o1.parent_id = o3.parent_id AND r1.child_id = o3.child_id);
>
> I'm not totally clear on what this is supposed to accomplish, but
> it seems like there should be some join clause between o1 and r1.
>
>             regards, tom lane

Charles F. Munat wrote:
> Thanks, but the join clause is there, it's just buried in the subqueries.
>
> If there is a problem, it is probably that the loop never ends.
>
> Or it could be that the answer is exponential, and I just have too many
> rows in the source table and too deep a graph.
>
> I figured out how to do it in the application with one call to the
> database and a simple recursive method in a class, though, so I'm not
> going to use a stored function in the DB.

If you have figured it out this way you can even use one of the
PL/languages to implement it within the database :-)

Cheers
Tino