Recursion with PostgreSQL Part 3 - Cycle Detection

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
$$;

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;
$$;

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

select * from big_tree_test

I expect to see the following manually checked results:

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

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;

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;
$$;

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

• 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;

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.