Skip to content

Instantly share code, notes, and snippets.

@chanmix51
Created August 1, 2012 09:12
Show Gist options
  • Save chanmix51/3225313 to your computer and use it in GitHub Desktop.
Save chanmix51/3225313 to your computer and use it in GitHub Desktop.
Recursive tree browsing in Postgres SQL
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;
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
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;
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment