CODEWITHSUNDEEP
jsonpostgresqlrecursionadjacency-list
ChrisArmstrong
ChrisArmstrong

Reputation: 2521

Returning adjacency list as nested JSON in Postgres

Given the simplest base case of a two column Postgres table (id, parent_id), is there a way to query an id and get back all of the children as a nested json structure like the following?

{
    "id": 1,
    "children": [{
        "id": 2,
        "children": [{
            "id": 3,
            "children": []
        }]
    }]
}

I understand how to recurse through the table, but I can't piece together how to use any of the psql json functions to return a result like above. Maybe I should just be using my language of choice to convert in postprocessing?

SQLFiddle of current progress.

Upvotes: 2

Views: 582

Answers (2)

Notes
Notes

Reputation: 1

This will only return the primary path. If you add multiple children at any level it will discard those. Try with:

CREATE TABLE foo (
id INT PRIMARY KEY,
parent_id INT);

insert into foo values (1, null);
insert into foo values (2, 1);
insert into foo values (3, 2);
insert into foo values (4, 2);
insert into foo values (5, 4);
insert into foo values (6, 1);
insert into foo values (7, 8);
insert into foo values (8, 5);
insert into foo values (9, 2);
insert into foo values (10, 9);

returns

[{"id": 1, "children": [{"id": 2, "children": [{"id": 4, "children": [{"id": 5, "children": [{"id": 8, "children": [{"id": 7, "children": []}]}]}]}]}]}]

Upvotes: 0

Ezequiel Tolnay
Ezequiel Tolnay

Reputation: 4582

Freaking difficult, took me hours to solve :-P

CREATE TABLE foo (
id INT PRIMARY KEY,
parent_id INT);

insert into foo values (1, null);
insert into foo values (2, 1);
insert into foo values (3, 2);

WITH RECURSIVE 
    tree AS (
    SELECT 1 AS round, id, parent_id, ARRAY(SELECT id FROM foo WHERE parent_id = f.id) AS children
    FROM foo f
    WHERE id = 1
    UNION ALL
    SELECT round+1, f.id, f.parent_id, ARRAY(SELECT id FROM foo WHERE parent_id = f.id) AS children
    FROM tree t
    JOIN foo f ON (f.id = ANY(t.children))
    ),
    rev AS (
    SELECT r.round-1 AS round,
            to_jsonb(ARRAY(
                    SELECT a
                    FROM (
                        SELECT f.parent_id AS id, json_agg(jsonb_build_object('id', f.id, 'children', '{}'::text[])) AS children
                        FROM tree t
                        JOIN foo f ON (f.id = t.id)
                        WHERE t.round = r.round
                        GROUP BY f.parent_id
                        ) a
                    )) AS list
    FROM (SELECT MAX(round)::int AS round FROM tree) r
    UNION ALL
    SELECT r.round-1,
            to_jsonb(ARRAY(
                    SELECT a
                    FROM (
                        SELECT f.parent_id AS id, json_agg(jsonb_build_object('id', f.id, 'children', t->'children')) AS children
                        FROM jsonb_array_elements(list) t
                        JOIN foo f ON (f.id = (t->>'id')::int)
                        GROUP BY f.parent_id
                        ) a
                    )) AS list
    FROM rev r
    WHERE round > 1
    )
SELECT list as nested_json_tree
FROM rev
WHERE round = 1

The complexity lies in the requirement to build first the tree (top down), and then build the object from the tree, bottom-up. Recursive bottom-up is tricky due to limitation in recursive queries, such as the recursive alias within the UNION ALL section not being able to being grouped, nor included in a subquery. I solved this by doing the unwrapping via reversed rounds.

This query should properly build complex trees, with multiple children per node, and any number of nesting levels.

Upvotes: 3

Related Questions