Tree structure query with PostgreSQL

00-setup.sql

-- Create tables
CREATE TABLE groups (id serial NOT NULL, name character varying NOT NULL);
CREATE TABLE network_group_members (pid integer, cid integer NOT NULL);

-- Insert the groups
INSERT INTO groups (name) VALUES ('GROUP 1'),('GROUP 2'),('GROUP 3'),('GROUP 4'),('GROUP 5'),('GROUP 6'),('GROUP 7'),('GROUP 8'),('GROUP 9'),('GROUP 10'),('GROUP 11'),('GROUP 12'),('GROUP 13');
-- Build the "Network"
INSERT INTO network_group_members(pid,cid) VALUES (1,2),(1,3),(1,4),(2,5),(5,6),(5,7),(7,8),(3,9),(4,10),(4,11),(11,12),(12,13);

01-get-tree-from-root-readable.sql

WITH RECURSIVE nodes(pid, parentName, cid, childName, path, depth) AS (
	SELECT
		r."pid", p1."name",
		r."cid", p2."name",
		ARRAY[r."pid"], 
		1
	FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2
	  WHERE 
	    -- change r.pid = 1 to the root node id that you want to query the tree from
	    r."pid" = 1 AND 
	    p1."id" = r."pid" 
	    AND p2."id" = r."cid"
	UNION ALL
  	SELECT
  		r."pid", 
  		p1."name",
  		r."cid", 
  		p2."name",
  		path || r."pid", 
  		nd.depth + 1
  	FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2, nodes AS nd
  	  WHERE 
  	    r."pid" = nd.cid AND 
  	    p1."id" = r."pid" AND 
  	    p2."id" = r."cid" 
  	    -- To query all descendant nodes within a specific depth level, uncomment the next line
  	    -- AND depth < 2
)
SELECT * FROM nodes;

01-get-tree-from-root-single-line.sql

WITH RECURSIVE nodes(pid, parentName, cid, childName, path, depth) AS ( SELECT r."pid", p1."name", r."cid", p2."name", ARRAY[r."pid"], 1 FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2 WHERE r."pid" = 1 AND p1."id" = r."pid" AND p2."id" = r."cid" UNION ALL SELECT r."pid", p1."name", r."cid", p2."name", path || r."pid", nd.depth + 1 FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2, nodes AS nd WHERE r."pid" = nd.cid AND p1."id" = r."pid" AND p2."id" = r."cid") SELECT * FROM nodes;

02-tree-output-root.txt

#############################################################################################
# Output is the entire tree, using Group 1 (record #1) as the root node of the entire tree. #
#############################################################################################
 pid | parentname | cid | childname |    path     | depth 
-----+------------+-----+-----------+-------------+-------
   1 | GROUP 1    |   2 | GROUP 2   | {1}         |     1
   1 | GROUP 1    |   3 | GROUP 3   | {1}         |     1
   1 | GROUP 1    |   4 | GROUP 4   | {1}         |     1
   2 | GROUP 2    |   5 | GROUP 5   | {1,2}       |     2
   3 | GROUP 3    |   9 | GROUP 9   | {1,3}       |     2
   4 | GROUP 4    |  11 | GROUP 11  | {1,4}       |     2
   4 | GROUP 4    |  10 | GROUP 10  | {1,4}       |     2
   5 | GROUP 5    |   6 | GROUP 6   | {1,2,5}     |     3
   5 | GROUP 5    |   7 | GROUP 7   | {1,2,5}     |     3
  11 | GROUP 11   |  12 | GROUP 12  | {1,4,11}    |     3
   7 | GROUP 7    |   8 | GROUP 8   | {1,2,5,7}   |     4
  12 | GROUP 12   |  13 | GROUP 13  | {1,4,11,12} |     4

03-get-tree-from-node5-readable.sql

WITH RECURSIVE nodes(pid, parentName, cid, childName, path, depth) AS (
	SELECT
		r."pid", p1."name",
		r."cid", p2."name",
		ARRAY[r."pid"], 
		1
	FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2
	  WHERE 
	    r."pid" = 5 AND 
	    p1."id" = r."pid" 
	    AND p2."id" = r."cid"
	UNION ALL
  	SELECT
  		r."pid", 
  		p1."name",
  		r."cid", 
  		p2."name",
  		path || r."pid", 
  		nd.depth + 1
  	FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2, nodes AS nd
  	  WHERE 
  	    r."pid" = nd.cid AND 
  	    p1."id" = r."pid" AND 
  	    p2."id" = r."cid"
)
SELECT * FROM nodes;

