Getting list of all children in “adjacency list” tree structure

So, you have a table which looks like this:

# \d test
                           Table "public.test"
  Column   |  Type   |                     Modifiers
-----------+---------+---------------------------------------------------
 id        | integer | not null default nextval('test_id_seq'::regclass)
 parent_id | integer |
 x         | text    |
Indexes:
    "test_pkey" PRIMARY KEY, btree (id)
Foreign-key constraints:
    "test_parent_id_fkey" FOREIGN KEY (parent_id) REFERENCES test(id)
Referenced by:
  "test_parent_id_fkey" IN test FOREIGN KEY (parent_id) REFERENCES test(id)

And you would like to easily get all children starting from given node?

You can use recursive function, but instead we can use loop. What's pretty nifty is that we can do it in such a way that the total number of queries issued to database will be dependent on number of levels below given node, and not number of children!.

To make it as simple as possible I decided to use arrays to store the information in function, and return out of it:

CREATE OR REPLACE FUNCTION get_all_children_array(use_parent INT4) RETURNS INT4[] AS $$
DECLARE
    process_parents INT4[] := ARRAY[ use_parent ];
    children INT4[] := '{}';
    new_children INT4[];
BEGIN
    WHILE ( array_upper( process_parents, 1 ) IS NOT NULL ) LOOP
        new_children := ARRAY( SELECT id FROM test WHERE parent_id = ANY( process_parents ) AND id <> ALL( children ) );
        children := children || new_children;
        process_parents := new_children;
    END LOOP;
    RETURN children;
END;
$$ LANGUAGE plpgsql;

Side note – the function has been edited after I posted this information. I added “AND id <> ALL( children )".

This condition will make the function work correctly in case of loops in the tree.

Now, we can put some data in test table:

# SELECT * FROM test;
 id | parent_id | x
----+-----------+---
  1 |    [NULL] | a
  2 |    [NULL] | b
  3 |         1 | c
  4 |         1 | d
  5 |         3 | e
  6 |         3 | f
  7 |         2 | g
  8 |         7 | h
  9 |         5 | i
(9 ROWS)

and test the function:

First, sanity check for node with no children:

# SELECT get_all_children_array(9);
 get_all_children_array
------------------------
 {}
(1 ROW)

Looks good. Now for more demanding tests:

# SELECT get_all_children_array(5);
 get_all_children_array
------------------------
 {9}
(1 ROW)
 
# SELECT get_all_children_array(1);
 get_all_children_array
------------------------
 {3,4,5,6,9}
(1 ROW)

Hope you'll find it useful.

4 thoughts on “Getting list of all children in “adjacency list” tree structure”

Hey Depesz,
I feel honoured to have a blogpost dedicated to my problem. This is indeed an imporivement over recursion where you execute a query for each child element instead of a query for each level. Many thanks.

looks like a candidate for WITH RECURSIVE… to me 😉

I am waiting for 8.4 and Common Table Expressions. I’ve used them in SQLServer for a while, and DB2 for years. A Much, much more logical way to answer the question. Let’s go 8.4

for gregj:

WITH RECURSIVE struct AS (
SELECT t.* FROM test t WHERE parent_id = 1
UNION ALL
SELECT t.* FROM test t, struct s WHERE s.id = t.parent_id
)
SELECT ARRAY(SELECT id FROM struct) AS ID;

Comments are closed.