closures

-- CREATE TABLE nodes_u AS SELECT * FROM diskdb.nodes; -- initial table. _u == unsorted
CREATE TABLE nodes_s ( -- _s == sorted
      id         INTEGER PRIMARY KEY
    , parent_id  INTEGER
    , isdir      INTEGER
    , name       TEXT
    , pathlength INTEGER DEFAULT NULL
);

CREATE TABLE nodes (
      id         INTEGER PRIMARY KEY
    , parent_id  INTEGER
    , isdir      INTEGER
    , name       TEXT
);
CREATE INDEX index_name ON nodes (name);

CREATE TABLE closures (
      ancestor   INTEGER NOT NULL
    , descendant INTEGER NOT NULL
    , pathlength INTEGER NOT NULL
    , PRIMARY KEY (ancestor, descendant)
    , FOREIGN KEY (ancestor)   REFERENCES nodes(id)
    , FOREIGN KEY (descendant) REFERENCES nodes(id)
);
CREATE INDEX index_descendant_ancestor ON closures (descendant, ancestor);

CREATE TRIGGER build_closures
AFTER INSERT ON nodes
FOR EACH ROW
BEGIN
    INSERT INTO closures (ancestor,descendant,pathlength)
    SELECT ancestor, NEW.id, pathlength+1
    FROM Closures
    WHERE descendant = NEW.parent_id

    UNION ALL

    SELECT NEW.id,NEW.id,0;
END;

-- REPEAT until COUNT nodes_u doesn't change
    INSERT INTO nodes_s
    SELECT nodes_u.*, (SELECT COALESCE(MAX(pathlength)+1, 0) FROM nodes_s)
    FROM nodes_u
    WHERE parent_id IN (SELECT id FROM nodes_s) OR parent_id IS NULL;

    DELETE FROM nodes_u
    WHERE id IN (SELECT id FROM nodes_s);
    -- SELECT COUNT(*) FROM nodes_u;


-- BUILD CLOSURES
INSERT INTO nodes
SELECT id, parent_id, isdir, name
FROM nodes_s
ORDER BY pathlength;