Search Postgresql Archives

PL/pgSQL graph enumeration function hangs

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Index of Archives]     [Postgresql Jobs]     [Postgresql Admin]     [Postgresql Performance]     [Linux Clusters]     [PHP Home]     [PHP on Windows]     [Kernel Newbies]     [PHP Classes]     [PHP Books]     [PHP Databases]     [Postgresql & PHP]     [Yosemite]
  Powered by Linux