0

So I want to limit tree depth traversal (as the simplest recursion killer tool). Example code that turns normalized records into tree:

CREATE TABLE items (
  item_id     serial PRIMARY KEY,
  title text
);
CREATE TABLE joins (
  id          serial PRIMARY KEY,
  item_id     int,
  child_id    int
);
INSERT INTO items (item_id,title) VALUES
  (1,'PARENT'),
  (2,'LEVEL 2'),
  (3,'LEVEL 3.1'),
  (4,'LEVEL 4.1'),
  (5,'LEVEL 4.2'),
  (6,'LEVEL 3.2');
INSERT INTO joins (item_id, child_id) VALUES
  (1,2),
  (2,3),
  (3,4),
  (3,5),
  (2,6);

WITH RECURSIVE t(item_id, json) AS (
        SELECT item_id, to_jsonb(items)
        FROM items
        WHERE NOT EXISTS (
                SELECT 1
                FROM joins
                WHERE items.item_id = joins.item_id
        )
        UNION ALL
        SELECT parent.item_id, to_jsonb(parent) || jsonb_build_object( 'children', t.json )
        FROM t
        JOIN joins AS j
                ON t.item_id = j.child_id
        JOIN items AS parent
                ON j.item_id = parent.item_id
)
SELECT item_id, jsonb_pretty(json)
FROM t
WHERE item_id = 1;

It works thanks to this beautiful answer. Now imagine we had

INSERT INTO joins (item_id, child_id) VALUES
  (1,2),
  (2,3),
  (3,1);

So we get a loop 1->2->3->1 and I want to limit its output using limiters - I want all my trees to be no bigger than depth X set by a number I give to this tree constructing function. How to do such thing in postgres 13+?

2 Answers 2

2

It's pretty simple, really: you add the recursion level value and filter on it:

WITH RECURSIVE t(item_id, json, level) AS (
        SELECT item_id, to_jsonb(items), 1
        FROM items
        WHERE NOT EXISTS (
                SELECT 1
                FROM joins
                WHERE items.item_id = joins.item_id
        )
        UNION ALL
        SELECT parent.item_id, to_jsonb(parent) || jsonb_build_object( 'children', t.json ),
               level + 1
        FROM t
        JOIN joins AS j
                ON t.item_id = j.child_id
        JOIN items AS parent
                ON j.item_id = parent.item_id
        WHERE level < 3
)
SELECT item_id, jsonb_pretty(json)
FROM t
WHERE item_id = 1;
0
2

I'm not entirely clear from your question whether you primarily want to just limit depth traversal, or if in reality you would actually want a solution for recursion loops if it was possible. I've gone for the latter.

What you can do is add an extra column to the rCTE, which concatenates the ascendants together. Then you check in the recursive join for the new item, that it isn't in the array already.

Fortunately, Postgres has arrays, which simplifies things (otherwise you would need to stringify everything).

WITH RECURSIVE t(item_id, json, items) AS (
        SELECT
            item_id,
            to_jsonb(items),
            ARRAY[items.item_id]
        FROM items
        WHERE NOT EXISTS (
                SELECT 1
                FROM joins
                WHERE items.item_id = joins.item_id
        )
        UNION ALL
        SELECT
            parent.item_id,
            to_jsonb(parent) || jsonb_build_object( 'children', t.json ),
            array_append(t.items, parent.item_id)
        FROM t
        JOIN joins AS j
                ON t.item_id = j.child_id
                AND NOT EXISTS (SELECT j.item_id
                                INTERSECT
                                SELECT * FROM unnest(t.items))
        JOIN items AS parent
                ON j.item_id = parent.item_id
)
SELECT item_id, jsonb_pretty(json)
FROM t
WHERE item_id = 1;

I used the NOT EXISTS condition, because a much simpler condition had problems

AND j.item_id <> ANY(t.items)
-- or
AND j.item_id <> ANY(SELECT * FROM unnest(t.items))

For some reason this syntax recursed forever, I can't quite work out why.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.