0

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

FIgure 5, cte1 value after 2nd iteration

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?

0

1 Answer 1

2

What you are referring to as anchor part will only be evaluated once. You can compare that to the base case in an induction proof. This can be illustrated with a trivial example:

with t (n,origin) as ( 
  select 1, 'Anchor   '
  union all
  select n+1, 'Recursive'
  from t where n<10
)
select * from t;

n   origin
1   Anchor
2   Recursive
3   Recursive
4   Recursive
5   Recursive
6   Recursive
7   Recursive
8   Recursive
9   Recursive
10  Recursive

If the anchor part where evaluated several times it would be part of the result, since there is no predicate that can be evaluated to false

Fiddle

3
  • Yes, that's what I would expect, as well. From the blog: "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." Then the blog is incorrect, because the code would never evaluate the anchor again during recursion. It not only wouldn't return empty sets, it wouldn't return anything period because it's only evaluated during the first iteration. Feb 14, 2023 at 20:53
  • In the blog, they're basically stating: if (iteration >= 2) { anchor = {}; recursionResult = doRecursion(); return anchor + recursionResult; }...combining that empty tuple with the recursive tuple which yields just the recursive tuple as the final result for the iteration, send it the buffer, and then proceed to the next iteration. And what I was unclear about was, OK, why would the code even evaluate the anchor again during recursion, as the blog seems to more than imply here. Feb 14, 2023 at 20:59
  • 1
    I must admit I did not read the blog very carefully, but I think it is important to distinguish between what is actually happening, and a model that tries to explain what is happening. Being closed source, we will never know for sure but I would be very surprised if the code actually returned the empty set for each iteration when it does not have to. I suppose one could debug the process and find indications to whether that is true, but I believe it would be a tedious work. Feb 15, 2023 at 6:43

Your Answer

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

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