How does SQL recursion actually work?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP












18















Coming to SQL from other programming languages, the structure of a recursive query looks rather odd. Walk through it step by step, and it seems to fall apart.



Consider the following simple example:



CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
SELECT N FROM #NUMS
UNION ALL
SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Let's walk through it.



First, the anchor member executes and the result set is put into R. So R is initialized to 3, 5, 7.



Then, execution drops below the UNION ALL and the recursive member is executed for the first time. It executes on R (that is, on the R that we currently have in hand: 3, 5, 7). This results in 9, 25, 49.



What does it do with this new result? Does it append 9, 25, 49 to the existing 3, 5, 7, label the resulting union R, and then carry on with the recursion from there? Or does it redefine R to be only this new result 9, 25, 49 and do all the union-ing later?



Neither choice makes sense.



If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7.



If R is now only 9, 25, 49, then we have a mislabeling problem. R is understood to be the union of the anchor member result set and all the subsequent recursive member result sets. Whereas 9, 25, 49 is only a component of R. It is not the full R that we have accrued so far. Therefore, to write the recursive member as selecting from R makes no sense.




I certainly appreciate what @Max Vernon and @Michael S. have detailed below. Namely, that (1) all the components are created up to the recursion limit or null set, and then (2) all the components are unioned together. This is how I understand SQL recursion to actually work.



If we were redesigning SQL, maybe we would enforce a more clear and explicit syntax, something like this:



