Recursively generate JSON tree from hierarchical table in Postgres and jOOQ

Question

I have a hierarchical table in Postgres database, e.g. category. The structure is simple like this:

id	parent_id	name
1	null	A
2	null	B
3	1	A1
4	3	A1a
5	3	A1b
6	2	B1
7	2	B2

What i need to get from this table is recursive deep tree structure like this:

[
  {
    "id": 1,
    "name": "A",
    "children": [
      {
        "id": 3,
        "name": "A1",
        "children": [
          {
            "id": 4,
            "name": "A1a",
            "children": []
          },
          {
            "id": 5,
            "name": "A1b",
            "children": []
          }
        ]
      }
    ]
  },
  {
    "id": 2,
    "name": "B",
    "children": [
      {
        "id": 6,
        "name": "B1",
        "children": []
      },
      {
        "id": 7,
        "name": "B2",
        "children": []
      }
    ]
  },
]

Is it possible with unknown depth using combination of WITH RECURSIVE and json_build_array() or some other solution?

Answer 1

Doing this with SQL

I found an answer to this question in this excellent blog post here, as I was wondering how to generalise over this problem in jOOQ. The solution in the post has a flaw, which I've fixed in my own version from this blog post.

It would be useful if jOOQ could materialise arbitrary recursive object trees in a generic way: https://github.com/jOOQ/jOOQ/issues/12341

In the meantime, use this SQL statement, which was inspired by the above blog post, with a few modifications. Translate to jOOQ if you must, though you might as well store this as a view:

WITH RECURSIVE
  d1 (id, parent_id, name) as (
    values
      (1, null, 'A'),
      (2, null, 'B'),
      (3,    1, 'A1'),
      (4,    3, 'A1a'),
      (5,    3, 'A1b'),
      (6,    2, 'B1'),
      (7,    2, 'B2')
  ),
  d2 AS (
    SELECT d1.*, 0 AS level
    FROM d1
    WHERE parent_id IS NULL
    UNION ALL
    SELECT d1.*, d2.level + 1
    FROM d1
    JOIN d2 ON d2.id = d1.parent_id
  ),
  d3 AS (
    SELECT d2.*, null::jsonb children
    FROM d2
    WHERE level = (SELECT max(level) FROM d2)
    UNION (
      SELECT
        (branch_parent).*, 
        jsonb_strip_nulls(
          jsonb_agg(branch_child - 'parent_id' - 'level'
            ORDER BY branch_child->>'name'
          ) FILTER (
            WHERE branch_child->>'parent_id' = (branch_parent).id::text
          )
        )
      FROM (
        SELECT
          branch_parent,
          to_jsonb(branch_child) AS branch_child
        FROM d2 branch_parent
        JOIN d3 branch_child ON branch_child.level = branch_parent.level + 1
      ) branch
      GROUP BY branch_parent
    )
  )
SELECT
  jsonb_pretty(jsonb_agg(to_jsonb(d3) - 'parent_id' - 'level')) AS tree
FROM d3
WHERE level = 0;

dbfiddle. Again, read the linked blog post for an explanation of how this works

Doing this in the client

Perhaps, you don't really have to materialise your hierarchy in SQL, but could do it in the client. jOOQ 3.19 will ship with a new Collectors::intoHierarchy collector (see #12341), which can do this for you:

record Category(int id, String name, List<Category> children) {}

// Optionally, make this a recursive query using WITH RECURSIVE or
// CONNECT BY, if you need to start from some node and then fetch
// only its children
List<Category> roots =
ctx.select(CATEGORY.ID, CATEGORY.PARENT_ID, CATEGORY.NAME)
   .from(CATEGORY)
   .orderBy(CATEGORY.ID)
   .collect(intoHierarchy(
       r -> r.value1(),
       r -> r.value2(),
       (r, l) -> new Category(r.value1(), r.value3(), l)
   ));

The Collector is just this:

public static final <K, E, R extends Record> Collector<R, ?, List<E>> 
intoHierarchy(
    Function<? super R, ? extends K> keyMapper,
    Function<? super R, ? extends K> parentKeyMapper,
    BiFunction<? super R, ? super List<E>, ? extends E> recordMapper
) {
    return intoHierarchy(
        keyMapper, parentKeyMapper, recordMapper, ArrayList::new
    );
}


public static final <K, E, C extends Collection<E>, R extends Record> 
Collector<R, ?, List<E>> intoHierarchy(
    Function<? super R, ? extends K> keyMapper,
    Function<? super R, ? extends K> parentKeyMapper,
    BiFunction<? super R, ? super C, ? extends E> recordMapper,
    Supplier<? extends C> collectionFactory
) {
    record Tuple3<T1, T2, T3>(T1 t1, T2 t2, T3 t3) {}

    return collectingAndThen(
        intoMap(keyMapper, r -> {
            C e = collectionFactory.get();
            return new Tuple3<R, C, E>(r, e, recordMapper.apply(r, e));
        }),
        m -> {
            List<E> r = new ArrayList<>();

            m.forEach((k, v) -> {
                K parent = parentKeyMapper.apply(v.t1());
                E child = v.t3();

                if (m.containsKey(parent))
                    m.get(parent).t2().add(child);
                else
                    r.add(child);
            });

            return r;
        }
    );
}

Now, you can use any means of turning this tree structure into a JSON document, e.g. using Jackson.