Recursive query on a self-referential table where each node has one link to its child's node

Consider the following table and data (fiddle available here):

CREATE TABLE test 
(
  id INTEGER NOT NULL AUTO_INCREMENT PRIMARY KEY,
  next_id INTEGER NOT NULL
);

INSERT INTO test (id,   next_id) VALUES
(1, 3),
(2, 3),
(3, 6),
(4, 5),
(5, 6),
(6, 8),
(7, 10),
(8, 9);

I want to be able to select only the rows starting from ID = 1 following the Next ID in a recursive way. That is, I want to select in this example the following rows:

ID
Next ID

1
3

3
6

6
8

8
9

I realize it would be relatively easy with a programming language to achieve, but I'd like to know if anyone has an idea how to achieve that using pure SQL.

You can run the following (all the code below is available on the fiddle here):

WITH RECURSIVE cte (id_, next_id_) AS
(
  SELECT id, next_id FROM test WHERE id = (SELECT MIN(id) FROM test)
  UNION ALL
  SELECT 
    c.next_id_, t.next_id
  FROM
    cte c
  JOIN test t
  ON c.next_id_ = t.id
)
SELECT * FROM cte;

Result:

rn  id_   next_id_
 1    1          3
 2    3          6
 3    6          8
 4    8          9

These queries are tricky and it can take one (well, me anyway) a while to get one's head around them, so I'll go through this line by line - as much for me as for you! :-) (or anybody else who's struggling with these delicate and (potentially very) complex beasts!).

So, first line

WITH RECURSIVE cte (id_, next_id_) AS

The RECURSIVE keyword is obligatory for MySQL, MariaDB & PostgreSQL and throws an error for SQL Server, SQLite and Oracle. You may or may not require the field definitions in the brackets - check it out yourself - most seem to accept it and it's a help when you're actually formulating your query!

Then:

SELECT id, next_id FROM test WHERE id = (SELECT MIN(id) FROM test)

Our "seed" or "anchor" query - the first values in our RECURSIVE CTE - in this case, it's the tuple (1, 3).

The obligatory UNION ALL is followed by the core of the recursive part of the query:

SELECT 
  c.next_id_, t.next_id
FROM
  cte c
JOIN test t
ON c.next_id_ = t.id

So, starting with (1,3), we SELECT 3 (c.next_id) from the RCTE and a value from test by JOINing them ON 3 = t.id - now t.id is test's PK and therefore UNIQUE, so we obtain the tuple (3, 6).

In the next iteration, we have 6 as our cte.id_ and the JOIN picks up the cte.next_id_ value of 8 in the JOIN - and so on to the end of the table - 8 then picks up 9 and the query terminates. Voilà - the desired result!

@RickJames kindly pointed out that there is a limit to the available depth of recursion. In MySQL, this is determined by the system variable cte_max_recursion_depth, which by default is equal to 1000 (see bottom of fiddle).

SHOW VARIABLES LIKE 'cte_max_recursion_depth';

Result:

Variable_name            Value
cte_max_recursion_depth   1000

It can be set on a session or a global basis.

SET cte_max_recursion_depth = 1200;    ✓

Rerun our SHOW VARIABLES command:

SHOW VARIABLES LIKE 'cte_max_recursion_depth';

Result:

Variable_name   Value
cte_max_recursion_depth   1200

Of course, it cannot be increased ad infinitum (or even to its Maximum Value of 4294967295) - systems only have finite resources - YMMV!

StackExchange Database Administrators Q#301903, answer score: 4