Skip to Main Content
  • Questions

  • cycle detected in recursive query where it seems to be no cycle

Breadcrumb

Question and Answer

Chris Saxon

Thanks for the question, Tomáš.

Asked: September 16, 2020 - 12:29 pm UTC

Last updated: March 05, 2021 - 9:40 am UTC

Version: Oracle 11

Viewed 1000+ times

You Asked

I have recursive query on Oracle 11g table with undirected graph data. Each row represents one edge. The recursive query traverses all edges starting from given input edge. The idea of query is:

- input edge is at the 0th level
- for n>0, edge is on n-th level if it incides with node of some edge on (n-1)-th level.

Query:

with edges (id, a, b) as (
  select 1, 'X', 'Y' from dual union
  select 2, 'X', 'Y' from dual
), r (l, id, parent_a, parent_b, child_a, child_b, edge_seen) as (
  select 0, id, null, null, a, b, cast(collect(id) over () as sys.ku$_objnumset)
  from edges
  where id = 1 
  union all
  select r.l + 1, e.id, r.child_a, r.child_b, e.a, e.b
       , r.edge_seen multiset union distinct (cast(collect(e.id) over () as sys.ku$_objnumset))
  from r
  join edges e on (r.child_a in (e.a, e.b) or r.child_b in (e.a, e.b))
    and e.id not member of (select r.edge_seen from dual)
)
select * from r;


The query worked well with other inputs until two parallel edges between same node pair occured. In this case, there is edge 1 on 0th level of recursion (initial row). I expected edge 2 would be added to result on 1st level of recursion since join condition holds. Instead I get "ORA-32044: cycle detected while executing recursive with query".

I know this error is reported when the row newly joined to recursive query result would be same as some existing row. What I don't understand is why Oracle treats row with same node ids but different edge id as duplicate. Adding

cycle child_a, child_b set iscycle to 1 default 0


clause gives iscycle=1 for new row, adding

cycle id, child_a, child_b set iscycle to 1 default 0


gives iscycle=0, which is both correct.


Is it some known Oracle 11g bug and what's the best way to handle it?

I cannot fill LiveSQL link form since LiveSQL supports only Oracle 19 and the problem is reproducible only in Oracle 11g which I can't migrate from. The dbfiddle equivalent is https://dbfiddle.uk/?rdbms=oracle_11.2&fiddle=43af3cfae920e31f9a2748c1c31b54ad .

Thanks.

and Chris said...

From the docs:

A row is considered to form a cycle if one of its ancestor rows has the same values for the cycle columns.

i.e. the database doesn't consider the whole row, only the values of the columns you use in the cycle clause.

So when you have only:

cycle child_a, child_b


The database does consider this a cycle because edge 2 has exactly the same A, B values as edge 1, which is its ancestor.

By adding edge_seen and the multiset union nonsense, what you've done is implement your own cycle clause!

You could remove this and cycle on ID alone:

with edges (id, a, b) as (
  select 1, 'X', 'Y' from dual union
  select 2, 'X', 'Y' from dual
), r (l, id, parent_a, parent_b, child_a, child_b) as (
  select 0, id, null, null, a, b
  from edges
  where id = 1 
  union all
  select r.l + 1, e.id, r.child_a, r.child_b, e.a, e.b
  from r
  join edges e on (r.child_a in (e.a, e.b) or r.child_b in (e.a, e.b))
) 
  cycle id set iscycle to 1 default 0
select * from r
where  iscycle = 0;

L    ID    PARENT_A    PARENT_B    CHILD_A    CHILD_B    ISCYCLE   
   0     1 <null>      <null>      X          Y          0          
   1     2 X           Y           X          Y          0

Rating

  (1 rating)

Is this answer out of date? If it is, please let us know via a Comment

Comments

unclarities about cycle detection and collection usage

Tomáš Záluský, March 04, 2021 - 10:24 pm UTC

Thanks for response, Chris.

I read definition of cycle you cited and I understand cycle clause makes it working. Actually I switched to cycle clause according to your advice.
However, I would like to understand the cause of ORA-32044 error when no cycle clause exists. In such case I assume the ancestor row is (0,1,null,null,X,Y,{1}) and the new row generated in recursive part is (1,2,X,Y,X,Y,{1,2}). What's the definition of cycle in case of absence of cycle clause? Or was the error caused by usage of collection?

And second unclarity: was the usage of collection wrong only because I mixed it with built-in cycle detection or aren't you recommending collections at all circumstances? I saw them in some of your tutorials. After replacing edge_seen collection by cycle clause I encountered performance problems having graph with 65 edges: while edge_seen keeps number of recursion levels as small as possible, traversal controlled by cycle clause generates has possible walks with lot of duplicities. Is there any way how to avoid it?
Chris Saxon
March 05, 2021 - 9:40 am UTC

What's the definition of cycle in case of absence of cycle clause?

From the docs:

a row forms a cycle if one of its ancestor rows has the same values for all the columns in the column alias list for query_name that are referenced in the WHERE clause of the recursive member.

In the example above, both rows have the same value for A and B and only these are in the join clause. As a result you have a cycle because both rows point to themselves as well as the other row. Cycle detection avoids this problem.

was the usage of collection wrong only because I mixed it with built-in cycle detection or aren't you recommending collections at all circumstances?

There are reasons for using collections, just not this!

In this case there's a much easier way to avoid revisiting the same point: check that the new ID > current ID:

with edges (id, a, b) as (
  select 1, 'X', 'Y' from dual union
  select 2, 'X', 'Y' from dual
), r (l, id, parent_a, parent_b, child_a, child_b) as (
  select 0, id, null, null, a, b
  from edges
  where id = 1 
  union all
  select r.l + 1, e.id, r.child_a, r.child_b, e.a, e.b
  from r
  join edges e 
  on (r.child_a in (e.a, e.b) or r.child_b in (e.a, e.b))
  and e.id > r.id
) 
select * from r;


It looks like you're solving a true graph traversal problem, in which case it's worth looking at the graph capabilities in the database to do this. These are now included in your database license, no extra costs!

https://blogs.oracle.com/oraclespatial/graph-database-and-analytics-for-everyone
more

Connor and Chris don't just spend all day on AskTOM. You can also catch regular content via Connor's blog and Chris's blog. Or if video is more your thing, check out Connor's latest video and Chris's latest video from their Youtube channels. And of course, keep up to date with AskTOM via the official twitter account.

More to Explore

Analytics

Analytic SQL got you confused? Check out Connor McDonald's complete video course.