Recursion with PostgreSQL Follow-Up 2 - CYCLE Detection and Processing Millions of Nodes

[vbilopav]

Yesterday, I wrote another article for my Recursion with PostgreSQL series: Recursion with PostgreSQL Follow-Up 1 - Performances .

My conclusion was that the CTE recursion method was severely lacking a way out of the infinite loops - and then I proceeded to write a version that defined a maximum recursion depth as a parameter:

create or replace function select_nodes_recursive_cte(
    _id text,
    _max_recursion int = 100
)
returns table (
    id text,
    parent_id text,
    level int
)
language sql
as 
$$
with recursive _recursive_cte as (
    select
        id,
        parent_id,
        1 as level
    from
        big_tree_test
    where 
        id = _id
    
    union 

    select
        rec.parent_id as id,
        t.parent_id,
        rec.level + 1 as level
    from
        _recursive_cte rec
        inner join big_tree_test t on rec.parent_id = t.id
    where
        level < _max_recursion 
)
select r.id, r.parent_id, r.level
from _recursive_cte r
$$;

And that seemed to me as a significant limitation on the part of PostgreSQL's recursive functionality, a sort of deal breaker in my book.

Then, I proceeded with a classic functional recursion (as opposed to this CTE recursion), and I tried to figure out how much it could be optimized.

Oh, much little did I know...

During the day, @xocolatl (Vik Fearing) left this comment that pointed out that PostgreSQL already has a feature called Cycle Detection which was exactly to solution for my problem.

And Vik was kind enough to even write a full working version for me (using the example from the first article).

What can I say? I always felt that three days of debugging and testing could save 30 minutes of reading the documentation. And I'm also amazed that there is always something new to learn in SQL, even after many decades of use.

Anyway, the CYCLE feature was exactly the right solution. Documentation:

When working with recursive queries, it is important to be sure that the recursive part of the query will eventually return no tuples, or else the query will loop indefinitely. Sometimes, using UNION instead of UNION ALL can accomplish this by discarding rows that duplicate previous output rows. However, often, a cycle does not involve output rows that are completely duplicated: it may be necessary to check just one or a few fields to see if the same point has been reached before. The standard method for handling such situations is to compute an array of the already-visited values.

The way it works syntax-wise is to add at the end of recursive CTE this: CYCLE [field_to_check_for_cycle] SET is_cycle USING path, where path is a newly generated field containing a path to check, but you may call it or use it as you wish.

The is_cycle is also a new field with a fixed name of the boolean type that will tell us if we are in a cycle or not. And all we have to do at the end is to check if we are in the cycle with where not is_cycle, and that is it.

So, given that example, Vik provided the function select_nodes_recursive_cte, will now look like this:

create or replace function select_nodes_recursive_cte(
    _id text
)
returns table (
    id text,
    parent_id text,
    level int
)
language sql
as 
$$
with recursive _recursive_cte as (
    select
        id,
        parent_id,
        1 as level
    from
        big_tree_test
    where 
        id = _id
    
    union 

    select
        rec.parent_id as id,
        t.parent_id,
        rec.level + 1 as level
    from
        _recursive_cte rec
        inner join big_tree_test t on rec.parent_id = t.id
)
cycle id set is_cycle using path
select r.id, r.parent_id, r.level
from _recursive_cte r
where not is_cycle;
$$;

New Problem

After I tested this version on my standard test fixture:

select * from big_tree_test

id	parent_id
node_1	node_3
node_1	node_8
node_4	node_8
node_5	node_7
node_6	node_4
node_6	node_6
node_6	node_9
node_7	node_10
node_8	node_10
node_8	node_5
node_8	node_9
node_9	node_9
node_10	node_1

I expect to see the following manually checked results:

id	parent_id	level
node_1	node_3	1
node_1	node_8	1
node_8	node_10	2
node_8	node_5	2
node_8	node_9	2
node_10	node_1	3
node_5	node_7	3
node_9	node_9	3
node_7	node_10	4

However, that is NOT what the new function with CYCLE returns. This version adds another (unexpected) recursion level (level 5 with node_10):

id	parent_id	level
node_1	node_3	1
node_1	node_8	1
node_8	node_10	2
node_8	node_5	2
node_8	node_9	2
node_10	node_1	3
node_5	node_7	3
node_9	node_9	3
node_7	node_10	4
node_10	node_1	5

The node node_10 - node_1 has already appeared in level 3 and, therefore, in my opinion - shouldn't be included in the results.

After some investigation, my best assumption is that the PostgreSQL algorithm, when it decides that the row is a cycle row - includes that row also into the results and then exists cycle.

And again, the only way to exclude this field that I've found is to use the MIN aggregate in the final query:

return query 
select 
    t.id,
    t.parent_id,
    min(t.level) as level
from 
    _result t
group by
    t.id, t.parent_id;

After this small tweak - the results from both functions select_nodes_recursive_cte (recursive CTE with CYCLE) and select_nodes_recursive_function (my optimized classic function recursion version) - are identical.

The next step is to do some serious performance testing.

However, I'm still not completely sure about this last node: Maybe it would be a better idea to leave select_nodes_recursive_cte as-is (without MIN aggregate) and to modify select_nodes_recursive_function to behave identically as CTE with CYCLE version. That means that before exiting recursion, we must include that last node.

So the final version select_nodes_recursive_function looks like this:

create or replace function select_nodes_recursive_function(
    _p_id text[],
    _level int = 1
)
returns table (
    id text,
    parent_id text,
    level int
)
language plpgsql
as 
$$
declare 
    _row record;
    _parents text[];
    _id text[];
begin    
    if not exists(
        select 1 from information_schema.tables t
        where t.table_name = '_result' and table_type = 'LOCAL TEMPORARY'
    ) then
        create temp table _result (
            id text,
            parent_id text,
            level int
        ) on commit drop;
    end if;

    _id = array(select unnest(_p_id) except select distinct t.id from _result t);

    if _id = '{}' then
        insert into _result
        select
            t.id,
            t.parent_id,
            _level
        from
            big_tree_test t
        where 
            t.id = any(_p_id);
        return;
    end if;
    
    with _insert_cte as (
        insert into _result
        select
            t.id,
            t.parent_id,
            _level
        from
            big_tree_test t
        where 
            t.id = any(_id)
        returning 
            _result.parent_id
    ) 
    select array_agg(distinct p.parent_id)
    into _parents
    from _insert_cte p; 

    perform select_nodes_recursive_function(_parents, _level + 1);

    return query 
    select 
        t.id,
        t.parent_id,
        t.level
    from 
        _result t;
end;
$$;

As we can see, before we exit the recursion with return - we insert the current nodes with the current level.

Both functions are returning identical results now, and we are finally ready for serious performance testing.

Performance Testing

round	records 1	unique nodes 2	select_nodes_recursive_function	select_nodes_recursive_cte
1	13	8	00:00:00.058	00:00:00.044
2	13	8	00:00:00.060	00:00:00.037
3	13	8	00:00:00.053	00:00:00.060
1	45	20	00:00:00.055	00:00:00.051
2	45	20	00:00:00.056	00:00:00.054
3	45	20	00:00:00.053	00:00:00.071
1	90	30	00:00:00.065	00:00:24.986
2	90	30	00:00:00.048	00:00:19.298
3	90	30	00:00:00.060	00:00:21.342
1	128	30	00:00:00.092	ERROR 3
2	128	30	00:00:00.041	ERROR 3
3	128	30	00:00:00.058	ERROR 3
1	291	99	00:00:00.089	ERROR 3
2	291	99	00:00:00.063	ERROR 3
3	291	99	00:00:00.049	ERROR 3
1	1723	148	00:00:00.100	ERROR 3
2	1723	148	00:00:00.050	ERROR 3
3	1723	148	00:00:00.054	ERROR 3
1	6638	499	00:00:00.092	ERROR 3
2	6638	499	00:00:00.069	ERROR 3
3	6638	499	00:00:00.078	ERROR 3
1	24803	999	00:00:00.120	ERROR 3
2	24803	999	00:00:00.128	ERROR 3
3	24803	999	00:00:00.128	ERROR 3
1	126804	5000	00:00:00.785	ERROR 3
2	126804	5000	00:00:00.751	ERROR 3
3	126804	5000	00:00:00.778	ERROR 3
1	1301479	99999	00:00:07.665	ERROR 3
2	1301479	99999	00:00:07.743	ERROR 3
3	1301479	99999	00:00:08.729	ERROR 3
1	2510281	49998	00:00:12.596	ERROR 3
2	2510281	49998	00:00:13.621	ERROR 3
3	2510281	49998	00:00:14.128	ERROR 3
1	5050378	100000	00:00:37.156	ERROR 3
2	5050378	100000	00:00:39.230	ERROR 3
3	5050378	100000	00:00:40.284	ERROR 3

• 1 - records is the number of total records in big_tree_test table. That is the number of tree connections.
• 2 - unique nodes is the number of unique id values (nodes) in big_tree_test table. That is the number of unique tree nodes.
• 3 - Execution ends up in an error. Approximately after a minute and a half of execution, it breaks with: ERROR: could not write to file "base/pgsql_tmp/pgsql_tmp226.8386": No space left on device. I have 400GB free on my laptop. In later tests, when I ran this function on a larger, the connection was being reset. So, something very strange is going on with recursive CTE execution.

