4

I'm trying to write a recursive CTE to explore a workflow system. Unfortunately, I'm getting maximum recursion errors due to loops:

with cteActs as
 (
  select a.id as [id], aa.TASKNEXTID as [childid]
  from TASK a
  inner join TASKNEXT aa on a.id = aa.TASKPARENTID
  where a.id != aa.TASKNEXTID
  ),
 cteNext as
(
    select a.*
    from cteActs as a
    where a.id=42
    union all
    select a.*
    from cteActs as a
    inner join cteNext as n on a.id = n.childid
    )
select * 
from cteNext

The table TASK is a list of tasks whereby 42 is "Start job" for example. TASKNEXT links 42 to possible subtasks back in the TASK table. e.g. it may link 42 to 43 which may be "Find materials" e.g.

ID, name, childID
42, Start job, 43
42, Start job, 44
43, Find materials, 200
44, Report to boss, 201
201, Discuss with boss, 202
202, Receive payment, 44

I think the recursion is dying because 44>201>202>44 creates a loop the query doesn't escape from. How can I allow for this? Most of the examples/tutorials I read assume a strict parent>child relationship, where a child can never be the parent of something in its own higher tree.

What I'm trying to get to is a distinct list of TASKS that originate from flows starting at task 42, or wherever I choose.


This is iteration 2 which may work, but runs so slow:

  select a.id as [id], aa.ACTIONACTIVITYID as [childid]
   into #temp
  from TASK a
  inner joinTASKNEXT aa on a.id = aa.TASKPARENTID
  where a.id != aa.TASKNEXTID    
  create clustered index [hello] on #temp (ID ASC)
  create nonclustered index [hello2] on #temp (childid ASC)
  ;
with cteNext as
(
    select a.*, 
    cast(',' + cast(a.ID as varchar(10)) + ',' as varchar(max)) as Path,
    0 as [cyc]
    from #temp as a
    where a.id=42
    union all
    select a.*,
    n.Path + cast(a.ID as varchar(10)) + ',',
         case when n.Path like '%,'+cast(a.ID as varchar(10))+',%' 
           then 1 
           else 0 
         end as [cyc]
    from #temp as a
    inner join cteNext as n on a.id = n.childid
    where n.cyc = 0
    )

select   id, childid
from cteNext
where cyc =0

Execution plan

5
  • 2
    Not an identical duplicate question but it is related. CTE Running in Infinite Loop. You could modify one of the answers to make your recursion terminate when a loop is found. Use the same technique used in the answer to build a string representing the loop path and remove where Cycle = 1 from the main query and you should have what you are looking for, I guess? Look at the second answer, not the accepted one. Jan 26, 2017 at 10:14
  • I think that works, I refactored my code and tried at a sub flow than I know involves a loop and just half a dozen tasks. However for task 42 (the biggest) it's taking forever to execute. 32minutes and counting as I type.
    – Paul
    Jan 26, 2017 at 11:15
  • 1
    Your performance could probably be improved by putting the result for cteActs in a temp table and use that temp table instead of the CTE in the recursive part of the query. As you have it now cteActsis evaluated a lot, I think once for each invocation of the recursive part of the query. . Proper indexing of the temp table will also help. Jan 26, 2017 at 11:53
  • @MikaelEriksson is right, but you may find the limiting factor to be that the recursive part of an rCTE is always run serially. Check out this article for alternatives: sqlblog.com/blogs/adam_machanic/archive/2015/04/07/… Jan 26, 2017 at 12:55
  • @sp_BlitzErik I think the data is just too complex, running a select * and watching the path column change as I scroll it's running the right ragged and never getting back up to the left most tasks.
    – Paul
    Jan 26, 2017 at 15:01

1 Answer 1

3

So the best result I've managed to come up with is adding the following improvements
- optimising the queried table (creating a new temporary table with suggested indexes)
- adding a path element to check I'm not revisiting an existing part of the path
- adding a depth counter as a limiter. This does however mean I'm consciously choosing not to have the full result set

  select a.id as [id], aa.ACTIONACTIVITYID as [childid]
   into #temp
  from TASK a
  inner join TASKNEXT aa on a.id = aa.TASKPARENTID
  where a.id != aa.TASKNEXTID

  create clustered index [hello] on #temp (ID ASC)
  create nonclustered index [hello2] on #temp (childid ASC)
  ;
  drop table #temp2;
with cteNext as
(
    select a.*, 
    cast(',' + cast(a.ID as varchar(10)) + ',' as varchar(max)) as Path,
    0 as [cyc], 0 as [depth]
    from #temp as a
    where a.id=42
    union all
    select a.*,
    n.Path + cast(a.ID as varchar(10)) + ',',
         case when n.Path like '%,'+cast(a.ID as varchar(10))+',%' 
           then 1 
           else 0 
         end as [cyc], n.depth+1 as [depth]
    from #temp as a
    inner join cteNext as n on a.id = n.childid
    where n.cyc = 0 and n.depth <=11
    )

select *
into #temp2
from cteNext
where cyc =0

The initial purpose of this data is "fluffy", I'm generating a graph-map out of it to show our workflows so a limited depth is fine in the first instance at least. But better answers accepted if anyone has any

2
  • 1
    I see a varchar(max) in your SQL statement. I my experience, SQL Server seems to operate slower on varchar(max) columns than a varchar(xxxx) column even though the data content is the same. Based upon the length of your IDs and limiting depth, you might get faster performance limiting your varchar to a specified length just long enough to include the longest IDs and delimiters.
    – Zarepheth
    Mar 6, 2018 at 21:36
  • I ran into a similar issue when building an overview of our database. I wrote a CTE to recursively follow foreign key references to a given base table, but ran into infinite loops in multiple places. I like the idea of keeping a path element to allow cutting off those loops.
    – dybzon
    Feb 19, 2021 at 9:25

Your Answer

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

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