public
Created

Recursive tree browsing in Postgres SQL

  • Download Gist
create_table.sql
SQL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
CREATE TABLE node (name varchar PRIMARY KEY, is_child_of varchar REFERENCES node (name), some_int integer NOT NULL);
CREATE INDEX node_is_child_of_idx ON node (is_child_of);
 
-- Fill the table with nice big random tree
WITH RECURSIVE
path_node AS (
SELECT
md5(chr(CAST(floor(random() * 223) AS integer) + 32) || random()) AS name,
NULL AS is_child_of,
0 AS some_int,
1 AS child_no
UNION ALL
SELECT
md5(chr(CAST(floor(random() * 223) AS integer) + 32) || random()) AS name,
name AS is_child_of,
some_int + 1 AS some_int,
generate_series(1, CAST(floor(random() * 5) AS integer)) AS child_no
FROM
path_node
WHERE
some_int <= 15
)
INSERT INTO node SELECT name, is_child_of, some_int FROM path_node;
get_ancestors_of.sql
SQL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
CREATE OR REPLACE FUNCTION get_ancestors_of (varchar) RETURNS SETOF node AS $_$
WITH RECURSIVE
node_path AS (
SELECT
*
FROM
node
WHERE
name = $1
UNION ALL
SELECT
n.*
FROM
node n
JOIN node_path np ON n.name = np.is_child_of
WHERE
np.is_child_of IS NOT NULL
)
SELECT * FROM node_path;
$_$ LANGUAGE sql
get_children_of.sql
SQL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
CREATE OR REPLACE FUNCTION get_children_of(varchar) RETURNS SETOF node AS $_$
WITH RECURSIVE
node_path (name, is_child_of, some_int) AS (
SELECT
*
FROM
node
WHERE
name = $1
UNION ALL
SELECT
n.*
FROM
node n
JOIN node_path np ON n.is_child_of = np.name
)
SELECT * FROM node_path;
$_$ LANGUAGE SQL;
get_leafs.sql
SQL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
CREATE OR REPLACE FUNCTION get_leafs() RETURNS SETOF node AS $_$
WITH
child_count (name, children_count) AS (
SELECT
n.name,
count(child.name)
FROM
node n
LEFT JOIN node child ON n.name = child.is_child_of
GROUP BY
n.name
)
SELECT
n.*
FROM
node n
NATURAL JOIN child_count cc
WHERE
cc.children_count = 0;
$_$ LANGUAGE sql

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.