Skip to content

Topological Sorting #34343

@alexey-milovidov

Description

@alexey-milovidov

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    featurewarmup taskThe task for new ClickHouse team members. Low risk, moderate complexity, no urgency.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions