Thread: 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