How is a sql recursive statement interpreted?

Question

I would like to ask to help you understand how it works "with recursive". More precisely, why the anchor request (non-recursive term) is not replicated to the CTE subheading. I tried my best to understand, but I'm not sure.

First of all, let's take an example of PostgreSQL, which is the simplest one found (make a sum from 1 to 100):

WITH RECURSIVE t(n) AS ( VALUES (1) UNION ALL SELECT n+1 FROM t WHERE n < 100) SELECT sum(n) FROM t; 

Passing my code (I used the links below):

• Rate the non-recursive term. For UNION [...].

  Include all remaining rows as a result of a recursive query, and place them in a temporary worksheet.

• Until the worksheet is empty , repeat the following steps:

  • Evaluate a recursive term by replacing the current contents of the worksheet with recursive self-promotion. For UNION [...]. Include all remaining rows as a result of the recursive query, and place them in a temporary staging table.

  • Replace the contents of the worksheet with the contents of the staging table, then run the staging table.

LVL 0:

• non-recursive part

  • CTE: (N) 1
  • WORKING TABLES: (N) 1

• recursive part

  • CTE: (N) 1
  • WORKING TABLES: (N) 1
  • INTERIM TABLES (N) 2

(this is the part that I think of, I think of) - a replacement for WORKING TABLE

So recursive t will use WORKING TABLE to execute SELECT n + 1 and put the result in INTERMEDIATE TABLE.

3. UNION ALL

   • CTE: (N) 1 2
   • WORKING TABLES: (N) 2
   • INTERIM TABLES: CLEAN

4. Then we move on to the next lvl by calling t on the right? (since the condition is END WHERE n <100 = FALSE)

LVL 1:

We know that postgreSQL says that "until the worksheet is empty, repeat the recursive steps" This way, it will repeat steps 2. and 3. (if I'm right) to the END state, then execute SUM.

BUT if I just go through the call of the next lvl t, if we don't do VALUES (1) first?

I am really confused about how this is possible.

Regards, Falt4rm

• PostgreSQL: query-with
• Microsoft Technet: CTE structure

Answer 1

There is no "recursion" here, and I think that you are confused here.

From the PostgreSQL documentation: http://www.postgresql.org/docs/9.4/static/queries-with.html

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

To rephrase this sentence, WITH RECURSIVE can be thought of as a simple WHILE loop.

 WITH RECURSIVE t(n) AS ( VALUES (1) UNION ALL SELECT n+1 FROM t WHERE n < 100 ) SELECT * FROM t; 

Here are a few custom-made pseudo codes to explain this process in detail.

 # Step 1: initialisation LET cte_result = EMPTY LET working_table = VALUES (1) LET intermediate_table = EMPTY # Step 2: result initialisation, merge initialisation into cte_result cte_result = cte_result UNION working_table # Step 3: iteration test WHILE (working_table is not empty) DO # Step 4: iteration select, we substitute the self-reference with working_table intermediate_table = SELECT n+1 FROM working_table WHERE n < 100 # Step 5: iteration merge, merge the iteration result into cte_result cte_result = cte_result UNION intermediate_table # Step 6: iteration end, prepare for next iteration working_table = intermediate_table intermediate_table = EMPTY END WHILE # Step 7: return RETURN cte_result 

And using an example

 # Step 1: initialisation cte_result: EMPTY | working_table: 1 | intermediate_table: EMPTY # Step 2: result initialisation cte_result: 1 | working_table: 1 | intermediate_table: EMPTY # Step 3: iteration test count(working_table) = 1 # OK # Step 4: iteration select cte_result: 1 | working_table: 1 | intermediate_table: 2 # Step 5: iteration merge cte_result: 1, 2 | working_table: 1 | intermediate_table: 2 # Step 6: iteration end cte_result: 1, 2 | working_table: 2 | intermediate_table: EMPTY # Step 3: iteration test count(working_table) = 1 # OK # Step 4: iteration select cte_result: 1, 2 | working_table: 2 | intermediate_table: 3 # Step 5: iteration merge cte_result: 1, 2, 3 | working_table: 2 | intermediate_table: 3 # Step 6: iteration end cte_result: 1, 2, 3 | working_table: 3 | intermediate_table: EMPTY # … 97 more iterations and you get this state cte_result: 1, 2, …, 100 | working_table: 100 | intermediate_table: EMPTY # Step 3: iteration test count(working_table) = 1 # OK # Step 4: iteration select, the iteration query does not return any rows due to the WHERE clause cte_result: 1, 2, …, 100 | working_table: 100 | intermediate_table: EMPTY # Step 5: iteration merge, nothing is merged into the cte_result cte_result: 1, 2, …, 100 | working_table: 100 | intermediate_table: EMPTY # Step 6: iteration end cte_result: 1, 2, …, 100 | working_table: EMPTY | intermediate_table: EMPTY # Step 3: iteration test count(working_table) = 0 # STOP # Step 7: return cte_result: 1, 2, …, 100 

Thus, the result of CTE are all numbers from 1 to 100.