MySQL 8.0.1: [Рекурсивные] Обобщенные Табличные Выражения в MySQL, часть 4 - обход дерева в глубину или в ширину, транзитивное замыкание, предотвращение зацикливания
Дата: 4.07.2017
Данная статья является переводом статьи Гильема Бишота.
ОТВ и рекурсивные ОТВ появились в MySQL 8.0; первоначально в Labs релизе, а теперь и в основном релизе 8.0.1. Это четвертая статья из цикла, предыдущие: раз, два и три. Мой коллега Øystein написал о том, как использование ОТВ в 2 раза ускоряет выполнение запроса из теста DBT-3.
В этой статье я сосредоточусь на следующих моментах рекурсивных ОТВ:
- обход дерева в глубину или в ширину
- предотвращение зацикливания с помощью UNION DISTINCT
- предотвращение зацикливания в более сложных случаях
Обход дерева в глубину или в ширину
Я уже рассматривал этот вопрос в предыдущем материале (в параграфе "Обход всего дерева"), но давайте резюмируем проблему и решение. Пусть у нас есть таблица людей с отношением родитель-ребенок.
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-а:
WITH RECURSIVE descendants AS
(
SELECT person
FROM tree
WHERE person='Thurimbert'
UNION ALL
SELECT t.person
FROM descendants d, tree t
WHERE t.parent=d.person
)
SELECT * FROM descendants;
+-------------+
| person |
+-------------+
| Thurimbert |
| Robert II |
| Cancor |
| Landrade |
| Ingramm |
| Robert III |
| Chaudegrand |
| Ermengarde |
+-------------+
Сортировка "в ширину" означает, что мы хотим видеть сначала всех детей, потом внуков и т.д. Именно такой порядок и вернул наш запрос (однако, по стандарту 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”, значение которого будет расширяться при переходе на более глубокий уровень, и отсортируем по нему:
WITH RECURSIVE descendants AS
(
SELECT person, CAST(person AS CHAR(500)) AS path
FROM tree
WHERE person='Thurimbert'
UNION ALL
SELECT t.person, CONCAT(d.path, ',', t.person)
FROM descendants d, tree t
WHERE t.parent=d.person
)
SELECT * FROM descendants ORDER BY path;
+-------------+---------------------------------+
| person | path |
+-------------+---------------------------------+
| Thurimbert | Thurimbert |
| Cancor | Thurimbert,Cancor |
| Ingramm | Thurimbert,Ingramm |
| Ermengarde | Thurimbert,Ingramm,Ermengarde |
| Landrade | Thurimbert,Landrade |
| Chaudegrand | Thurimbert,Landrade,Chaudegrand |
| Robert II | Thurimbert,Robert II |
| Robert III | Thurimbert,Robert II,Robert III |
+-------------+---------------------------------+
Я уже объяснял необходимость использования 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);
Обратите внимание, что правительство намеренно не предоставляет возможность вернуться обратно на Землю.
Давайте составим маршруты, по которым могут двигаться переселенцы: сначала определим планеты, имеющие прямое сообщение с Землей; потом те, до которых можно добраться с одной пересадкой, и т.д.:
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;
+---------+
| planet |
+---------+
| Mars |
| Jupiter |
| Saturn |
+---------+
Пусть к 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:
WITH RECURSIVE all_destinations AS
(
SELECT destination AS planet
FROM rockets
WHERE origin='Earth'
UNION DISTINCT
SELECT r.destination
FROM rockets r, all_destinations d
WHERE r.origin=d.planet
)
SELECT * FROM all_destinations;
+---------+
| planet |
+---------+
| Mars |
| Jupiter |
| Saturn |
| Earth |
+---------+
Предотвращение зацикливания в более сложных случаях
Итак, у нас работающий запрос с 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
Что? Снова зацикливание? Давайте, рассмотрим первые строки, генерируемые запросом:
- первоначально SELECT: Mars, 2
- итерация 1: Jupiter, 5 (2+3)
- итерация 2: Saturn, 9 (5+4)
- итерация 3: Earth, 18 (9+9)
- итерация 4: Mars, 20 (18+2)
Время в пути до Марса по маршруту 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.
WITH RECURSIVE all_destinations AS
(
SELECT destination AS planet, trip_time AS total_time,
CAST(destination AS CHAR(500)) AS path
FROM rockets
WHERE origin='Earth'
UNION ALL
SELECT r.destination, d.total_time+r.trip_time,
CONCAT(d.path, ',', r.destination)
FROM rockets r, all_destinations d
WHERE r.origin=d.planet
AND FIND_IN_SET(r.destination, d.path)=0
)
SELECT * FROM all_destinations;
+---------+------------+---------------------------+
| planet | total_time | path |
+---------+------------+---------------------------+
| Mars | 2 | Mars |
| Jupiter | 5 | Mars,Jupiter |
| Saturn | 9 | Mars,Jupiter,Saturn |
| Earth | 18 | Mars,Jupiter,Saturn,Earth |
+---------+------------+---------------------------+
Обратите внимание, если имя планеты может содержать запятую, то для корректной работы 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 |
+---------+------------+--------------------------------+----------+
“1” в столбце “is_cycle” указывает на цикл.
Вот и все на сегодня. Надеюсь, что показанные примеры помогут вам писать мощные запросы для управления иерархически данными. И как всегда: "Спасибо, что используете MySQL!".
Дата публикации: 4.07.2017
© Все права на данную статью принадлежат порталу SQLInfo.ru. Перепечатка в интернет-изданиях разрешается только с указанием автора и прямой ссылки на оригинальную статью. Перепечатка в бумажных изданиях допускается только с разрешения редакции.
|