How Does a Recursive Cte Run, Line by Line

How does a Recursive CTE run, line by line?

Think of a recursive CTE as of an endless UNION ALL:

WITH    rows AS
        (
        SELECT  *
        FROM    mytable
        WHERE   anchor_condition
        ),
        rows2 AS
        (
        SELECT  *
        FROM    set_operation(mytable, rows)
        ),
        rows3 AS
        (
        SELECT  *
        FROM    set_operation(mytable, rows2)
        ),
        …
SELECT  *
FROM    rows
UNION ALL
SELECT  *
FROM    rows2
UNION ALL
SELECT  *
FROM    rows3
UNION ALL
…

In your case, that would be:

WITH    abcd1 AS
        ( 
        SELECT  *
        FROM    @tbl t
        WHERE   ParentId IS NULL 
        ),
        abcd2 AS
        ( 
        SELECT  t.*
        FROM    abcd1
        JOIN    @tbl t
        ON      t.ParentID = abcd1.id
        ),
        abcd3 AS
        ( 
        SELECT  t.*
        FROM    abcd2
        JOIN    @tbl t
        ON      t.ParentID = abcd2.id
        ),
        abcd4 AS
        ( 
        SELECT  t.*
        FROM    abcd3
        JOIN    @tbl t
        ON      t.ParentID = abcd3.id
        ),
        abcd5 AS
        ( 
        SELECT  t.*
        FROM    abcd4
        JOIN    @tbl t
        ON      t.ParentID = abcd4.id
        ),
        abcd6 AS
        ( 
        SELECT  t.*
        FROM    abcd5
        JOIN    @tbl t
        ON      t.ParentID = abcd5.id
        )
SELECT  *
FROM    abcd1
UNION ALL
SELECT  *
FROM    abcd2
UNION ALL
SELECT  *
FROM    abcd3
UNION ALL
SELECT  *
FROM    abcd4
UNION ALL
SELECT  *
FROM    abcd5
UNION ALL
SELECT  *
FROM    abcd6

Since abcd6 yields no results, this implies a stopping condition.

Theoretically, a recursive CTE can be infinite, but practically, SQL Server tries to forbid the queries that would lead to infinite recordsets.

You may want to read this article:

SQL Server: are the recursive CTE’s really set-based?

What is the flow of control of recursive cte methods in SQL?

It is stated in the documentation that the recursion terminates once the result set is empty. I am not able to understand at what step of the flow will the recurion terminate.

Let's have a look at the recursive part of the CTE:

select a.employee_id 
from employees a 
inner join cte b on b.employee_id = a.manager_id

When does this return no rows? When there is no employee whose manager_id is equal to the employee_id of cte.

Basically, the query walks a hierarchical structure: at each step, it brings the managees of the current employee. When the current employee is not managing any employee, the recursive part comes back empty, and the recursion stops.

How does this recursive SQL CTE work exactly?

Your query, when properly fixed, generates a list of primes below 1000:

WITH recursive n(n) AS (
  SELECT 2 n
  UNION ALL
  SELECT n+1 FROM n WHERE n<1000
)
SELECT a.n
FROM n a
  LEFT JOIN n b
  ON b.n <= sqrt(a.n)                        -- Fix #1
GROUP BY a.n
HAVING a.n=2 OR a.n=3 OR MIN(a.n % b.n) > 0  -- Fix #2
ORDER BY a.n ASC

Demo.

The explanation is rather straightforward: the recursive part of your query is simply a way to give you a list of numbers from 2, inclusive, to 1000, exclusive. You could replace the recursive clause with an actual table populated with consecutive integer numbers.

These numbers are then fed into the non-CTE part of your query, and joined to themselves on the condition b.n < sqrt(a.n). The a side represents candidate primes; the b side represents candidate divisors.

Here is the first error in your query: < must be changed to <=, otherwise square roots of prime squares would be included into the output.

The GROUP BY groups potential primes with its candidate divisors into a single group. HAVING clause drops everything with one or more candidate divisors dividing the candidate prime evenly, i.e. where MIN(a.n % b.n) is zero.

This is where you need a second fix, because the square root of 3, a prime number, is less than 2, the smallest candidate divisor on the list. Hence, 3 ends up with no candidate divisors at all, and get thrown out by HAVING clause; you need to add OR a.n=3 to preserve it.

Understanding steps of recursive CTE

Each time the second half of the CTE runs, it sees only the results of the previous run. So the initial run executes the top half and yields 1. The second run executes the bottom half. It sees t as containing 1, so it returns 2. The third run sees t as containing 2 (not 1 and 2, because it only sees the results of the previous run), so it returns 3.

The fourth run sees 3 and returns 4.