Optimized function select_nodes_recursive_function starts to seriously degrade in performance just after a couple of million tree connections and after a million unique tree nodes.

For the last performance tests, I tried to create an index on the tree table:

create index on big_tree_test using btree (id);
reindex table big_tree_test;

Results are approximately the same:

1. 00:00:33.184
2. 00:00:37.163
3. 00:00:36.106

Most likely, indexes were never used.

Perhaps someone has a better idea?

Conclusion

Makeup what you will, it is what it is.

I still hold the position that recursive CTE queries are confusing, at least to me.

Anyhow, if someone is using them and starts to experience performance issues, maybe there is a better way?

This approach I demonstrated in this series may be the solution for processing a huge number of tree nodes.

Or maybe not.

Anyhow, I said last time that I'd focus on testing and debugging these functions now, I guess it will have to wait for another article in this series.

UPDATE 1:

I was suggested to use UNION ALL instead of just UNION in the CTE version. Unfortunately, no difference. On a small dataset, it will return identical results, it will be slow on a medium dataset, and it will crash on a big dataset.

I still don't know what to think of it.

Either the PostgreSQL CTE implementation is bad or ... I really don't know.

Next, I'll try to play around with that CTE version execution plan to try to figure it out.

UPDATE 2

Here is the execution plan for the CTE version (with UNION ALL, which should be better because it doesn't look for duplicates):

CTE Scan on _recursive_cte r  (cost=73.68..86.58 rows=322 width=68) (actual time=0.014..81982.777 rows=7341736 loops=1)
  Filter: (NOT is_cycle)
  Rows Removed by Filter: 11291893
  CTE _recursive_cte
    ->  Recursive Union  (cost=0.00..73.68 rows=645 width=76) (actual time=0.012..65812.549 rows=18633629 loops=1)
          ->  Seq Scan on big_tree_test  (cost=0.00..2.59 rows=5 width=51) (actual time=0.011..0.019 rows=5 loops=1)
                Filter: (id = 'node_1'::text)
                Rows Removed by Filter: 122
          ->  Hash Join  (cost=1.31..5.82 rows=64 width=76) (actual time=216.675..1395.792 rows=503611 loops=37)
                Hash Cond: (t.id = rec.parent_id)
                ->  Seq Scan on big_tree_test t  (cost=0.00..2.27 rows=127 width=14) (actual time=0.009..0.031 rows=127 loops=36)
                ->  Hash  (cost=1.00..1.00 rows=25 width=68) (actual time=216.606..216.606 rows=198425 loops=37)
                      Buckets: 32768 (originally 1024)  Batches: 128 (originally 1)  Memory Usage: 117836kB
                      ->  WorkTable Scan on _recursive_cte rec  (cost=0.00..1.00 rows=25 width=68) (actual time=0.044..104.818 rows=198425 loops=37)
                            Filter: (NOT is_cycle)
                            Rows Removed by Filter: 305186
Planning Time: 0.206 ms
Execution Time: 83266.186 ms

This -> Recursive Union (cost=0.00..73.68 rows=645 width=76) (actual time=0.012..65812.549 rows=18633629 loops=1), this has some crazy number of rows and execution time.

The big_tree_test has only 127 records with 49 unique id's.

I'm baffled.

[fatalmind]

I cannot understand some of your claims:

The node node_10 - node_1 has already appeared in level 3 and, therefore, in my opinion - shouldn't be included in the results.

You function select_nodes_recursive_function also delivers this twice, and it is also correct because they appear on different path's. E.g. run the query and also select the path column:

with recursive _recursive_cte as (
    select
        id,
        parent_id,
        1 as level
    from
        big_tree_test
    where
        id = 'node_1'

    union ALL
    select
        rec.parent_id as id,
        t.parent_id,
        rec.level + 1 as level
    from
        _recursive_cte rec
        inner join big_tree_test t on rec.parent_id = t.id
)
cycle id set is_cycle using path
select r.id, r.parent_id, r.level, path
from _recursive_cte r
where not is_cycle;

   id    | parent_id | level |                      path
---------+-----------+-------+-------------------------------------------------
 node_1  | node_3    |     1 | {(node_1)}
 node_1  | node_8    |     1 | {(node_1)}
 node_8  | node_10   |     2 | {(node_1),(node_8)}
 node_8  | node_5    |     2 | {(node_1),(node_8)}
 node_8  | node_9    |     2 | {(node_1),(node_8)}
 node_5  | node_7    |     3 | {(node_1),(node_8),(node_5)}
 node_9  | node_9    |     3 | {(node_1),(node_8),(node_9)}
 node_10 | node_1    |     3 | {(node_1),(node_8),(node_10)}
 node_7  | node_10   |     4 | {(node_1),(node_8),(node_5),(node_7)}
 node_10 | node_1    |     5 | {(node_1),(node_8),(node_5),(node_7),(node_10)}

The level=5 row has visited node_10 only once, the other row that gave id=node_10 is on a different path (directly from 8->10, not via 5->7). Your manual implementation seems to treat this differently: It's not excluding just cycles, but generally visiting each node only once (don't have the time to check why node_10/node_1 is still included twice when I run your manual function).