03-get-tree-from-node5-single-line.sql

WITH RECURSIVE nodes(pid, parentName, cid, childName, path, depth) AS ( SELECT r."pid", p1."name", r."cid", p2."name", ARRAY[r."pid"], 1 FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2 WHERE r."pid" = 5 AND p1."id" = r."pid" AND p2."id" = r."cid" UNION ALL SELECT r."pid", p1."name", r."cid", p2."name", path || r."pid", nd.depth + 1 FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2, nodes AS nd WHERE r."pid" = nd.cid AND p1."id" = r."pid" AND p2."id" = r."cid") SELECT * FROM nodes;

04-tree-output-node5.txt

#############################################################################################
# Output is the entire tree, using Group 5 (record #5) as the root node.                    #
#############################################################################################
 pid | parentname | cid | childname | path  | depth 
-----+------------+-----+-----------+-------+-------
   5 | GROUP 5    |   6 | GROUP 6   | {5}   |     1
   5 | GROUP 5    |   7 | GROUP 7   | {5}   |     1
   7 | GROUP 7    |   8 | GROUP 8   | {5,7} |     2

05-explain-node1-root.txt

#############################################################################################
# Explain of output of entire tree, using node 1 as the root.                               #
#############################################################################################
EXPLAIN(WITH RECURSIVE nodes(pid, parentName, cid, childName, path, depth) AS ( SELECT r."pid", p1."name", r."cid", p2."name", ARRAY[r."pid"], 1 FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2 WHERE r."pid" = 1 AND p1."id" = r."pid" AND p2."id" = r."cid" UNION ALL SELECT r."pid", p1."name", r."cid", p2."name", path || r."pid", nd.depth + 1 FROM "network_group_members" AS r, "groups" AS p1, "groups" AS p2, nodes AS nd WHERE r."pid" = nd.cid AND p1."id" = r."pid" AND p2."id" = r."cid") SELECT * FROM nodes);
                                                    QUERY PLAN                                                     
-------------------------------------------------------------------------------------------------------------------
 CTE Scan on nodes  (cost=679259.53..1007884.05 rows=16431226 width=108)
   CTE nodes
     ->  Recursive Union  (cost=36.89..679259.53 rows=16431226 width=108)
           ->  Nested Loop  (cost=36.89..94.97 rows=406 width=72)
                 ->  Hash Join  (cost=36.89..64.48 rows=68 width=40)
                       Hash Cond: (p2.id = r.cid)
                       ->  Seq Scan on groups p2  (cost=0.00..22.30 rows=1230 width=36)
                       ->  Hash  (cost=36.75..36.75 rows=11 width=8)
                             ->  Seq Scan on network_group_members r  (cost=0.00..36.75 rows=11 width=8)
                                   Filter: (pid = 1)
                 ->  Materialize  (cost=0.00..25.41 rows=6 width=36)
                       ->  Seq Scan on groups p1  (cost=0.00..25.38 rows=6 width=36)
                             Filter: (id = 1)
           ->  Merge Join  (cost=1749.21..35054.00 rows=1643082 width=108)
                 Merge Cond: (nd.cid = r_1.pid)
                 ->  Merge Join  (cost=409.97..790.65 rows=24969 width=76)
                       Merge Cond: (p1_1.id = nd.cid)
                       ->  Sort  (cost=85.43..88.50 rows=1230 width=36)
                             Sort Key: p1_1.id
                             ->  Seq Scan on groups p1_1  (cost=0.00..22.30 rows=1230 width=36)
                       ->  Sort  (cost=324.54..334.69 rows=4060 width=40)
                             Sort Key: nd.cid
                             ->  WorkTable Scan on nodes nd  (cost=0.00..81.20 rows=4060 width=40)
                 ->  Sort  (cost=1339.24..1372.15 rows=13161 width=40)
                       Sort Key: r_1.pid
                       ->  Merge Join  (cost=235.20..438.77 rows=13161 width=40)
                             Merge Cond: (p2_1.id = r_1.cid)
                             ->  Sort  (cost=85.43..88.50 rows=1230 width=36)
                                   Sort Key: p2_1.id
                                   ->  Seq Scan on groups p2_1  (cost=0.00..22.30 rows=1230 width=36)
                             ->  Sort  (cost=149.78..155.13 rows=2140 width=8)
                                   Sort Key: r_1.cid
                                   ->  Seq Scan on network_group_members r_1  (cost=0.00..31.40 rows=2140 width=8)
(33 rows)

Expensive, but it works.