PL/pgSQL graph enumeration function hangs - Mailing list pgsql-general

From Charles F. Munat
Subject PL/pgSQL graph enumeration function hangs
Date
Msg-id 48482B3F.3020406@munat.com
Whole thread Raw
List pgsql-general
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

pgsql-general by date:

Previous
From: "Brent Wood"
Date:
Subject: Re: Temporary Tables and Web Application
Next
From: Gary Fu
Date:
Subject: Re: how to clean up temporary schemas (how to sync the system table with pg_dump)