How to limit tree traversal in case of loops?

All we need is an easy explanation of the problem, so here it is.

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+?

How to solve :

I know you bored from this bug, So we are here to help you! Take a deep breath and look at the explanation of your problem. We have many solutions to this problem, But we recommend you to use the first method because it is tested & true method that will 100% work for you.

Method 1

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;

Method 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.

Note: Use and implement method 1 because this method fully tested our system.
Thank you 🙂

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply