-
Notifications
You must be signed in to change notification settings - Fork 8.3k
Topological Sorting #34343
Description
Use case
Backup and restore tables based on their dependencies.
Describe the solution you'd like
ORDER BY x DEPENDS ON y
Where y has the same type as x or Nullable of the same type, or it is an array of elements of the same type as x.
what dependencies
'Moscow' ['Russia']
'Russia' ['Europe', 'Asia']
'Europe' []
'Asia' []
SELECT what FROM places ORDER BY what DEPENDS ON dependencies
will give
Europe
Asia
Russia
Moscow
Similarly, on:
what dependencies
'Moscow' 'Russia'
'Russia' 'Europe'
'Europe' ''
the same query will give
Europe
Russia
Moscow
To implement it, we can maintain the set of already processed items and a queue of postponed items.
If an item has dependency that has not been already processed, we will place it to the end of queue.
We also track, what was the last number of items in the queue after the item, when the item from the queue was pushed back to the end of queue again. If the number does not change, we understand it as a loop or a broken dependency and process item nevertheless.
PS. Not sure if the algorithm is correct. More info https://en.wikipedia.org/wiki/Topological_sorting