Skip to content

Instantly share code, notes, and snippets.

@wellic

wellic/00-setup.sql

Forked from apneadiving/00-setup.sql
Created October 7, 2021 09:39
Show Gist options
  • Save wellic/90956017b5a7f3a552f27654a4846613 to your computer and use it in GitHub Desktop.
Save wellic/90956017b5a7f3a552f27654a4846613 to your computer and use it in GitHub Desktop.
Download ZIP
Tree structure query with PostgreSQL
Raw
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);
Raw
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;
Raw
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;
Raw
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
Raw
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;
Raw
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;
Raw
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
Raw
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment