How to sort linked list in sql?

Question

I applied the linked list as a self-reference database table:

CREATE TABLE LinkedList( Id bigint NOT NULL, ParentId bigint NULL, SomeData nvarchar(50) NOT NULL) 

where Id is the primary key, and ParentId is the identifier of the previous node in the list. The first node has ParentId = NULL.

Now I want to SELECT from the table, sorting the rows in the same order in which they should appear, as nodes in the list.

For example: if the table contains rows

 Id ParentId SomeData 24971 NULL 0 38324 24971 1 60088 60089 3 60089 38324 2 61039 61497 5 61497 60088 4 109397 109831 7 109831 61039 6 

Then sorting using criteria should result in:

 Id ParentId SomeData 24971 NULL 0 38324 24971 1 60089 38324 2 60088 60089 3 61497 60088 4 61039 61497 5 109831 61039 6 109397 109831 7 

You should use Color SomeData as a control, so please don't fool the ORDER command with SomeData :-)

Answer 1

In Oracle:

 SELECT Id, ParentId, SomeData FROM ( SELECT ll.*, level AS lvl FROM LinkedList ll START WITH ParentID IS NULL CONNECT BY ParentId = PRIOR Id ) ORDER BY lvl 

P. S. It is bad practice to use NULL as a ParentID , because it cannot be specified by indexes. Instead, insert a surrogate root with the identifier 0 or -1 and use START WITH ParentID = 0 .

Answer 2

I found a solution for SQLServer, but it looks big and much less elegant than

Quassnoi.

 WITH SortedList (Id, ParentId, SomeData, Level) AS ( SELECT Id, ParentId, SomeData, 0 as Level FROM LinkedList WHERE ParentId IS NULL UNION ALL SELECT ll.Id, ll.ParentId, ll.SomeData, Level+1 as Level FROM LinkedList ll INNER JOIN SortedList as s ON ll.ParentId = s.Id ) SELECT Id, ParentId, SomeData FROM SortedList ORDER BY Level 

Answer 3

(edit: d'oh! While I was debugging, you found it too!)

In SQL Server:

 ;WITH cte (Id, ParentId, SomeData, [Level]) AS ( SELECT Id, ParentId, SomeData, 0 FROM LinkedList WHERE ParentId IS NULL UNION ALL SELECT ll.Id, ll.ParentId, ll.SomeData, cte.[Level] + 1 FROM LinkedList ll INNER JOIN cte ON ll.ParentID = cte.ID ) SELECT * FROM cte ORDER BY [Level]