Skip to main content
added 43 characters in body
Source Link
CL.
  • 5.3k
  • 1
  • 22
  • 23

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 athow 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.
    […]

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 at other databases. 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.
    […]

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.
    […]
Source Link
CL.
  • 5.3k
  • 1
  • 22
  • 23

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 at other databases. 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.
    […]