MySQL 8.0.1: [Рекурсивные] Обобщенные Табличные Выражения в MySQL, часть 4 - обход дерева в глубину или в ширину, транзитивное замыкание, предотвращение зацикливания

ОТВ и рекурсивные ОТВ появились в MySQL 8.0; первоначально в Labs релизе, а теперь и в основном релизе 8.0.1. Это четвертая статья из цикла, предыдущие: раз, два и три. Мой коллега Øystein написал о том, как использование ОТВ в 2 раза ускоряет выполнение запроса из теста DBT-3.

В этой статье я сосредоточусь на следующих моментах рекурсивных ОТВ:

Обход дерева в глубину или в ширину

Я уже рассматривал этот вопрос в предыдущем материале (в параграфе "Обход всего дерева"), но давайте резюмируем проблему и решение. Пусть у нас есть таблица людей с отношением родитель-ребенок.

CREATE TABLE tree (person CHAR(20), parent CHAR(20));
INSERT INTO tree VALUES
('Robert I', NULL),
('Thurimbert', 'Robert I'),
('Robert II', 'Thurimbert'),
('Cancor', 'Thurimbert'),
('Landrade', 'Thurimbert'),
('Ingramm', 'Thurimbert'),
('Robert III', 'Robert II'),
('Chaudegrand', 'Landrade'),
('Ermengarde', 'Ingramm');

Это часть родословной французских королей, в районе 8-го века нашей эры. Схематично:

Robert I -> Thurimbert --> Robert II -> Robert III
+-> Cancor
+-> Landrade -> Chaudegrand
+-> Ingramm -> Ermengarde

Теперь мы хотим определить всех потомков Thurimbert-а:

Сортировка "в ширину" означает, что мы хотим видеть сначала всех детей, потом внуков и т.д. Именно такой порядок и вернул наш запрос (однако, по стандарту SQL, если вы не указываете в явном виде ORDER BY, то порядок строк не гарантирован). Добавим столбец “level”, значение которого будет увеличиваться при переходе на более глубокий уровень, и отсортируем по нему:

WITH RECURSIVE descendants AS
(
SELECT person, 1 as level
FROM tree
WHERE person='Thurimbert'
UNION ALL
SELECT t.person, d.level+1
FROM descendants d, tree t
WHERE t.parent=d.person
)
SELECT * FROM descendants ORDER BY level;
+-------------+-------+
| person | level |
+-------------+-------+
| Thurimbert | 1 |
| Robert II | 2 |
| Cancor | 2 |
| Landrade | 2 |
| Ingramm | 2 |
| Robert III | 3 |
| Chaudegrand | 3 |
| Ermengarde | 3 |
+-------------+-------+

Сортировка "в глубину" означает, что мы хотим видеть детей сразу после их родителя. Для этого добавим строковый столбец “path”, значение которого будет расширяться при переходе на более глубокий уровень, и отсортируем по нему:

Я уже объяснял необходимость использования CAST в одной из предыдущих статей: тип колонки "path" определяется в источнике рекурсии и он должен быть достаточно широким, чтобы вместить путь до самых глубоких листьев дерева; CAST это обеспечивает.

В стандарте SQL есть необязательная конструкция SEARCH BY для указания вида сортировки: "в ширину" или "в глубину"; как видно из примеров выше, в MySQL можно легко эмулировать такое поведение с помощью дополнительных столбцов “level” или “path”.

Вычисление транзитивного замыкания, простейший случай предотвращения зацикливания

К 2300 году Земля станет перенаселена, и люди будут стремиться эмигрировать на другие планеты с помощью следующих ракетных маршрутов:

CREATE TABLE rockets
(origin CHAR(20), destination CHAR(20), trip_time INT);
INSERT INTO rockets VALUES
('Earth', 'Mars', 2),
('Mars', 'Jupiter', 3),
('Jupiter', 'Saturn', 4);

Обратите внимание, что правительство намеренно не предоставляет возможность вернуться обратно на Землю.

Давайте составим маршруты, по которым могут двигаться переселенцы: сначала определим планеты, имеющие прямое сообщение с Землей; потом те, до которых можно добраться с одной пересадкой, и т.д.:

Пусть к 2400 году население сократится столь сильно, что правительство решит вернуть назад часть переселенцев, для чего организуют новый маршрут с Сатурна на Землю:

INSERT INTO rockets VALUES ('Saturn', 'Earth', 9);

Давайте повторим наш запрос, составляющий маршрут:

WITH RECURSIVE all_destinations AS
(
SELECT destination AS planet
FROM rockets
WHERE origin='Earth'
UNION ALL
SELECT r.destination
FROM rockets r, all_destinations d
WHERE r.origin=d.planet
)
SELECT * FROM all_destinations;
^C -- query aborted
ERROR 1317 (70100): Query execution was interrupted

