Fetching all nodes of a directed graph by an id of any node Task: Rowset of all reachable(in any direction) nodes from any node in a graph. In other words I need to extract all nodes of a particular graph from a table in the database where graph specified by an id of any one graph node. The final goal is a map in the app.

Table structure of DocumentDependency is simple as:

descendant_id | predecessor_id 
-------------------------------
     2857     |      2856
     2858     |      2856
     2859     |      2856
     2859     |      2857
     2860     |      2859
     2861     |      2859


Finally I came up with CTE:

WITH RECURSIVE DocumentGraph AS
(
    SELECT
        CASE WHEN predecessor_id = 2858 THEN descendant_id ELSE predecessor_id END AS anchor_id,
        ARRAY[ROW(predecessor_id, descendant_id)] path,
        1 depth

    FROM
        DocumentDependency

    WHERE
        2858 in (descendant_id, predecessor_id)

    UNION ALL

    SELECT
        CASE WHEN DocumentDependency.predecessor_id = DocumentGraph.anchor_id THEN DocumentDependency.descendant_id ELSE DocumentDependency.predecessor_id END,
        path || ROW(DocumentDependency.predecessor_id, DocumentDependency.descendant_id) path,
        depth + 1

    FROM
        DocumentGraph

    JOIN DocumentDependency ON
        DocumentGraph.anchor_id in (DocumentDependency.predecessor_id, DocumentDependency.descendant_id)
        AND
        ROW(DocumentDependency.predecessor_id, DocumentDependency.descendant_id) &lt;&gt; ALL(path)
)


There are a lot discussions about directed graphs and this is sort of a compilation from stack* and one useful book1, but I'm experiencing an overdose and what I need is criticism.


Maybe this is generally an inappropriate approach? =)
Lightweight? (What if DocumentDependency will have 500k rows?)
Portability? (for now I'm using PostgreSQL12)
Simplicity? (I'm under custom ORM and need to extend for ROWS/ARRAYS/CTE support but probably there is a way to avoid using arrays?)




1Joe Celko's Trees and Hierarchies in SQL For Smarties (highly recommended, btw ;)
I am not well qualified to answer this, as I know nothing of PostgreSQL or the RECURSIVE extension you are using, so unfortunately I cannot very well comment on your solution.

However perhaps it can be tackled with (relatively!) standard SQL. Let's define a temporary table 

CREATE TABLE #Temp ( id int, status int )


A status of 1 will indicate the node is reachable, but it has not yet been processed, a status of 2 indicates the node is reachable, and all immediate descendants have been added. We initialise by inserting the starting node ( I think in your example it is 2858 ).

INSERT INTO #temp ( id, status ) VALUES ( 2858, 1 )


Now we can set up a loop to insert all the reachable nodes:

DECLARE @x int 
WHILE 1 = 1
BEGIN
  SELECT @x = -1 -- Some value that is not a valid node id
  SELECT @x = id FROM #Temp WHERE Status = 1
  IF @x = -1 BREAK -- All reachable nodes processed.

  INSERT INTO #temp( id, status ) 
  SELECT descendant_id, 1 
  FROM DocumentDependency WHERE predecessor_id = @x
  AND descendant_id NOT in ( SELECT id FROM #Temp )

  UPDATE #temp SET status = 2 WHERE id = @x
END


When the loop terminates, #Temp should contain all the reachable node ids. Provided suitable indexes are defined, I think this should be reasonably efficient. As a variation, you could perhaps process multiple nodes with status 1 on each iteration of the loop, I will leave that as an exercise ( you may need an extra status value to differentiate between nodes that have just been added and nodes that are being processed ).