The fifth run sees 4 and returns 5.

The sixth run sees 5, but that is excluded by the WHERE clause, so it returns no rows. Returning no rows is the signal to stop.

So now the complete result of the CTE is 1, 2, 3, 4, 5, which is what everything outside the CTE sees.

SQL Server CTE and recursion example

I haven't tested your code, just tried to help you understand how it operates in comment;

WITH
  cteReports (EmpID, FirstName, LastName, MgrID, EmpLevel)
  AS
  (
-->>>>>>>>>>Block 1>>>>>>>>>>>>>>>>>
-- In a rCTE, this block is called an [Anchor]
-- The query finds all root nodes as described by WHERE ManagerID IS NULL
    SELECT EmployeeID, FirstName, LastName, ManagerID, 1
    FROM Employees
    WHERE ManagerID IS NULL
-->>>>>>>>>>Block 1>>>>>>>>>>>>>>>>>
    UNION ALL
-->>>>>>>>>>Block 2>>>>>>>>>>>>>>>>>    
-- This is the recursive expression of the rCTE
-- On the first "execution" it will query data in [Employees],
-- relative to the [Anchor] above.
-- This will produce a resultset, we will call it R{1} and it is JOINed to [Employees]
-- as defined by the hierarchy
-- Subsequent "executions" of this block will reference R{n-1}
    SELECT e.EmployeeID, e.FirstName, e.LastName, e.ManagerID,
      r.EmpLevel + 1
    FROM Employees e
      INNER JOIN cteReports r
        ON e.ManagerID = r.EmpID
-->>>>>>>>>>Block 2>>>>>>>>>>>>>>>>>
  )
SELECT
  FirstName + ' ' + LastName AS FullName,
  EmpLevel,
  (SELECT FirstName + ' ' + LastName FROM Employees
    WHERE EmployeeID = cteReports.MgrID) AS Manager
FROM cteReports
ORDER BY EmpLevel, MgrID

The simplest example of a recursive CTE I can think of to illustrate its operation is;

;WITH Numbers AS
(
    SELECT n = 1
    UNION ALL
    SELECT n + 1
    FROM Numbers
    WHERE n+1 <= 10
)
SELECT n
FROM Numbers

Q 1) how value of N is getting incremented. if value is assign to N every time then N value can be incremented but only first time N value was initialize.

A1: In this case, N is not a variable. N is an alias. It is the equivalent of SELECT 1 AS N. It is a syntax of personal preference. There are 2 main methods of aliasing columns in a CTE in T-SQL. I've included the analog of a simple CTE in Excel to try and illustrate in a more familiar way what is happening.

--  Outside
;WITH CTE (MyColName) AS
(
    SELECT 1
)
-- Inside
;WITH CTE AS
(
    SELECT 1 AS MyColName
    -- Or
    SELECT MyColName = 1  
    -- Etc...
)

Excel_CTE

Q 2) now here about CTE and recursion of employee relation
the moment i add two manager and add few more employee under second manager then problem start.
i want to display first manager detail and in the next rows only those employee details will come those who are subordinate of that manager

A2:

Does this code answer your question?

--------------------------------------------
-- Synthesise table with non-recursive CTE
--------------------------------------------
;WITH Employee (ID, Name, MgrID) AS 
(
    SELECT 1,      'Keith',      NULL   UNION ALL
    SELECT 2,      'Josh',       1      UNION ALL
    SELECT 3,      'Robin',      1      UNION ALL
    SELECT 4,      'Raja',       2      UNION ALL
    SELECT 5,      'Tridip',     NULL   UNION ALL
    SELECT 6,      'Arijit',     5      UNION ALL
    SELECT 7,      'Amit',       5      UNION ALL
    SELECT 8,      'Dev',        6   
)
--------------------------------------------
-- Recursive CTE - Chained to the above CTE
--------------------------------------------
,Hierarchy AS
(
    --  Anchor
    SELECT   ID
            ,Name
            ,MgrID
            ,nLevel = 1
            ,Family = ROW_NUMBER() OVER (ORDER BY Name)
    FROM Employee
    WHERE MgrID IS NULL

    UNION ALL
    --  Recursive query
    SELECT   E.ID
            ,E.Name
            ,E.MgrID
            ,H.nLevel+1
            ,Family
    FROM Employee   E
    JOIN Hierarchy  H ON E.MgrID = H.ID
)
SELECT *
FROM Hierarchy
ORDER BY Family, nLevel

Another one sql with tree structure

SELECT ID,space(nLevel+
                    (CASE WHEN nLevel > 1 THEN nLevel ELSE 0 END)
                )+Name
FROM Hierarchy
ORDER BY Family, nLevel

How Does a Recursive Cte Run, Line by Line