Казалось, что запрос никогда не завершится, поэтому мне пришлось прервать его. Почему так произошло? Мы имеем зацикливание данных: начинаем с Земли, добавляем Марс, затем Юпитер, Сатурн и (за счет нового маршрута) возвращаемся снова к Земле. После чего снова добавляем Марс и так далее по кругу, бесконечно.

С помощью переменной max_execution_time можно автоматически убивать запросы по истечению таймаута, но как переписать запрос, чтобы он работал корректно?

Простейшее решение - не добавлять планету в итоговый набор, если она там уже присутствует. Такого удаления дубликатов можно добиться, используя UNION DISTINCT вместо UNION ALL:

Предотвращение зацикливания в более сложных случаях

Итак, у нас работающий запрос с UNION DISTINCT. Давайте немного расширим его, чтобы дополнительно отображать время в пути до каждой планеты (довольно невинная идея, правда?):

WITH RECURSIVE all_destinations AS
(
SELECT destination AS planet, trip_time AS total_time
FROM rockets
WHERE origin='Earth'
UNION DISTINCT
SELECT r.destination, d.total_time+r.trip_time
FROM rockets r, all_destinations d
WHERE r.origin=d.planet
)
SELECT * FROM all_destinations;
^C -- query aborted
ERROR 1317 (70100): Query execution was interrupted

Что? Снова зацикливание? Давайте, рассмотрим первые строки, генерируемые запросом:

Время в пути до Марса по маршруту Earth->Mars->Jupiter->Saturn->Earth->Mars составляет 20 единиц, в то время как напрямую по маршруту Earth->Mars всего 2 единицы; т.е. разные маршруты до одной и той же планеты формируют разные строки, отличающиеся длительностью поездки: (Mars, 2) и (Mars, 20). UNION DISTINCT удаляет только те строки, в которых совпадают значения всех столбцов. Таким образом, строка (Mars, 20) попадает в итоговый набор, в свою очередь формирует (Jupiter, 23) и так далее до бесконечности.

Для таких случаев в стандарте SQL есть конструкция CYCLE, функциональность которой можно легко повторить с помощью дополнительной колонки “path”, содержащей все промежуточные точки назначения (по аналогии с сортировкой "в глубину" из первой части статьи) и прерыванием процесса, при повторном добавлении ранее пройденного элемента пути. В DISTINCT больше нет необходимости, поэтому для исключения накладных расходов используется ALL.

Обратите внимание, если имя планеты может содержать запятую, то для корректной работы FIND_IN_SET при добавлении значений в колонку “path” их нужно кодировать с помощью TO_BASE64 или HEX.

Если зацикливание данных является аномалией, которую мы хотим отловить, то предыдущий запрос можно преобразовать для решения этой задачи. Нужно, чтобы строки с зацикленными данными попали в итоговый набор и были отмечены (с помощью новой колонки “is_cycle”), но сам запрос при этом не должен уйти в бесконечный цикл, т.е. не выполняются итерации по строкам, где is_cycle=1:

WITH RECURSIVE all_destinations AS
(
SELECT destination AS planet, trip_time AS total_time,
CAST(destination AS CHAR(500)) AS path, 0 AS is_cycle
FROM rockets
WHERE origin='Earth'
UNION ALL
SELECT r.destination, d.total_time+r.trip_time,
CONCAT(d.path, ',', r.destination),
FIND_IN_SET(r.destination, d.path)!=0
FROM rockets r, all_destinations d
WHERE r.origin=d.planet
AND is_cycle=0
)
SELECT * FROM all_destinations;
+---------+------------+--------------------------------+----------+
| planet | total_time | path | is_cycle |
+---------+------------+--------------------------------+----------+
| Mars | 2 | Mars | 0 |
| Jupiter | 5 | Mars,Jupiter | 0 |
| Saturn | 9 | Mars,Jupiter,Saturn | 0 |
| Earth | 18 | Mars,Jupiter,Saturn,Earth | 0 |
| Mars | 20 | Mars,Jupiter,Saturn,Earth,Mars | 1 |
+---------+------------+--------------------------------+----------+

Вот и все на сегодня. Надеюсь, что показанные примеры помогут вам писать мощные запросы для управления иерархически данными. И как всегда: "Спасибо, что используете MySQL!".

© Все права на данную статью принадлежат порталу SQLInfo.ru. Перепечатка в интернет-изданиях разрешается только с указанием автора и прямой ссылки на оригинальную статью. Перепечатка в бумажных изданиях допускается только с разрешения редакции.