For reference, your manually verified test set:

INSERT INTO big_tree_test VALUES ('node_1', 'node_3'),
('node_1',  'node_8'),
('node_4',  'node_8'),
('node_5',  'node_7'),
('node_6',  'node_4'),
('node_6',  'node_6'),
('node_6',  'node_9'),
('node_7',  'node_10'),
('node_8',  'node_10'),
('node_8',  'node_5'),
('node_8',  'node_9'),
('node_9',  'node_9'),
('node_10', 'node_1')
;

[lelle1234]

Does it make a difference if you put a unique index on big_tree_test (id)?

[vbilopav]

@lelle1234 Id field isn't unique, I tried with non-unique, and it really doesn't make any difference.

[vbilopav]

Hi @fatalmind

Thanks for your input; I much appreciated it.

It does seem that I got CYCLE and PATH wrong (again). So CYCLE means not ID is repeated as I first implemented. It means the ID repeats in a PATH.

And in order to figure out that, we need to calculate the path correctly. And if we have a lot of data, those paths can be rather long, so it makes sense that I ran out of space.

However, I gave it more thought and tried to find a way to calculate a path and is_cycle correctly without using recursive CTE.

And I think I did. Actually, I'm pretty sure I did. Preliminary performance tests show that it still runs much faster than the recursive CTE and it doesn't run out of space. So it's much more efficient.

I'll do some more testing and write another article when I have some time, perhaps over the weekend (have to work for a living, unfortunately). Meanwhile, here is what I came up with:

select drop_function('public', 'select_nodes_recursive_function');

create or replace function select_nodes_recursive_function(
    _id text[],
    _level int = 1
)
returns table (
    id text,
    parent_id text,
    level int,
    path text[],
    is_cycle boolean
)
language plpgsql
as 
$$
declare 
    _row record;
    _parents text[];
begin    
    if not exists(
        select 1 from information_schema.tables t
        where t.table_name = '_result' and table_type = 'LOCAL TEMPORARY'
    ) then
        create temp table _result (
            id text,
            parent_id text,
            level int,
            path text[],
            is_cycle boolean
        ) on commit drop;
    end if;
  
    raise info 'id=%, level=%', _id, _level;
    with _insert_cte as (
        insert into _result
        select
            t.id,
            t.parent_id,
            _level,
            array_append(l.path, t.id),
            coalesce(l.is_cycle, false) as is_cycle
        from
            big_tree_test t
            left outer join lateral (
                select p.path, t.id = any(p.path) as is_cycle
                from _result p
                where p.level = _level-1 and p.parent_id = t.id
                limit 1
            ) l on true
        where 
            t.id = any(_id)
            and not coalesce(l.is_cycle, false)
        returning 
            _result.parent_id
    ) 
    select array_agg(distinct p.parent_id)
    into _parents
    from _insert_cte p;
        
    if not (_parents is null or _parents = '{}') then
        raise info '_parents=%, level=%', _parents, _level;
        perform select_nodes_recursive_function(_parents, _level + 1);
    end if;
    
    return query 
    select 
        t.id,
        t.parent_id,
        t.level,
        t.path,
        t.is_cycle
    from 
        _result t;
end;
$$;

create or replace function select_nodes_recursive_function(_id text)
returns table (
    id text,
    parent_id text,
    level int,
    path text[],
    is_cycle boolean
)
language sql
as 'select id, parent_id, level, path, is_cycle from select_nodes_recursive_function(array[_id]::text[])';

select * from select_nodes_recursive_function('node_1');

Again, thanks for your feedback and calirifcation. I hope you'll find these performance optimizations interesting.

[vbilopav]

Hi @fatalmind ,

I just wrote another follow-up on this article and approach.

Here it is:
Recursion with PostgreSQL Follow-Up 3 - Finding the Right Path

Thank you for your help and hope you find it interesting.