Version 11g release 2 introduced recursive subquery factoring or the recursive with clause. This is an extension to the SQL syntax with which you can do recursive/hierarchical queries. However, since version 2, Oracle has had the connect-by clause for hierarchical queries. And at first glance, the connect-by and the recursive-with seem very similar in what they can do. But on a second look, there are some really interesting differences. This post explores some of the similarities and the differences between the two.
Let's start with a query that will be familiar with everyone who has followed a SQL course at the start of their career: the classic example using the EMP table:
rwijk@ORA11GR2> select lpad(' ', 2 * level - 2, ' ') || ename as ename
2 , empno
3 , mgr
4 , level
5 from emp
6 connect by mgr = prior empno
7 start with mgr is null
8 /
ENAME EMPNO MGR LEVEL
-------------------- ---------- ---------- ----------
KING 7839 1
JONES 7566 7839 2
SCOTT 7788 7566 3
ADAMS 7876 7788 4
FORD 7902 7566 3
SMITH 7369 7902 4
BLAKE 7698 7839 2
ALLEN 7499 7698 3
WARD 7521 7698 3
MARTIN 7654 7698 3
TURNER 7844 7698 3
JAMES 7900 7698 3
CLARK 7782 7839 2
MILLER 7934 7782 3
14 rows selected.The hierarchy is made visible by left padding the ename with spaces according to the level. The lower in the hierarchy, the more the ename is indented. Using the recursive with clause, the query becomes:
rwijk@ORA11GR2> with emps (ename,empno,mgr,lvl) as
2 ( select ename
3 , empno
4 , mgr
5 , 1
6 from emp
7 where mgr is null
8 union all
9 select emp.ename
10 , emp.empno
11 , emp.mgr
12 , emps.lvl + 1
13 from emp
14 join emps on (emp.mgr = emps.empno)
15 ) search depth first by empno set a
16 select lpad(' ', 2 * lvl - 2, ' ') || ename as ename
17 , empno
18 , mgr
19 , lvl
20 from emps
21 order by a
22 /
ENAME EMPNO MGR LVL
-------------------- ---------- ---------- ----------
KING 7839 1
JONES 7566 7839 2
SCOTT 7788 7566 3
ADAMS 7876 7788 4
FORD 7902 7566 3
SMITH 7369 7902 4
BLAKE 7698 7839 2
ALLEN 7499 7698 3
WARD 7521 7698 3
MARTIN 7654 7698 3
TURNER 7844 7698 3
JAMES 7900 7698 3
CLARK 7782 7839 2
MILLER 7934 7782 3
14 rows selected.
The query has become a lot more verbose, but as you can see, it can do the same kind of hierarchical queries as the good old connect-by. With the recursive with clause you don't have a LEVEL pseudocolumn, but you can easily mimic one as above. The first part of the UNION ALL contains the start-with query, where the newly introduced column contains the number 1. The second part of the query contains the recursion where you refer to the name of the recursive-with clause. The select list contains "emps.lvl + 1" to calculate the level.
Using the same technique you can also mimic other helper functions. On the AMIS-blog, Lucas Jellema already wrote how to simulate SYS_CONNECT_BY_PATH, CONNECT_BY_ROOT, and even CONNECT_BY_ISLEAF. Now let's have a look at some of the differences:
Cycle detection
If your data contains a cycle, the query could run infinitely. So Oracle detects this situation and lets the query fail. We can see that behaviour by letting JONES be the manager of KING. Now KING manages JONES and JONES manages KING. A loop:
rwijk@ORA11GR2> update emp
2 set mgr = 7566
3 where ename = 'KING'
4 /
1 row updated.
rwijk@ORA11GR2> select lpad(' ', 2 * level - 2, ' ') || ename as ename
2 , empno
3 , mgr
4 , level
5 from emp
6 connect by mgr = prior empno
7 start with ename = 'KING'
8 /
ERROR:
ORA-01436: CONNECT BY loop in user data
The recursive with clause also has cycle detection, of course:
rwijk@ORA11GR2> with emps (ename,empno,mgr,lvl) as
2 ( select ename
3 , empno
4 , mgr
5 , 1
6 from emp
7 where ename = 'KING'
8 union all
9 select emp.ename
10 , emp.empno
11 , emp.mgr
12 , emps.lvl + 1
13 from emp
14 join emps on (emp.mgr = emps.empno)
15 ) search depth first by empno set a
16 select lpad(' ', 2 * lvl - 2, ' ') || ename as ename
17 , empno
18 , mgr
19 , lvl
20 from emps
21 order by a
22 /
from emps
*
ERROR at line 20:
ORA-32044: cycle detected while executing recursive WITH query
A different error code, but a similar message.
Since version 10, the connect-by has the NOCYCLE attribute and the CONNECT_BY_ISCYCLE pseudocolumn:
rwijk@ORA11GR2> select lpad(' ', 2 * level - 2, ' ') || ename as ename
2 , empno
3 , mgr
4 , level
5 , connect_by_iscycle
6 from emp
7 connect by nocycle mgr = prior empno
8 start with ename = 'KING'
9 /
ENAME EMPNO MGR LEVEL CONNECT_BY_ISCYCLE
-------------------- ---------- ---------- ---------- ------------------
KING 7839 7566 1 0
JONES 7566 7839 2 1
SCOTT 7788 7566 3 0
ADAMS 7876 7788 4 0
FORD 7902 7566 3 0
SMITH 7369 7902 4 0
BLAKE 7698 7839 2 0
ALLEN 7499 7698 3 0
WARD 7521 7698 3 0
MARTIN 7654 7698 3 0
TURNER 7844 7698 3 0
JAMES 7900 7698 3 0
CLARK 7782 7839 2 0
MILLER 7934 7782 3 0
14 rows selected.Here you see that the query continues, and just stops processing the branch where the cycle was detected. The CONNECT_BY_ISCYCLE shows a "1" exactly at the spot where this cycle was detected.
The recursive with clause has a CYCLE clause you can use for something similar:
rwijk@ORA11GR2> with emps (ename,empno,mgr,lvl) as
2 ( select ename
3 , empno
4 , mgr
5 , 1
6 from emp
7 where ename = 'KING'
8 union all
9 select emp.ename
10 , emp.empno
11 , emp.mgr
12 , emps.lvl + 1
13 from emp
14 join emps on (emp.mgr = emps.empno)
15 ) search depth first by empno set a
16 cycle empno set is_cycle to '1' default '0'
17 select lpad(' ', 2 * lvl - 2, ' ') || ename as ename
18 , empno
19 , mgr
20 , lvl
21 , is_cycle
22 from emps
23 /
ENAME EMPNO MGR LVL I
-------------------- ---------- ---------- ---------- -
KING 7839 7566 1 0
JONES 7566 7839 2 0
SCOTT 7788 7566 3 0
ADAMS 7876 7788 4 0
KING 7839 7566 3 1
FORD 7902 7566 3 0
SMITH 7369 7902 4 0
BLAKE 7698 7839 2 0
ALLEN 7499 7698 3 0
WARD 7521 7698 3 0
MARTIN 7654 7698 3 0
TURNER 7844 7698 3 0
JAMES 7900 7698 3 0
CLARK 7782 7839 2 0
MILLER 7934 7782 3 0
15 rows selected.
But there is a clear difference here: the recursive with clause cannot spot the cycle, until it has processed another recursion level. So you'll see KING repeated here, and the is_cycle attribute is set to '1' at one level lower than the CONNECT_BY_ISCYCLE pseudocolumn did. Quassnoi provided a nice answer to my Stack Overflow question about this topic. He states:
CONNECT_BY_ISCYCLE checks the children (which are yet to be returned), while CYCLE checks the current row (which is already returned).
CONNECT BY is row based, while recursive CTE's are set-based.
I think the results of the recursive with clause are somewhat counterintuitive, but I have heard several people stating otherwise. No matter what anyone thinks, what matters is to be aware there is a difference.
Calculate using previously calculated values
In part three of my SQL Model Clause Tutorial, I used this example of a simplified financial product of which I want to calculate the balance at the end of each year:
rwijk@ORA11GR2> select * from deposits
2 /
CUSTOMER AMOUNT THE_DATE
---------- ---------- -------------------
1 1000 01-01-2003 00:00:00
1 200 01-01-2004 00:00:00
1 500 01-01-2005 00:00:00
1 100 01-01-2006 00:00:00
1 800 01-01-2007 00:00:00
2 20 01-01-2003 00:00:00
2 150 01-01-2004 00:00:00
2 60 01-01-2005 00:00:00
2 100 01-01-2006 00:00:00
2 100 01-01-2007 00:00:00
10 rows selected.
rwijk@ORA11GR2> select * from interest_rates
2 /
THE_DATE PERCENTAGE
------------------- ----------
01-01-2003 00:00:00 5
01-01-2004 00:00:00 3.2
01-01-2005 00:00:00 4.1
01-01-2006 00:00:00 5.8
01-01-2007 00:00:00 4.9
5 rows selected.
rwijk@ORA11GR2> select customer
2 , amount
3 , the_date
4 , percentage
5 , balance balance_at_end_of_year
6 from deposits s
7 , interest_rates r
8 where s.the_date = r.the_date
9 model
10 partition by (s.customer)
11 dimension by (s.the_date)
12 measures (s.amount, r.percentage, 0 balance)
13 rules
14 ( balance[any] order by the_date
15 = round
16 ( (nvl(balance[add_months(cv(),-12)],0) + amount[cv()])
17 * (1 + percentage[cv()]/100)
18 , 2
19 )
20 )
21 order by customer
22 , the_date
23 /
CUSTOMER AMOUNT THE_DATE PERCENTAGE BALANCE_AT_END_OF_YEAR
---------- ---------- ------------------- ---------- ----------------------
1 1000 01-01-2003 00:00:00 5 1050
1 200 01-01-2004 00:00:00 3.2 1290
1 500 01-01-2005 00:00:00 4.1 1863.39
1 100 01-01-2006 00:00:00 5.8 2077.27
1 800 01-01-2007 00:00:00 4.9 3018.26
2 20 01-01-2003 00:00:00 5 21
2 150 01-01-2004 00:00:00 3.2 176.47
2 60 01-01-2005 00:00:00 4.1 246.17
2 100 01-01-2006 00:00:00 5.8 366.25
2 100 01-01-2007 00:00:00 4.9 489.1
10 rows selected.
Here 1050 = (1000 * 1.05), and 1290 = (1050 + 200) * 1.032. In other words, you need the calculated value of the previous step to calculate the new balance. You can produce this exact result with the recursive with clause like this:
rwijk@ORA11GR2> with t as
2 ( select s.customer
3 , r.the_date
4 , 1 + r.percentage/100 factor
5 , s.amount
6 from deposits s
7 , interest_rates r
8 where s.the_date = r.the_date
9 )
10 , t_recursive (customer,the_date,amount) as
11 ( select customer
12 , min(the_date)
13 , min(amount * factor) keep (dense_rank first order by the_date)
14 from t
15 group by customer
16 union all
17 select t.customer
18 , t.the_date
19 , round((tr.amount + t.amount) * t.factor,2)
20 from t
21 , t_recursive tr
22 where tr.customer = t.customer
23 and tr.the_date = t.the_date - interval '1' year
24 )
25 select *
26 from t_recursive
27 order by customer
28 , the_date
29 /
CUSTOMER THE_DATE AMOUNT
---------- ------------------- ----------
1 01-01-2003 00:00:00 1050
1 01-01-2004 00:00:00 1290
1 01-01-2005 00:00:00 1863.39
1 01-01-2006 00:00:00 2077.27
1 01-01-2007 00:00:00 3018.26
2 01-01-2003 00:00:00 21
2 01-01-2004 00:00:00 176.47
2 01-01-2005 00:00:00 246.17
2 01-01-2006 00:00:00 366.25
2 01-01-2007 00:00:00 489.1
10 rows selected.
The first with clause is a regular one, to only do the join once. And as you can see, combining those clauses is not a problem, although you can't use two recursive with clauses in one statement. The first union all part selects the balance for each customer at the end of their first year (2003). The second part uses recursion to get the other years. The point here is that you can use the expression round((tr.amount + t.amount) * t.factor,2), referencing tr.amount, which is a calculated value. With the connect-by clause you can select PRIOR [column_name], but you cannot select PRIOR [calculated_value]. So what used to be impossible with the connect-by, is now possible with the recursive-with (for people who don't like the model clause that is :-) ). So recursive-with is more powerful.
Performance
Let's check how our running example query performs:
rwijk@ORA11GR2> select /*+ gather_plan_statistics */
2 lpad(' ', 2 * level - 2, ' ') || ename as ename
3 , empno
4 , mgr
5 , level
6 from emp
7 connect by mgr = prior empno
8 start with mgr is null
9 /
ENAME EMPNO MGR LEVEL
-------------------- ---------- ---------- ----------
KING 7839 1
JONES 7566 7839 2
SCOTT 7788 7566 3
ADAMS 7876 7788 4
FORD 7902 7566 3
SMITH 7369 7902 4
BLAKE 7698 7839 2
ALLEN 7499 7698 3
WARD 7521 7698 3
MARTIN 7654 7698 3
TURNER 7844 7698 3
JAMES 7900 7698 3
CLARK 7782 7839 2
MILLER 7934 7782 3
14 rows selected.
rwijk@ORA11GR2> select * from table
2 (dbms_xplan.display_cursor(null,null,'basic iostats last'))
3 /
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------
EXPLAINED SQL STATEMENT:
------------------------
select /*+ gather_plan_statistics */ lpad(' ', 2 * level - 2,
' ') || ename as ename , empno , mgr , level from
emp connect by mgr = prior empno start with mgr is null
Plan hash value: 763482334
--------------------------------------------------------------------------------
--------------------------
| Id | Operation | Name | Starts | E-Rows | A-Row
s | A-Time | Buffers |
--------------------------------------------------------------------------------
--------------------------
| 0 | SELECT STATEMENT | | 1 | | 1
4 |00:00:00.01 | 7 |
|* 1 | CONNECT BY NO FILTERING WITH START-WITH| | 1 | | 1
4 |00:00:00.01 | 7 |
| 2 | TABLE ACCESS FULL | EMP | 1 | 14 | 1
4 |00:00:00.01 | 7 |
--------------------------------------------------------------------------------
--------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("MGR"=PRIOR NULL)
filter("MGR" IS NULL)
22 rows selected.
Just one full table access. A nice optimization for this kind of query. Here you can see how the plan looked like in previous versions. Probably the cost based optimizer realizes that no row can appear more than once in the output - else it would be a cycle - and thus it doesn't necessarily need the "connect-by-pump" access path.
Here is how the plan of the recursive with clause looks like:
rwijk@ORA11GR2> with emps (ename,empno,mgr,lvl) as
2 ( select ename
3 , empno
4 , mgr
5 , 1
6 from emp
7 where mgr is null
8 union all
9 select emp.ename
10 , emp.empno
11 , emp.mgr
12 , emps.lvl + 1
13 from emp
14 join emps on (emp.mgr = emps.empno)
15 ) search depth first by empno set a
16 select /*+ gather_plan_statistics */
17 lpad(' ', 2 * lvl - 2, ' ') || ename as ename
18 , empno
19 , mgr
20 , lvl
21 from emps
22 /
ENAME EMPNO MGR LVL
-------------------- ---------- ---------- ----------
KING 7839 1
JONES 7566 7839 2
SCOTT 7788 7566 3
ADAMS 7876 7788 4
FORD 7902 7566 3
SMITH 7369 7902 4
BLAKE 7698 7839 2
ALLEN 7499 7698 3
WARD 7521 7698 3
MARTIN 7654 7698 3
TURNER 7844 7698 3
JAMES 7900 7698 3
CLARK 7782 7839 2
MILLER 7934 7782 3
14 rows selected.
rwijk@ORA11GR2> select * from table
2 (dbms_xplan.display_cursor(null,null,'basic iostats last'))
3 /
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------
EXPLAINED SQL STATEMENT:
------------------------
with emps (ename,empno,mgr,lvl) as ( select ename , empno
, mgr , 1 from emp where mgr is null union all
select emp.ename , emp.empno , emp.mgr , emps.lvl
+ 1 from emp join emps on (emp.mgr = emps.empno) ) search
depth first by empno set a select /*+ gather_plan_statistics */
lpad(' ', 2 * lvl - 2, ' ') || ename as ename , empno , mgr
, lvl from emps
Plan hash value: 3907725112
--------------------------------------------------------------------------------
--------------------------
| Id | Operation | Name | Starts | E-Rows | A-Row
s | A-Time | Buffers |
--------------------------------------------------------------------------------
--------------------------
| 0 | SELECT STATEMENT | | 1 | | 1
4 |00:00:00.01 | 35 |
| 1 | VIEW | | 1 | 3 | 1
4 |00:00:00.01 | 35 |
| 2 | UNION ALL (RECURSIVE WITH) DEPTH FIRST| | 1 | | 1
4 |00:00:00.01 | 35 |
|* 3 | TABLE ACCESS FULL | EMP | 1 | 1 |
1 |00:00:00.01 | 7 |
|* 4 | HASH JOIN | | 4 | 2 | 1
3 |00:00:00.01 | 28 |
| 5 | RECURSIVE WITH PUMP | | 4 | | 1
4 |00:00:00.01 | 0 |
|* 6 | TABLE ACCESS FULL | EMP | 4 | 13 | 5
2 |00:00:00.01 | 28 |
--------------------------------------------------------------------------------
--------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - filter("MGR" IS NULL)
4 - access("EMP"."MGR"="EMPS"."EMPNO")
6 - filter("EMP"."MGR" IS NOT NULL)
31 rows selected.
In this plan, step 3 represents the first part of the union all (the start with). Steps 4 to 6 are executed as much times as there are levels; 4 in this case (note the "Starts" column!) and in step 2 the results are put together. It is like you write the query. But it's not optimized in the same way as the connect-by query is. In this case it's five times slower. Mind you, I'm not saying: don't ever use this technique because of performance. Just mentioning that there are differences that you should be aware of when writing a hierarchical query.
I'd like to end with two special "use cases":
1) Remember the First International NoCOUG SQL Challenge? You can solve it with the recursive with clause.
2) And you can even solve sudoku's with it.
Rob,
ReplyDelete(Once again) Thanks for nice detailed blog post with examples. Reading your posts is always a treat (and also shifts my goal-post further away... :) ).
Does this recursive subquery feature achieve anything that CONNECT BY and MODEL clause can not do? I think MODEL feature release was a revolution (well, you have proved it with your examples).
Hi Rob,
ReplyDeleteIt's Quassnoi of Stack Overflow.
I wondered if the recursive CTE's in Oracle 11g are really set-based?
In SQL Server, they are only allowed against set operations that distribute over UNION ALL and, hence, just copy the CONNECT BY abilities (though unlike CONNECT BY, you can reference the expressions computed on the previous steps).
PostgreSQL, on the other hand, implements them in truly set-based way.
It would be nice to know how does Oracle implement them. A query similar to the ROW_NUMBER query in this post could easily reveal the truth.
Hi Narendra,
ReplyDeleteThe recursive subquery factoring does not open up new ranges of questions that can now be answered. With the introduction of MODEL, the language has already become complete. But it provides new ways to achieve your goal, which are sometimes easier or more elegant than with other methods. For example, compare the sudoku solvers using the model clause and the recursive with clause. The latter is A LOT easier ...
Regards,
Rob.
Hi Alex,
ReplyDeleteUsing the ROW_NUMBER analytic function in the recursion part, leads to the error message ORA-32486.
ORA-32486: unsupported operation in recursive branch of recursive WITH clause
Cause: The recursive component of the UNION ALL in a recursive WITH clause element used an operation that was currently not supported. The following should not be used in the recursive branch of the UNION ALL operation: GROUP BY, DISTINCT, MODEL, grouping sets, CONNECT BY, window functions, HAVING, aggregate functions.
Action: Rewrite the query without the unsupported operation.
Regards,
Rob.
Hi, Rob.
ReplyDeleteIt seems that Oracle does not implement a set-based approach to recursion as well. That's a pity.
Anyway, thanks for trying it out!
Hi Rob,
ReplyDeleteLast few days I was googling to find out a solution for my problem in creating a hierarchical tree.
My scenario is:
I have a table called tb_emp which contains emp_code, emp_name.
From the Form, the user will enter emp_name (or any part of it). The query should return all the rows which contains that text and its child and parent. ie, if he entered JONES then, query should return all the employees under JONES and all the managers who comes in JONES's hierarchy. Can u pls help me in this case...
Quassnoi's explanation of cycle detection in recursive subquery factoring, as being based on a "set" concept of ancestry, is indeed nice, but I believe it is wrong. I posted a counter-example there (stackoverflow.com); here it is. Note that the output has two copies of the same row, one coming from the anchor member and one from the recursive member. If the "set-based" explanation were correct, the copy coming from the recursive member should have CYCLE = '1', but in fact it does not.
ReplyDelete`with
t(parent, child) as (
select 1, 2 from dual union all
select 1, 3 from dual union all
select 2, 3 from dual
),
r (parent, child) as (
select parent, child from t where parent = 1
union all
select r.parent, t.child from t join r on t.parent = r.child
)
cycle parent, child set cycle to '1' default '0'
select * from r;
PARENT CHILD CYCLE
------ ----- -----
1 2 0
1 3 0
1 3 0
I am still trying to figure out the correct definition of "cycle" for recursive factored subqueries - I don't know how ancestry is defined. Too bad it's not clearly documented.
In reply to mathguy, the 1/3 row from the recursive branch is not descended from 1/3 in the anchor, but from 1/2, so it isn't really a cycle row.
ReplyDeleteThe anchor branch might best be considered as a partitioning, with recursion proceeding independently for each partition, and the cycle column being set accordingly.
with
t(parent, child) as (
select 1, 2 from dual union all
select 1, 3 from dual union all
select 2, 3 from dual
),
r (parent, child, lev, root) as (
select parent, child, 0, parent || '/' || child from t where parent = 1
union all
select r.parent, t.child, lev+1, root from t join r on t.parent = r.child
)
cycle parent, child set cycle to '1' default '0'
select * from r
PARENT CHILD LEV ROOT CYCLE
1 3 0 1/3 0
1 2 0 1/2 0
1 3 1 1/2 0