WITH R AS
(
SELECT N
INTO R[0]
FROM #NUMS
UNION ALL
SELECT N*N AS N
INTO R[K+1]
FROM R[K]
WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Sort of like an inductive proof in mathematics.



The problem with SQL recursion as it currently stands is that it is written in a confusing way. The way it is written says that each component is formed by selecting from R, but it does not mean the full R that has been (or, appears to have been) constructed so far. It just means the previous component.










share|improve this question
























  • "If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7." I don't see how you lose 3,5,7 if it works like that.

    – ypercubeᵀᴹ
    Jan 11 at 22:22











  • @yper-crazyhat-cubeᵀᴹ — I was following on from the first hypothesis that I proposed, namely, what if the intermediate R is an accumulation of everything that had been calculated up to that point? Then, at the next iteration of the recursive member, every element of R is squared. Thus, 3, 5, 7 becomes 9, 25, 49 and we never again have 3, 5, 7 in R. In other words, 3, 5, 7 is lost from R.

    – UnLogicGuys
    Jan 14 at 19:36















18















Coming to SQL from other programming languages, the structure of a recursive query looks rather odd. Walk through it step by step, and it seems to fall apart.



Consider the following simple example:



CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
SELECT N FROM #NUMS
UNION ALL
SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Let's walk through it.



First, the anchor member executes and the result set is put into R. So R is initialized to 3, 5, 7.



Then, execution drops below the UNION ALL and the recursive member is executed for the first time. It executes on R (that is, on the R that we currently have in hand: 3, 5, 7). This results in 9, 25, 49.



What does it do with this new result? Does it append 9, 25, 49 to the existing 3, 5, 7, label the resulting union R, and then carry on with the recursion from there? Or does it redefine R to be only this new result 9, 25, 49 and do all the union-ing later?



Neither choice makes sense.



If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7.



If R is now only 9, 25, 49, then we have a mislabeling problem. R is understood to be the union of the anchor member result set and all the subsequent recursive member result sets. Whereas 9, 25, 49 is only a component of R. It is not the full R that we have accrued so far. Therefore, to write the recursive member as selecting from R makes no sense.




I certainly appreciate what @Max Vernon and @Michael S. have detailed below. Namely, that (1) all the components are created up to the recursion limit or null set, and then (2) all the components are unioned together. This is how I understand SQL recursion to actually work.



If we were redesigning SQL, maybe we would enforce a more clear and explicit syntax, something like this:



WITH R AS
(
SELECT N
INTO R[0]
FROM #NUMS
UNION ALL
SELECT N*N AS N
INTO R[K+1]
FROM R[K]
WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Sort of like an inductive proof in mathematics.



The problem with SQL recursion as it currently stands is that it is written in a confusing way. The way it is written says that each component is formed by selecting from R, but it does not mean the full R that has been (or, appears to have been) constructed so far. It just means the previous component.










share|improve this question
























  • "If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7." I don't see how you lose 3,5,7 if it works like that.

    – ypercubeᵀᴹ
    Jan 11 at 22:22











  • @yper-crazyhat-cubeᵀᴹ — I was following on from the first hypothesis that I proposed, namely, what if the intermediate R is an accumulation of everything that had been calculated up to that point? Then, at the next iteration of the recursive member, every element of R is squared. Thus, 3, 5, 7 becomes 9, 25, 49 and we never again have 3, 5, 7 in R. In other words, 3, 5, 7 is lost from R.

    – UnLogicGuys
    Jan 14 at 19:36













18












18








18


6






Coming to SQL from other programming languages, the structure of a recursive query looks rather odd. Walk through it step by step, and it seems to fall apart.



Consider the following simple example:



CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
SELECT N FROM #NUMS
UNION ALL
SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Let's walk through it.



First, the anchor member executes and the result set is put into R. So R is initialized to 3, 5, 7.



Then, execution drops below the UNION ALL and the recursive member is executed for the first time. It executes on R (that is, on the R that we currently have in hand: 3, 5, 7). This results in 9, 25, 49.



What does it do with this new result? Does it append 9, 25, 49 to the existing 3, 5, 7, label the resulting union R, and then carry on with the recursion from there? Or does it redefine R to be only this new result 9, 25, 49 and do all the union-ing later?



Neither choice makes sense.



If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7.



If R is now only 9, 25, 49, then we have a mislabeling problem. R is understood to be the union of the anchor member result set and all the subsequent recursive member result sets. Whereas 9, 25, 49 is only a component of R. It is not the full R that we have accrued so far. Therefore, to write the recursive member as selecting from R makes no sense.




I certainly appreciate what @Max Vernon and @Michael S. have detailed below. Namely, that (1) all the components are created up to the recursion limit or null set, and then (2) all the components are unioned together. This is how I understand SQL recursion to actually work.



If we were redesigning SQL, maybe we would enforce a more clear and explicit syntax, something like this:



WITH R AS
(
SELECT N
INTO R[0]
FROM #NUMS
UNION ALL
SELECT N*N AS N
INTO R[K+1]
FROM R[K]
WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Sort of like an inductive proof in mathematics.



The problem with SQL recursion as it currently stands is that it is written in a confusing way. The way it is written says that each component is formed by selecting from R, but it does not mean the full R that has been (or, appears to have been) constructed so far. It just means the previous component.










share|improve this question
















Coming to SQL from other programming languages, the structure of a recursive query looks rather odd. Walk through it step by step, and it seems to fall apart.



Consider the following simple example:



CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
SELECT N FROM #NUMS
UNION ALL
SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Let's walk through it.



First, the anchor member executes and the result set is put into R. So R is initialized to 3, 5, 7.



Then, execution drops below the UNION ALL and the recursive member is executed for the first time. It executes on R (that is, on the R that we currently have in hand: 3, 5, 7). This results in 9, 25, 49.



What does it do with this new result? Does it append 9, 25, 49 to the existing 3, 5, 7, label the resulting union R, and then carry on with the recursion from there? Or does it redefine R to be only this new result 9, 25, 49 and do all the union-ing later?



Neither choice makes sense.



If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7.



If R is now only 9, 25, 49, then we have a mislabeling problem. R is understood to be the union of the anchor member result set and all the subsequent recursive member result sets. Whereas 9, 25, 49 is only a component of R. It is not the full R that we have accrued so far. Therefore, to write the recursive member as selecting from R makes no sense.




I certainly appreciate what @Max Vernon and @Michael S. have detailed below. Namely, that (1) all the components are created up to the recursion limit or null set, and then (2) all the components are unioned together. This is how I understand SQL recursion to actually work.



If we were redesigning SQL, maybe we would enforce a more clear and explicit syntax, something like this:



WITH R AS
(
SELECT N
INTO R[0]
FROM #NUMS
UNION ALL
SELECT N*N AS N
INTO R[K+1]
FROM R[K]
WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;


Sort of like an inductive proof in mathematics.



The problem with SQL recursion as it currently stands is that it is written in a confusing way. The way it is written says that each component is formed by selecting from R, but it does not mean the full R that has been (or, appears to have been) constructed so far. It just means the previous component.







sql-server cte recursive






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Jan 12 at 1:41









LowlyDBA

6,98252542




6,98252542










asked Jan 11 at 19:49









UnLogicGuysUnLogicGuys

1497




1497












  • "If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7." I don't see how you lose 3,5,7 if it works like that.

    – ypercubeᵀᴹ
    Jan 11 at 22:22











  • @yper-crazyhat-cubeᵀᴹ — I was following on from the first hypothesis that I proposed, namely, what if the intermediate R is an accumulation of everything that had been calculated up to that point? Then, at the next iteration of the recursive member, every element of R is squared. Thus, 3, 5, 7 becomes 9, 25, 49 and we never again have 3, 5, 7 in R. In other words, 3, 5, 7 is lost from R.

    – UnLogicGuys
    Jan 14 at 19:36

















  • "If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7." I don't see how you lose 3,5,7 if it works like that.

    – ypercubeᵀᴹ
    Jan 11 at 22:22











  • @yper-crazyhat-cubeᵀᴹ — I was following on from the first hypothesis that I proposed, namely, what if the intermediate R is an accumulation of everything that had been calculated up to that point? Then, at the next iteration of the recursive member, every element of R is squared. Thus, 3, 5, 7 becomes 9, 25, 49 and we never again have 3, 5, 7 in R. In other words, 3, 5, 7 is lost from R.

    – UnLogicGuys
    Jan 14 at 19:36
















"If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7." I don't see how you lose 3,5,7 if it works like that.

– ypercubeᵀᴹ
Jan 11 at 22:22





"If R is now 3, 5, 7, 9, 25, 49 and we execute the next iteration of the recursion, then we will end up with 9, 25, 49, 81, 625, 2401 and we've lost 3, 5, 7." I don't see how you lose 3,5,7 if it works like that.

– ypercubeᵀᴹ
Jan 11 at 22:22













@yper-crazyhat-cubeᵀᴹ — I was following on from the first hypothesis that I proposed, namely, what if the intermediate R is an accumulation of everything that had been calculated up to that point? Then, at the next iteration of the recursive member, every element of R is squared. Thus, 3, 5, 7 becomes 9, 25, 49 and we never again have 3, 5, 7 in R. In other words, 3, 5, 7 is lost from R.

– UnLogicGuys
Jan 14 at 19:36





@yper-crazyhat-cubeᵀᴹ — I was following on from the first hypothesis that I proposed, namely, what if the intermediate R is an accumulation of everything that had been calculated up to that point? Then, at the next iteration of the recursive member, every element of R is squared. Thus, 3, 5, 7 becomes 9, 25, 49 and we never again have 3, 5, 7 in R. In other words, 3, 5, 7 is lost from R.

– UnLogicGuys
Jan 14 at 19:36










4 Answers
4






active

oldest

votes


















25














The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:



  1. Split the CTE expression into anchor and recursive members.

  2. Run the anchor member(s) creating the first invocation or base result set (T0).

  3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.

  4. Repeat step 3 until an empty set is returned.

  5. Return the result set. This is a UNION ALL of T0 to Tn.

So each level only has as input the level above not the entire result set accumulated so far.



The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here and means that in practice each recursive element is just working with the parent row from the previous level, not the whole level. But the various restrictions on allowable syntax in recursive CTEs mean this approach works.



If you remove the ORDER BY from your query the results are ordered as follows



+---------+
| N |
+---------+
| 3 |
| 5 |
| 7 |
| 49 |
| 2401 |
| 5764801 |
| 25 |
| 625 |
| 390625 |
| 9 |
| 81 |
| 6561 |
+---------+


This is because the execution plan operates very similarly to the following C#



using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program

private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

private static void Main(string args)

//temp table #NUMS
var nums = new 3, 5, 7 ;

//Anchor member
foreach (var number in nums)
AddToStackSpoolAndEmit(number, 0);

//Recursive part
ProcessStackSpool();

Console.WriteLine("Finished");
Console.ReadLine();


private static void AddToStackSpoolAndEmit(long number, int recursionLevel)

StackSpool.Push(new N = number, RecursionLevel = recursionLevel );
Console.WriteLine(number);


private static void ProcessStackSpool()

//recursion base case
if (StackSpool.Count == 0)
return;

var row = StackSpool.Pop();

int thisLevel = row.RecursionLevel + 1;
long thisN = row.N * row.N;

Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

if (thisN < 10000000)
AddToStackSpoolAndEmit(thisN, thisLevel);

ProcessStackSpool();




NB1: As above by the time the first child of anchor member 3 is being processed all information about its siblings, 5 and 7, and their descendants, has already been discarded from the spool and is no longer accessible.



NB2: The C# above has the same overall semantics as the execution plan but the flow in the execution plan is not identical, as there the operators work in a pipelined exection fashion. This is a simplified example to demonstrate the gist of the approach. See the earlier links for more details on the plan itself.






share|improve this answer




















  • 5





    Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

    – Paul White
    Jan 12 at 16:04











  • Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

    – Joshua
    Jan 12 at 16:59



















4














This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.



T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.



So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:



  1. 3,5,7 -> result set

  2. recursive statements applied to 3,5,7, which is 9,25,49. 9,25,49 is added to result set, and replaces the left side of the UNION ALL.

  3. recursive statements applied to 9,25,49, which is 81,625,2401. 81,625,2401 is added to result set, and replaces the left side of the UNION ALL.

  4. recursive statements applied to 81,625,2401, which is 6561,390625,5764801. 6561,390625,5764801 is added to result set.

  5. Cursor is complete, since next iteration results in the WHERE clause returning false.

You can see this behavior in the execution plan for the recursive CTE:



enter image description here



This is step 1 above, where the left side of the UNION ALL is added to the output:



enter image description here



This is the right side of the UNION ALL where the output is concatenated to the result set:



enter image description here






share|improve this answer
































    3














    The SQL Server documentation, which mentions Ti and Ti+1, is neither very understandable, nor an accurate description of the actual implementation.



    The basic idea is that the recursive part of the query looks at all previous results, but only once.



    It might be helpful to look how other databases implement this (to get the same result). The Postgres documentation says:




    Recursive Query Evaluation



    1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

    2. So long as the working table is not empty, repeat these steps:

      1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

      2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.


    Note

    Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.




    The SQLite documentation hints at a slightly different implementation, and this one-row-at-a-time algorithm might be the easiest to understand:




    The basic algorithm for computing the content of the recursive table is as follows:



    1. Run the initial-select and add the results to a queue.

    2. While the queue is not empty:

      1. Extract a single row from the queue.

      2. Insert that single row into the recursive table

      3. Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.


    The basic procedure above may modified by the following additional rules:



    • If a UNION operator connects the initial-select with the recursive-select, then only add rows to the queue if no identical row has been previously added to the queue. Repeated rows are discarded before being added to the queue even if the repeated rows have already been extracted from the queue by the recursion step. If the operator is UNION ALL, then all rows generated by both the initial-select and the recursive-select are always added to the queue even if they are repeats.

      […]






    share|improve this answer
































      0














      My knowledge is in DB2 specifically but looking at the explain diagrams seems to be the same with SQL Server.



      The plan comes from here:



      See it on Paste the Plan



      SQL Server Explain Plan



      The optimizer does not literally run a union all for each recursive query. It takes the structure of the query and assigns the first part of the union all to an "anchor member" then it will run through the second half of the union all (called the "recursive member" recursively until it reaches the limitations defined. After the recursion is complete, the optimizer joins all records together.



      The optimizer just takes it as a suggestion to do a pre-defined operation.






      share|improve this answer
























        Your Answer








        StackExchange.ready(function()
        var channelOptions =
        tags: "".split(" "),
        id: "182"
        ;
        initTagRenderer("".split(" "), "".split(" "), channelOptions);

        StackExchange.using("externalEditor", function()
        // Have to fire editor after snippets, if snippets enabled
        if (StackExchange.settings.snippets.snippetsEnabled)
        StackExchange.using("snippets", function()
        createEditor();
        );

        else
        createEditor();

        );

        function createEditor()
        StackExchange.prepareEditor(
        heartbeatType: 'answer',
        autoActivateHeartbeat: false,
        convertImagesToLinks: false,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: null,
        bindNavPrevention: true,
        postfix: "",
        imageUploader:
        brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
        contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
        allowUrls: true
        ,
        onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        );



        );













        draft saved

        draft discarded


















        StackExchange.ready(
        function ()
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdba.stackexchange.com%2fquestions%2f226946%2fhow-does-sql-recursion-actually-work%23new-answer', 'question_page');

        );

        Post as a guest















        Required, but never shown

























        4 Answers
        4






        active

        oldest

        votes








        4 Answers
        4






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        25














        The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:



        1. Split the CTE expression into anchor and recursive members.

        2. Run the anchor member(s) creating the first invocation or base result set (T0).

        3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.

        4. Repeat step 3 until an empty set is returned.

        5. Return the result set. This is a UNION ALL of T0 to Tn.

        So each level only has as input the level above not the entire result set accumulated so far.



        The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here and means that in practice each recursive element is just working with the parent row from the previous level, not the whole level. But the various restrictions on allowable syntax in recursive CTEs mean this approach works.



        If you remove the ORDER BY from your query the results are ordered as follows



        +---------+
        | N |
        +---------+
        | 3 |
        | 5 |
        | 7 |
        | 49 |
        | 2401 |
        | 5764801 |
        | 25 |
        | 625 |
        | 390625 |
        | 9 |
        | 81 |
        | 6561 |
        +---------+


        This is because the execution plan operates very similarly to the following C#



        using System;
        using System.Collections.Generic;
        using System.Diagnostics;

        public class Program

        private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

        private static void Main(string args)

        //temp table #NUMS
        var nums = new 3, 5, 7 ;

        //Anchor member
        foreach (var number in nums)
        AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();


        private static void AddToStackSpoolAndEmit(long number, int recursionLevel)

        StackSpool.Push(new N = number, RecursionLevel = recursionLevel );
        Console.WriteLine(number);


        private static void ProcessStackSpool()

        //recursion base case
        if (StackSpool.Count == 0)
        return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
        AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();




        NB1: As above by the time the first child of anchor member 3 is being processed all information about its siblings, 5 and 7, and their descendants, has already been discarded from the spool and is no longer accessible.



        NB2: The C# above has the same overall semantics as the execution plan but the flow in the execution plan is not identical, as there the operators work in a pipelined exection fashion. This is a simplified example to demonstrate the gist of the approach. See the earlier links for more details on the plan itself.






        share|improve this answer




















        • 5





          Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

          – Paul White
          Jan 12 at 16:04











        • Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

          – Joshua
          Jan 12 at 16:59
















        25














        The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:



        1. Split the CTE expression into anchor and recursive members.

        2. Run the anchor member(s) creating the first invocation or base result set (T0).

        3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.

        4. Repeat step 3 until an empty set is returned.

        5. Return the result set. This is a UNION ALL of T0 to Tn.

        So each level only has as input the level above not the entire result set accumulated so far.



        The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here and means that in practice each recursive element is just working with the parent row from the previous level, not the whole level. But the various restrictions on allowable syntax in recursive CTEs mean this approach works.



        If you remove the ORDER BY from your query the results are ordered as follows



        +---------+
        | N |
        +---------+
        | 3 |
        | 5 |
        | 7 |
        | 49 |
        | 2401 |
        | 5764801 |
        | 25 |
        | 625 |
        | 390625 |
        | 9 |
        | 81 |
        | 6561 |
        +---------+


        This is because the execution plan operates very similarly to the following C#



        using System;
        using System.Collections.Generic;
        using System.Diagnostics;

        public class Program

        private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

        private static void Main(string args)

        //temp table #NUMS
        var nums = new 3, 5, 7 ;

        //Anchor member
        foreach (var number in nums)
        AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();


        private static void AddToStackSpoolAndEmit(long number, int recursionLevel)

        StackSpool.Push(new N = number, RecursionLevel = recursionLevel );
        Console.WriteLine(number);


        private static void ProcessStackSpool()

        //recursion base case
        if (StackSpool.Count == 0)
        return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
        AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();




        NB1: As above by the time the first child of anchor member 3 is being processed all information about its siblings, 5 and 7, and their descendants, has already been discarded from the spool and is no longer accessible.



        NB2: The C# above has the same overall semantics as the execution plan but the flow in the execution plan is not identical, as there the operators work in a pipelined exection fashion. This is a simplified example to demonstrate the gist of the approach. See the earlier links for more details on the plan itself.






        share|improve this answer




















        • 5





          Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

          – Paul White
          Jan 12 at 16:04











        • Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

          – Joshua
          Jan 12 at 16:59














        25












        25








        25







        The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:



        1. Split the CTE expression into anchor and recursive members.

        2. Run the anchor member(s) creating the first invocation or base result set (T0).

        3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.

        4. Repeat step 3 until an empty set is returned.

        5. Return the result set. This is a UNION ALL of T0 to Tn.

        So each level only has as input the level above not the entire result set accumulated so far.



        The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here and means that in practice each recursive element is just working with the parent row from the previous level, not the whole level. But the various restrictions on allowable syntax in recursive CTEs mean this approach works.



        If you remove the ORDER BY from your query the results are ordered as follows



        +---------+
        | N |
        +---------+
        | 3 |
        | 5 |
        | 7 |
        | 49 |
        | 2401 |
        | 5764801 |
        | 25 |
        | 625 |
        | 390625 |
        | 9 |
        | 81 |
        | 6561 |
        +---------+


        This is because the execution plan operates very similarly to the following C#



        using System;
        using System.Collections.Generic;
        using System.Diagnostics;

        public class Program

        private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

        private static void Main(string args)

        //temp table #NUMS
        var nums = new 3, 5, 7 ;

        //Anchor member
        foreach (var number in nums)
        AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();


        private static void AddToStackSpoolAndEmit(long number, int recursionLevel)

        StackSpool.Push(new N = number, RecursionLevel = recursionLevel );
        Console.WriteLine(number);


        private static void ProcessStackSpool()

        //recursion base case
        if (StackSpool.Count == 0)
        return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
        AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();




        NB1: As above by the time the first child of anchor member 3 is being processed all information about its siblings, 5 and 7, and their descendants, has already been discarded from the spool and is no longer accessible.



        NB2: The C# above has the same overall semantics as the execution plan but the flow in the execution plan is not identical, as there the operators work in a pipelined exection fashion. This is a simplified example to demonstrate the gist of the approach. See the earlier links for more details on the plan itself.






        share|improve this answer















        The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:



        1. Split the CTE expression into anchor and recursive members.

        2. Run the anchor member(s) creating the first invocation or base result set (T0).

        3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.

        4. Repeat step 3 until an empty set is returned.

        5. Return the result set. This is a UNION ALL of T0 to Tn.

        So each level only has as input the level above not the entire result set accumulated so far.



        The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here and means that in practice each recursive element is just working with the parent row from the previous level, not the whole level. But the various restrictions on allowable syntax in recursive CTEs mean this approach works.



        If you remove the ORDER BY from your query the results are ordered as follows



        +---------+
        | N |
        +---------+
        | 3 |
        | 5 |
        | 7 |
        | 49 |
        | 2401 |
        | 5764801 |
        | 25 |
        | 625 |
        | 390625 |
        | 9 |
        | 81 |
        | 6561 |
        +---------+


        This is because the execution plan operates very similarly to the following C#



        using System;
        using System.Collections.Generic;
        using System.Diagnostics;

        public class Program

        private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

        private static void Main(string args)

        //temp table #NUMS
        var nums = new 3, 5, 7 ;

        //Anchor member
        foreach (var number in nums)
        AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();


        private static void AddToStackSpoolAndEmit(long number, int recursionLevel)

        StackSpool.Push(new N = number, RecursionLevel = recursionLevel );
        Console.WriteLine(number);


        private static void ProcessStackSpool()

        //recursion base case
        if (StackSpool.Count == 0)
        return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
        AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();




        NB1: As above by the time the first child of anchor member 3 is being processed all information about its siblings, 5 and 7, and their descendants, has already been discarded from the spool and is no longer accessible.



        NB2: The C# above has the same overall semantics as the execution plan but the flow in the execution plan is not identical, as there the operators work in a pipelined exection fashion. This is a simplified example to demonstrate the gist of the approach. See the earlier links for more details on the plan itself.







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Jan 12 at 13:03

























        answered Jan 11 at 23:56









        Martin SmithMartin Smith

        62.4k10169251




        62.4k10169251







        • 5





          Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

          – Paul White
          Jan 12 at 16:04











        • Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

          – Joshua
          Jan 12 at 16:59













        • 5





          Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

          – Paul White
          Jan 12 at 16:04











        • Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

          – Joshua
          Jan 12 at 16:59








        5




        5





        Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

        – Paul White
        Jan 12 at 16:04





        Recursive queries in SQL Server are always converted from recursion to iteration (with stacking) during parsing. The implementation rule for iteration is IterateToDepthFirst - Iterate(seed,rcsv)->PhysIterate(seed,rcsv). Just FYI. Excellent answer.

        – Paul White
        Jan 12 at 16:04













        Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

        – Joshua
        Jan 12 at 16:59






        Incidentally, UNION is also allowed instead of UNION ALL but SQL Server won't do it.

        – Joshua
        Jan 12 at 16:59














        4














        This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.



        T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.



        So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:



        1. 3,5,7 -> result set

        2. recursive statements applied to 3,5,7, which is 9,25,49. 9,25,49 is added to result set, and replaces the left side of the UNION ALL.

        3. recursive statements applied to 9,25,49, which is 81,625,2401. 81,625,2401 is added to result set, and replaces the left side of the UNION ALL.

        4. recursive statements applied to 81,625,2401, which is 6561,390625,5764801. 6561,390625,5764801 is added to result set.

        5. Cursor is complete, since next iteration results in the WHERE clause returning false.

        You can see this behavior in the execution plan for the recursive CTE:



        enter image description here



        This is step 1 above, where the left side of the UNION ALL is added to the output:



        enter image description here



        This is the right side of the UNION ALL where the output is concatenated to the result set:



        enter image description here






        share|improve this answer





























          4














          This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.



          T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.



          So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:



          1. 3,5,7 -> result set

          2. recursive statements applied to 3,5,7, which is 9,25,49. 9,25,49 is added to result set, and replaces the left side of the UNION ALL.

          3. recursive statements applied to 9,25,49, which is 81,625,2401. 81,625,2401 is added to result set, and replaces the left side of the UNION ALL.

          4. recursive statements applied to 81,625,2401, which is 6561,390625,5764801. 6561,390625,5764801 is added to result set.

          5. Cursor is complete, since next iteration results in the WHERE clause returning false.

          You can see this behavior in the execution plan for the recursive CTE:



          enter image description here



          This is step 1 above, where the left side of the UNION ALL is added to the output:



          enter image description here



          This is the right side of the UNION ALL where the output is concatenated to the result set:



          enter image description here






          share|improve this answer



























            4












            4








            4







            This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.



            T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.



            So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:



            1. 3,5,7 -> result set

            2. recursive statements applied to 3,5,7, which is 9,25,49. 9,25,49 is added to result set, and replaces the left side of the UNION ALL.

            3. recursive statements applied to 9,25,49, which is 81,625,2401. 81,625,2401 is added to result set, and replaces the left side of the UNION ALL.

            4. recursive statements applied to 81,625,2401, which is 6561,390625,5764801. 6561,390625,5764801 is added to result set.

            5. Cursor is complete, since next iteration results in the WHERE clause returning false.

            You can see this behavior in the execution plan for the recursive CTE:



            enter image description here



            This is step 1 above, where the left side of the UNION ALL is added to the output:



            enter image description here



            This is the right side of the UNION ALL where the output is concatenated to the result set:



            enter image description here






            share|improve this answer















            This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.



            T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.



            So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:



            1. 3,5,7 -> result set

            2. recursive statements applied to 3,5,7, which is 9,25,49. 9,25,49 is added to result set, and replaces the left side of the UNION ALL.

            3. recursive statements applied to 9,25,49, which is 81,625,2401. 81,625,2401 is added to result set, and replaces the left side of the UNION ALL.

            4. recursive statements applied to 81,625,2401, which is 6561,390625,5764801. 6561,390625,5764801 is added to result set.

            5. Cursor is complete, since next iteration results in the WHERE clause returning false.

            You can see this behavior in the execution plan for the recursive CTE:



            enter image description here



            This is step 1 above, where the left side of the UNION ALL is added to the output:



            enter image description here



            This is the right side of the UNION ALL where the output is concatenated to the result set:



            enter image description here







            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Jan 11 at 20:40

























            answered Jan 11 at 20:31









            Max VernonMax Vernon

            50.5k13112222




            50.5k13112222





















                3














                The SQL Server documentation, which mentions Ti and Ti+1, is neither very understandable, nor an accurate description of the actual implementation.



                The basic idea is that the recursive part of the query looks at all previous results, but only once.



                It might be helpful to look how other databases implement this (to get the same result). The Postgres documentation says:




                Recursive Query Evaluation



                1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

                2. So long as the working table is not empty, repeat these steps:

                  1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

                  2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.


                Note

                Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.




                The SQLite documentation hints at a slightly different implementation, and this one-row-at-a-time algorithm might be the easiest to understand:




                The basic algorithm for computing the content of the recursive table is as follows:



                1. Run the initial-select and add the results to a queue.

                2. While the queue is not empty:

                  1. Extract a single row from the queue.

                  2. Insert that single row into the recursive table

                  3. Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.


                The basic procedure above may modified by the following additional rules:



                • If a UNION operator connects the initial-select with the recursive-select, then only add rows to the queue if no identical row has been previously added to the queue. Repeated rows are discarded before being added to the queue even if the repeated rows have already been extracted from the queue by the recursion step. If the operator is UNION ALL, then all rows generated by both the initial-select and the recursive-select are always added to the queue even if they are repeats.

                  […]






                share|improve this answer





























                  3














                  The SQL Server documentation, which mentions Ti and Ti+1, is neither very understandable, nor an accurate description of the actual implementation.



                  The basic idea is that the recursive part of the query looks at all previous results, but only once.



                  It might be helpful to look how other databases implement this (to get the same result). The Postgres documentation says:




                  Recursive Query Evaluation



                  1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

                  2. So long as the working table is not empty, repeat these steps:

                    1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

                    2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.


                  Note

                  Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.




                  The SQLite documentation hints at a slightly different implementation, and this one-row-at-a-time algorithm might be the easiest to understand:




                  The basic algorithm for computing the content of the recursive table is as follows:



                  1. Run the initial-select and add the results to a queue.

                  2. While the queue is not empty:

                    1. Extract a single row from the queue.

                    2. Insert that single row into the recursive table

                    3. Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.


                  The basic procedure above may modified by the following additional rules:



                  • If a UNION operator connects the initial-select with the recursive-select, then only add rows to the queue if no identical row has been previously added to the queue. Repeated rows are discarded before being added to the queue even if the repeated rows have already been extracted from the queue by the recursion step. If the operator is UNION ALL, then all rows generated by both the initial-select and the recursive-select are always added to the queue even if they are repeats.

                    […]






                  share|improve this answer



























                    3












                    3








                    3







                    The SQL Server documentation, which mentions Ti and Ti+1, is neither very understandable, nor an accurate description of the actual implementation.



                    The basic idea is that the recursive part of the query looks at all previous results, but only once.



                    It might be helpful to look how other databases implement this (to get the same result). The Postgres documentation says:




                    Recursive Query Evaluation



                    1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

                    2. So long as the working table is not empty, repeat these steps:

                      1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

                      2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.


                    Note

                    Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.




                    The SQLite documentation hints at a slightly different implementation, and this one-row-at-a-time algorithm might be the easiest to understand:




                    The basic algorithm for computing the content of the recursive table is as follows:



                    1. Run the initial-select and add the results to a queue.

                    2. While the queue is not empty:

                      1. Extract a single row from the queue.

                      2. Insert that single row into the recursive table

                      3. Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.


                    The basic procedure above may modified by the following additional rules:



                    • If a UNION operator connects the initial-select with the recursive-select, then only add rows to the queue if no identical row has been previously added to the queue. Repeated rows are discarded before being added to the queue even if the repeated rows have already been extracted from the queue by the recursion step. If the operator is UNION ALL, then all rows generated by both the initial-select and the recursive-select are always added to the queue even if they are repeats.

                      […]






                    share|improve this answer















                    The SQL Server documentation, which mentions Ti and Ti+1, is neither very understandable, nor an accurate description of the actual implementation.



                    The basic idea is that the recursive part of the query looks at all previous results, but only once.



                    It might be helpful to look how other databases implement this (to get the same result). The Postgres documentation says:




                    Recursive Query Evaluation



                    1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

                    2. So long as the working table is not empty, repeat these steps:

                      1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

                      2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.


                    Note

                    Strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee.




                    The SQLite documentation hints at a slightly different implementation, and this one-row-at-a-time algorithm might be the easiest to understand:




                    The basic algorithm for computing the content of the recursive table is as follows:



                    1. Run the initial-select and add the results to a queue.

                    2. While the queue is not empty:

                      1. Extract a single row from the queue.

                      2. Insert that single row into the recursive table

                      3. Pretend that the single row just extracted is the only row in the recursive table and run the recursive-select, adding all results to the queue.


                    The basic procedure above may modified by the following additional rules:



                    • If a UNION operator connects the initial-select with the recursive-select, then only add rows to the queue if no identical row has been previously added to the queue. Repeated rows are discarded before being added to the queue even if the repeated rows have already been extracted from the queue by the recursion step. If the operator is UNION ALL, then all rows generated by both the initial-select and the recursive-select are always added to the queue even if they are repeats.

                      […]







                    share|improve this answer














                    share|improve this answer



                    share|improve this answer








                    edited Jan 15 at 7:52

























                    answered Jan 12 at 8:22









                    CL.CL.

                    2,68011115




                    2,68011115





















                        0














                        My knowledge is in DB2 specifically but looking at the explain diagrams seems to be the same with SQL Server.



                        The plan comes from here:



                        See it on Paste the Plan



                        SQL Server Explain Plan



                        The optimizer does not literally run a union all for each recursive query. It takes the structure of the query and assigns the first part of the union all to an "anchor member" then it will run through the second half of the union all (called the "recursive member" recursively until it reaches the limitations defined. After the recursion is complete, the optimizer joins all records together.



                        The optimizer just takes it as a suggestion to do a pre-defined operation.






                        share|improve this answer





























                          0














                          My knowledge is in DB2 specifically but looking at the explain diagrams seems to be the same with SQL Server.



                          The plan comes from here:



                          See it on Paste the Plan



                          SQL Server Explain Plan



                          The optimizer does not literally run a union all for each recursive query. It takes the structure of the query and assigns the first part of the union all to an "anchor member" then it will run through the second half of the union all (called the "recursive member" recursively until it reaches the limitations defined. After the recursion is complete, the optimizer joins all records together.



                          The optimizer just takes it as a suggestion to do a pre-defined operation.






                          share|improve this answer



























                            0












                            0








                            0







                            My knowledge is in DB2 specifically but looking at the explain diagrams seems to be the same with SQL Server.



                            The plan comes from here:



                            See it on Paste the Plan



                            SQL Server Explain Plan



                            The optimizer does not literally run a union all for each recursive query. It takes the structure of the query and assigns the first part of the union all to an "anchor member" then it will run through the second half of the union all (called the "recursive member" recursively until it reaches the limitations defined. After the recursion is complete, the optimizer joins all records together.



                            The optimizer just takes it as a suggestion to do a pre-defined operation.






                            share|improve this answer















                            My knowledge is in DB2 specifically but looking at the explain diagrams seems to be the same with SQL Server.



                            The plan comes from here:



                            See it on Paste the Plan



                            SQL Server Explain Plan



                            The optimizer does not literally run a union all for each recursive query. It takes the structure of the query and assigns the first part of the union all to an "anchor member" then it will run through the second half of the union all (called the "recursive member" recursively until it reaches the limitations defined. After the recursion is complete, the optimizer joins all records together.



                            The optimizer just takes it as a suggestion to do a pre-defined operation.







                            share|improve this answer














                            share|improve this answer



                            share|improve this answer








                            edited Jan 11 at 20:55

























                            answered Jan 11 at 20:45









                            Michael S.Michael S.

                            14




                            14



























                                draft saved

                                draft discarded
















































                                Thanks for contributing an answer to Database Administrators Stack Exchange!


                                • Please be sure to answer the question. Provide details and share your research!

                                But avoid


                                • Asking for help, clarification, or responding to other answers.

                                • Making statements based on opinion; back them up with references or personal experience.

                                To learn more, see our tips on writing great answers.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function ()
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdba.stackexchange.com%2fquestions%2f226946%2fhow-does-sql-recursion-actually-work%23new-answer', 'question_page');

                                );

                                Post as a guest















                                Required, but never shown





















































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown

































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown






                                Popular posts from this blog

                                How to check contact read email or not when send email to Individual?

                                Displaying single band from multi-band raster using QGIS

                                How many registers does an x86_64 CPU actually have?