SQLinfo.ru - Все о MySQL

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

Дата: 4.07.2017

Данная статья является переводом статьи Гильема Бишота.

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

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

  1. обход дерева в глубину или в ширину
  2. предотвращение зацикливания с помощью UNION DISTINCT
  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-а:

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. Перепечатка в интернет-изданиях разрешается только с указанием автора и прямой ссылки на оригинальную статью. Перепечатка в бумажных изданиях допускается только с разрешения редакции.

Статьи :
 Установка и настройка MySQL
 Коды ошибок в MySQL
>Программирование в MySQL
 Оптимизация производительности
 Кодировка символов в MySQL
 Хранение данных в MySQL
 MySQL Cluster
См. также:
 Оптимизация производительности MySQL
 Онлайн-курс по оптимизации MySQL
 Услуги по оптимизации MySQL