SQL Recursion Without Recursion

Is there a way to select Parent IDs in SQL without recursion or looping?

The operation is inherently looped. Because each node does not have any finite relation to their root, you must traverse in order to discover it.

If, for example, you knew that there was a maximum depth of N then you could create N LEFT OUTER JOINs in a single statement and display the last non-null parent ID returned this way.

The looping requirement is that you simply don't know what N is, and you cannot ask a declarative language like SQL to "figure it out"

Even if you can accomplish it with some built-in method, it will still be a loop or recursion, just obfuscated from you.

How does a SQL Recursive Query not run into an endless loop?

There is nothing "recursive" in "recursive" queries.

It should have been called "iterative".

There are some differences between vendors but the basic concept is the same:

1. The anchor part (the one that doesn't refer to the "recursive" query name) creates the initial set.

2. The iterative part (the one that refers to the "recursive" query name) is using the last set to creates a new set that now becomes the last set, and so on.
   
   It stops when it gets to an empty set.

---

And here is an endless query:

with recursive t as (select 1 union all select 1 from t) 
select count(*) from t

---

Explanation for the OP example

Initial set created by the anchor part, `VALUES (1)`: 
1 record, n=1

Sets created by the iterative part, `SELECT n+1 FROM t WHERE n < 100`:
1 record, n=2 (the initial set has 1 record with n=1 so `SELECT n+1 from t` returns 2)
1 record, n=3 
1 record, n=4
1 record, n=5
.
.
.
1 record, n=99
1 record, n=100 

When n=100 the WHERE condition `WHERE n < 100` causes an empty set to be created 
and the iteration stops.

---

One way to think on iterative queries:

with        t0 as (select ...)
           ,t1 as (select ... t0 ...)
           ,t2 as (select ... t1 ...)
           ,t3 as (select ... t2 ...)
            .
            .
            .

            select * from t0
union all   select * from t1
union all   select * from t2
union all   select * from t3
union all   ...

t0 is a CTE with no dependencies in other CTE.

t1 is a CTE with dependency in t0.

t2 is a CTE with dependency in t1 (and only t1!).

t3 is a CTE with dependency in t2 (and only t2!).

etc.

t1, t2, t3 etc.. are declared with identical queries, different only in their dependencies.

Is there a way to make recursive SQL queries without using a CTE?

You don't nest CTEs, but they can be part of the insert:

with cte as (
      . . . 
     )
insert into . . .
   select . . .
   from cte;

You can see this in the syntax diagram for insert.

Note that in most databases, CTEs are part of the select, so you can do what you want.

traversing recursive CTE to the root in SQL Server reaches maximum recursion

You've managed to create an infinite loop. You can stick in a filter against level to debug these:

(also after removing the manager id)

WITH EmpCTE
AS
( 
  -- Anchor Member (AM)
  SELECT 
      empid, 
      empname, 
      mgrid, 
      0 AS level                            -- <------------------- SET LVL START FROM 0
  FROM Employees
  WHERE EMPID = 7
  UNION ALL
  -- Recursive Member (RM)
  SELECT 
      e.empid, 
      e.empname, 
      e.mgrid, 
      e.level+1                     -- <------------------- INCREMENT LVL
  FROM Employees AS m
    JOIN EmpCTE AS e                    -- <------------------- RECURSIVELY CALL EmpCTE
      ON e.mgrid = m.empid
where level < 2
)
SELECT * FROM EmpCTE;

empid       empname                   mgrid       level
----------- ------------------------- ----------- -----------
7           Robert                    3           0
7           Robert                    3           1
7           Robert                    3           2

This is because you are projecting the columns from EmpCTE as e rather than Employees as m, so you're just getting the same data again and again (plus the level being increased).

WITH EmpCTE
AS
( 
  -- Anchor Member (AM)
  SELECT 
      empid, 
      empname, 
      mgrid, 
      0 AS level                            -- <------------------- SET LVL START FROM 0
  FROM Employees
  WHERE EMPID = 7
  UNION ALL
  -- Recursive Member (RM)
  SELECT 
      m.empid,   -- these columns need to come from m
      m.empname, -- these columns need to come from m
      m.mgrid,   -- these columns need to come from m
      e.level+1                     -- <------------------- INCREMENT LVL
  FROM Employees AS m
    JOIN EmpCTE AS e                    -- <------------------- RECURSIVELY CALL EmpCTE
      ON e.mgrid = m.empid
)
SELECT * FROM EmpCTE;

empid       empname                   mgrid       level
----------- ------------------------- ----------- -----------
7           Robert                    3           0
3           Janet                     1           1
1           Nancy                     NULL        2

Possible to emulate a recursive CTE?

None of the solutions is very efficient, and most of them involve writing more code than you should. It would be better to upgrade to MySQL 8.0.

SQL works best on sets, not on iteration. So the standard way to generate a series in a single query is to already have a set of rows in a temporary table, and apply some set-based operations to it.

For example:

SELECT 0 AS num UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5;
+-----+
| num |
+-----+
|   0 |
|   1 |
|   2 |
|   3 |
|   4 |
|   5 |
+-----+

With this as the basis, you can do date arithmetic and then extract the weekday names with DATE_FORMAT():

SELECT DATE_FORMAT(CURDATE() + INTERVAL num DAY, '%W') AS weekday
FROM (
  SELECT 0 AS num UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5
) AS t;

+-----------+
| weekday   |
+-----------+
| Friday    |
| Saturday  |
| Sunday    |
| Monday    |
| Tuesday   |
| Wednesday |
+-----------+

You could also prepare a fixed base table of integers, fill it with as many as you need, and use it for different purposes.

SELECT DATE_FORMAT(CURDATE() + INTERVAL num DAY, '%W') AS weekday
FROM MySetOfIntegers
WHERE num BETWEEN 0 AND 5;

The suggestion of using an iterative approach would involve writing a lot more code. It will also mean N SQL queries, each generating a separate result set, so that's more code you have to write in your application to fetch all the result sets and append them together.

You could write a recursive stored procedure, but there's a risk of exceeding the thread stack space if you allow deep recursion. The default limit on stored procedure recursion is 0. That is, no recursion is allowed at all unless you set a finite limit. See https://dev.mysql.com/doc/refman/5.7/en/server-system-variables.html#sysvar_max_sp_recursion_depth

Here's an example of a recursive stored procedure:

DROP PROCEDURE IF EXISTS Weekdays;
DELIMITER //
CREATE PROCEDURE Weekdays(IN date DATE, IN num INT)
BEGIN
  IF num >= 1 THEN
    CALL Weekdays(date, num-1);
  END IF;
  SELECT DATE_FORMAT(date + INTERVAL num-1 DAY, '%W') AS weekday;
END//
DELIMITER ;

And calling it. Note it produces multiple result sets.

mysql> set max_sp_recursion_depth=6;

mysql> call Weekdays(CURDATE(), 6);

+----------+
| weekday  |
+----------+
| Thursday |
+----------+
1 row in set (0.00 sec)

+---------+
| weekday |
+---------+
| Friday  |
+---------+
1 row in set (0.00 sec)

+----------+
| weekday  |
+----------+
| Saturday |
+----------+
1 row in set (0.00 sec)

+---------+
| weekday |
+---------+
| Sunday  |
+---------+
1 row in set (0.00 sec)

+---------+
| weekday |
+---------+
| Monday  |
+---------+
1 row in set (0.00 sec)

+---------+
| weekday |
+---------+
| Tuesday |
+---------+
1 row in set (0.00 sec)

+-----------+
| weekday   |
+-----------+
| Wednesday |
+-----------+
1 row in set (0.00 sec)

I may have gotten the recursion off by one somewhere. This actually supports the point that it's not as easy as it sounds to implement a recursive routine.

Oh and you get an error — and no results — if you exceed the recursion limit.

mysql> call Weekdays(CURDATE(), 8);
ERROR 1456 (HY000): Recursive limit 6 (as set by the max_sp_recursion_depth variable) was exceeded for routine Weekdays

---

Related Topics