I've been reading up on the inner workings of CTE Recursion and I'm still not quite sure how SQL Server is implementing the Anchor element in their source code and how SQL Server Query Execution Engine / Query Optimizer is then interpreting those instruction sets.
I read through the following article very carefully to follow the logic: http://sqlchitchat.com/sqldev/tsql/recursive-cte/
Let's take Example 1 from said article: https://github.com/dmincic/SQLCHITCHAT/blob/master/CTE/Sql/Example1_cteQuery.sql
DECLARE @EmpId INT = 3;
;WITH cte1 AS
(
-- Anchor Element
SELECT EmpId
,MgrId
FROM dbo.Employees
WHERE MgrId = @EmpId
UNION ALL
-- Recursive Element
SELECT e.EmpId
,e.MgrId
FROM dbo.Employees e
INNER JOIN cte1 c
ON e.MgrId = c.EmpId
)
-- Invoke CTE Recursion
SELECT cte1.EmpId
,cte1.MgrId
FROM cte1;
If you scroll down to about the middle of the article, it talks about the role of the anchor element in the 2nd iteration / 1st recursion:
The second iteration begins.This is the first recursion. The anchor part played its part in the first iteration and from now on returns only empty sets. However, the recursive part can now reference it’s previous result(cte1 value after the first iteration) in the INNER JOIN operator. The table operation produces the result of the second iteration as shown in the figure below.
Figure 5: https://sqlchitchat.com/wp-content/uploads/2019/10/2nd_Iteration1.png
In the Figure, you can see the empty set (well, tuple) drawn out for EmpId and MgrId.
Then I read through How does SQL recursion actually work? and it appears, from the answers provided, the Anchor Element is not even evaluated for N+1 iterations.
So, which one is it then? Is the QE/QO evaluating the Anchor on every iteration and, somehow, it returns an empty tuple during recursion or is the Anchor being skipped outright during recursion and, thus, it would never return an empty tuple?
To clarify my question, here's what I'm asking: Does the underlying code resemble this:
static void Main(string[] args)
{
int Number = 0;
long Result;
// Anchor part
Number = GetNumberFromProgramArguments();
// Anchor part is only executed once
// Recursive part
Result = CalculateFactorial(Number);
}
public static long CalculateFactorial(int number)
{
// Termination check
if (number == 0)
return 1;
// Recursive call
return number * CalculateFactorial(number - 1);
}
Or is it more like this:
static void Main(string[] args)
{
int Number = 0;
long Result;
int RecursionLevel = 0;
// Recursive part
Result = CalculateFactorial(Number, RecursionLevel);
}
public static long CalculateFactorial(int number, int recursionLevel)
{
// Run Anchor part only if Recursion Level is 0
if (recursionLevel == 0)
// Anchor part
number = GetNumberFromProgramArguments();
// Termination check
if (number == 0)
return 1;
// Increment recursion
recursionLevel++;
// Recursive call
return number * CalculateFactorial(number - 1, recursionLevel);
}
It's not the greatest example because I've been focusing on tables, not numbers, but I hope you get my point. Why is the article stating that the Anchor is being evaluated and returned as an empty tuple during recursion? That's where I'm getting confused here. It doesn't make sense. The SQL Execution plan doesn't show the Anchor part being evaluated for N+1 iterations, just the very first iteration. And if that's the case, then the anchor part would never return anything during recursion because execution never reaches that part of the code again to even evaluate the anchor. I don't understand why Figure 5 is showing anchor being evaluated as an empty tuple during recursion. It shouldn't even show anything.
Yes, I understand that recursion is grabbing the previous iteration, if it's available. But from Figure 5 and from the paragraph I quoted, the blog is stating that the anchor executes every iteration and returns an empty tuple for the recursion part, which is not evident from the SQL Execution Plan. The Execution Plan shows the Anchor executing once and never again. Do you see why I'm getting confused here?
