Релиз MySQL 8.0 Labs: [Рекурсивные] Обобщенные Табличные Выражения в MySQL, часть 3 - иерархии
Дата: 3.11.2016
Данная статья является переводом статьи Гильема Бишота.
Это третья статья из цикла, посвященного обобщенным табличным выражениям (ОТВ), новой функциональности MySQL 8.0 доступной в этом Labs релизе. В первой статье мы рассмотрели новый синтаксис SQL и во второй использовали его для генерации последовательностей.
Сегодня мы рассмотрим самое популярное использование рекурсивных ОТВ: управление иерархическими данными. Т.е. данные в SQL таблицах представляют иерархию как:
- генеральный президент -> вице-президент -> руководитель -> сотрудник
- пункт -> подпункт -> подпункт подпункта
- родитель -> сын -> внук
- переписка по почте или на форуме (вопрос -> ответ -> ответ на ответ)
- город -> регион -> страна
Эти иерархии могут быть сколь угодно глубокими: это может быть структура большой корпорации или генеалогическое дерево многочисленного семейства, или жаркие дебаты по переписке ... Из таких данных можно получить ответы на множество интересных вопросов:
- Отдел кадров в попытке определить прохлаждается или загружен сотрудник интересуется: сколько человек прямо или косвенно подчиняются каждому сотруднику?
- Менеджер, рассматривающий вопрос об удалении товара X из каталога, спрашивает: какова стоимость всех комплектующих, необходимых для сборки X?
- Генеалогия: сколько людей является потомками миссис Х?
- Разработчики MySQL в попытке определить, какая функциональность вызывает больше всего проблем у пользователей, спрашивают: какие темы на форуме поддержки MySQL имели более 20 ответов в прошлом месяце?
На все эти вопросы можно получить ответы путем анализа иерархических данных. Как конкретно это сделать на практике, сильно зависит от выбранной модели данных. Есть как минимум две известных модели данных для представления иерархий:
- Списки смежности
- Вложенные множества
Мой бывший коллега Mike Hillyer составил прекрасное объяснение этих моделей: смотрите разделы "Введение", "Модель списка смежности" и "Модель вложенных множеств" по указанной ссылке. Материал был написан во времена MySQL 4.1, но всё ещё актуален.
В своей статье Майк делает 2 утверждения:
- средствами традиционного SQL трудно обрабатывать иерархии произвольного уровня вложенности: или придется писать хранимую процедуру (с циклами WHILE и вызовами рекурсивных процедур для нахождения пункта, затем подпункта, затем подпункта подпункта и т.д ), или, заранее определив максимальную глубину N, N раз объединять (JOIN) таблицу саму с собой.
- вложенные множества являются более простой в использовании альтернативой.
Однако, как мы вскоре увидим, с появлением рекурсивных ОТВ работа со списками смежности значительно упрощается.
Чтобы доказать своё утверждение, я для каждой проблемы, которую Майк решал с помощью вложенных множеств, покажу решение с использованием рекурсивных ОТВ и списков смежности. Для иллюстрации я буду использовать те же данные, что и Майк: таблица category, с полями category_id, name, parent: каждая строка содержит категорию, имеющую уникальный ID, имя и ID родительской категории. Например:
+-------------+----------------------+--------+
| category_id | name | parent |
+-------------+----------------------+--------+
| 1 | ELECTRONICS | NULL |
| 2 | TELEVISIONS | 1 |
| 3 | TUBE | 2 |
etc ...
“Tube” (ID 3) принадлежит категории “Televisions” (ID 2), которая в свою очередь принадлежит категории “Electronics” (ID 1); “Electronics” (ID 1) является наиболее общей категорией и не имеет родительской категории (NULL).
Я рекомендую посмотреть диаграмму в разделе "Введение" статьи Майка, она наглядно показывает иерархию категорий.
Итак, давайте приступим.
Обход всего дерева
WITH RECURSIVE cte AS
(
# источник рекурсии
SELECT category_id, name FROM category WHERE parent IS NULL
UNION ALL
# рекурсивный SELECT
SELECT c.category_id, c.name FROM category c JOIN cte
ON cte.category_id=c.parent # нахождение потомков
)
SELECT name FROM cte;
+-------------+----------------------+
| category_id | name |
+-------------+----------------------+
| 1 | ELECTRONICS |
| 2 | TELEVISIONS |
| 6 | PORTABLE ELECTRONICS |
| 3 | TUBE |
| 4 | LCD |
| 5 | PLASMA |
| 7 | MP3 PLAYERS |
| 9 | CD PLAYERS |
| 10 | 2 WAY RADIOS |
| 8 | FLASH |
+-------------+----------------------+
10 rows in set (0,00 sec)
Это работает следующим образом: начинаем обход с корня дерева, т.е. самой верхней/общей категории (которую определяем по условию WHERE parent IS NULL), это “Electronics”; далее получаем все категории, для которых найденная является родительской - это “Televisions” и “Portable Electronics”, т.е. категории, которые лежат на один уровень ниже чем “Electronics” и имеют первый уровень вложенности (иначе узлы первого уровня). Затем повторяем: находим все категории, для которых категории "первого уровня" являются родительскими; это даст нам категории "второго уровня". И так далее: на третьем уровне есть только одна категория “Flash”, не имеющая потомков, и рекурсивный SELECT ничего не найдет на четвертом уровне, т.е. не получит новых строк и ОТВ прекратит работу.
Вы можете заметить, что результат запроса такой же как и в статье Майка, но строки отсортированы в другом порядке. Майк использует ORDER BY node.lft за счет чего достигается так называемая сортировка "в глубину": потомки “Televisions” - (“Tube”, …) присутствуют в выдаче раньше, чем “Portable Electronics”. (Иными словами: при обходе дерева мы последовательно спускаемся до конца по каждой ветви.) В моём результате используется сортировка "в ширину" (сначала все узлы одного уровня, потом переход на следующий); однако, по стандарту SQL, если вы не указываете в явном виде ORDER BY, то порядок строк не гарантирован. Если мы хотим получить строки в определенном порядке, то его необходимо указать:
- для получения сортировки "в ширину": добавим целочисленный столбец “depth”, значение которого будет увеличиваться при переходе на более глубокий уровень, и отсортируем по нему:
WITH RECURSIVE cte AS
(
SELECT category_id, name, 0 AS depth FROM category WHERE parent IS NULL
UNION ALL
SELECT c.category_id, c.name, cte.depth+1 FROM category c JOIN cte ON
cte.category_id=c.parent
)
SELECT * FROM cte ORDER BY depth;
+-------------+----------------------+-------+
| category_id | name | depth |
+-------------+----------------------+-------+
| 1 | ELECTRONICS | 0 |
| 2 | TELEVISIONS | 1 |
| 6 | PORTABLE ELECTRONICS | 1 |
| 7 | MP3 PLAYERS | 2 |
| 9 | CD PLAYERS | 2 |
| 10 | 2 WAY RADIOS | 2 |
| 3 | TUBE | 2 |
| 4 | LCD | 2 |
| 5 | PLASMA | 2 |
| 8 | FLASH | 3 |
+-------------+----------------------+-------+
- для получения сортировки "в глубину": добавим строковый столбец “path”, значение которого будет расширяться при переходе на более глубокий уровень, и отсортируем по нему:
WITH RECURSIVE cte AS
(
SELECT category_id, name, CAST(category_id AS CHAR(200)) AS path
FROM category WHERE parent IS NULL
UNION ALL
SELECT c.category_id, c.name, CONCAT(cte.path, ",", c.category_id)
FROM category c JOIN cte ON cte.category_id=c.parent
)
SELECT * FROM cte ORDER BY path;
+-------------+----------------------+---------+
| category_id | name | path |
+-------------+----------------------+---------+
| 1 | ELECTRONICS | 1 |
| 2 | TELEVISIONS | 1,2 |
| 3 | TUBE | 1,2,3 |
| 4 | LCD | 1,2,4 |
| 5 | PLASMA | 1,2,5 |
| 6 | PORTABLE ELECTRONICS | 1,6 |
| 10 | 2 WAY RADIOS | 1,6,10 |
| 7 | MP3 PLAYERS | 1,6,7 |
| 8 | FLASH | 1,6,7,8 |
| 9 | CD PLAYERS | 1,6,9 |
+-------------+----------------------+---------+
Я уже объяснял необходимость использования CAST в прошлой статье: тип колонки "path" определяется в источнике рекурсии и он должен быть достаточно широким, чтобы вместить путь до самых глубоких листьев дерева; CAST это обеспечивает.
Получение всех листьев дерева
Здесь нет ничего нового, модель списков смежности отлично справлялась с этой задай изначально, для решения ОТВ не требуются: нужно просто найти строки, ID которых не присутствуют в столбце parent у других строк; это можно сделать с помощью LEFT JOIN или подзапроса с предикатом NOT EXISTS или NOT IN; Майк использовал LEFT JOIN, я для разнообразия применю подзапрос:
SELECT category_id, name FROM category
WHERE category_id NOT IN
# IDs of all parents:
(SELECT parent FROM category WHERE parent IS NOT NULL);
+-------------+--------------+
| category_id | name |
+-------------+--------------+
| 3 | TUBE |
| 4 | LCD |
| 5 | PLASMA |
| 8 | FLASH |
| 9 | CD PLAYERS |
| 10 | 2 WAY RADIOS |
+-------------+--------------+
6 rows in set (0,00 sec)
Получение пути до узла
Говорят, что путь для “Flash” начинается с “Flash”, далее его родитель, потом родитель его родителя и так далее до самого верха (иными словами, нужно получить всех предков заданного узла):
WITH RECURSIVE cte AS
(
SELECT name, parent FROM category WHERE name='FLASH'
UNION ALL
SELECT c.name, c.parent FROM category c JOIN cte
ON c.category_id=cte.parent # получение родителя
)
SELECT * FROM cte;
+----------------------+--------+
| name | parent |
+----------------------+--------+
| FLASH | 7 |
| MP3 PLAYERS | 6 |
| PORTABLE ELECTRONICS | 1 |
| ELECTRONICS | NULL |
+----------------------+--------+
4 rows in set (0,00 sec)
Порядок строк от потомка к родителю; если нужен обратный, добавьте колонку depth и сортируйте по ней:
WITH RECURSIVE cte AS
(
SELECT name, parent, 0 as depth FROM category WHERE name='FLASH'
UNION ALL
SELECT c.name, c.parent, cte.depth-1 FROM category c JOIN cte
ON c.category_id=cte.parent
)
SELECT * FROM cte ORDER BY depth;
+----------------------+--------+-------+
| name | parent | depth |
+----------------------+--------+-------+
| ELECTRONICS | NULL | -3 |
| PORTABLE ELECTRONICS | 1 | -2 |
| MP3 PLAYERS | 6 | -1 |
| FLASH | 7 | 0 |
+----------------------+--------+-------+
Определение уровня вложенности всех узлов
Мы хотим, чтобы потомки располагались сразу после родителя с отступом вправо. Т.е. мы хотим сортировку "в глубину", для чего нам потребуется колонка path. Количество необходимых отступов легко вычислить путем добавления колонки depth (альтернативный вариант - определять глубину вложенности как количество запятых в колонке path):
WITH RECURSIVE cte AS
(
SELECT category_id, CAST(name AS CHAR(200)) AS name,
CAST(category_id AS CHAR(200)) AS path,
0 as depth
FROM category WHERE parent IS NULL
UNION ALL
SELECT c.category_id,
CONCAT(REPEAT(' ', cte.depth+1), c.name), # отступ
CONCAT(cte.path, ",", c.category_id),
cte.depth+1
FROM category c JOIN cte ON
cte.category_id=c.parent
)
SELECT * FROM cte ORDER BY path;
+-------------+-----------------------+---------+-------+
| category_id | name | path | depth |
+-------------+-----------------------+---------+-------+
| 1 | ELECTRONICS | 1 | 0 |
| 2 | TELEVISIONS | 1,2 | 1 |
| 3 | TUBE | 1,2,3 | 2 |
| 4 | LCD | 1,2,4 | 2 |
| 5 | PLASMA | 1,2,5 | 2 |
| 6 | PORTABLE ELECTRONICS | 1,6 | 1 |
| 10 | 2 WAY RADIOS | 1,6,10 | 2 |
| 7 | MP3 PLAYERS | 1,6,7 | 2 |
| 8 | FLASH | 1,6,7,8 | 3 |
| 9 | CD PLAYERS | 1,6,9 | 2 |
+-------------+-----------------------+---------+-------+
10 rows in set (0,00 sec)
Получение всех потомков заданного узла
Мы хотим для определенной категории получить все под-категории вместе с их уровнем вложенности. Процесс получения начнем с заданной категории, которая является корнем под-дерева, и добавим колонку depth. Результат нам нужен отсортированный "в глубину", поэтому понадобится колонка path:
WITH RECURSIVE cte AS
(
SELECT category_id, name,
CAST(category_id AS CHAR(200)) AS path,
0 as depth
FROM category WHERE name='PORTABLE ELECTRONICS' # sub-tree root
UNION ALL
SELECT c.category_id,
c.name,
CONCAT(cte.path, ",", c.category_id),
cte.depth+1
FROM category c JOIN cte
ON cte.category_id=c.parent
)
SELECT * FROM cte ORDER BY path;
+-------------+----------------------+-------+-------+
| category_id | name | path | depth |
+-------------+----------------------+-------+-------+
| 6 | PORTABLE ELECTRONICS | 6 | 0 |
| 10 | 2 WAY RADIOS | 6,10 | 1 |
| 7 | MP3 PLAYERS | 6,7 | 1 |
| 8 | FLASH | 6,7,8 | 2 |
| 9 | CD PLAYERS | 6,9 | 1 |
+-------------+----------------------+-------+-------+
5 rows in set (0,00 sec)
Найти прямых потомков заданного узла
Запрос такой же как и предыдущий, но добавляется условие depth=0, чтобы найти только непосредственных потомков, и не нужна колонка path, так как все потомки находятся на одном уровне:
WITH RECURSIVE cte AS
(
SELECT category_id, name, 0 as depth
FROM category WHERE name='PORTABLE ELECTRONICS'
UNION ALL
SELECT c.category_id, c.name, cte.depth+1
FROM category c JOIN cte
ON cte.category_id=c.parent
WHERE cte.depth=0
)
SELECT * FROM cte;
+-------------+----------------------+-------+
| category_id | name | depth |
+-------------+----------------------+-------+
| 6 | PORTABLE ELECTRONICS | 0 |
| 7 | MP3 PLAYERS | 1 |
| 9 | CD PLAYERS | 1 |
| 10 | 2 WAY RADIOS | 1 |
+-------------+----------------------+-------+
4 rows in set (0,00 sec)
Агрегатные функции во вложенных множествах
Добавим таблицу товаров, такую же как у Майка, и посчитаем сколько товаров содержит каждая категория с учетом вложенных категорий. Сначала мы получим категории, которые непосредственно содержат товары, затем будем соединять (JOIN) полученный результат с их родителями, чтобы для родительских категорий учесть товары относящиеся к потомкам. Чтобы в итоговом запросе получить по одной строке для каждой категории с количеством прямо/косвенно содержащихся в ней товаров, нам нужно сгруппировать результат ОТВ по имени категории:
WITH RECURSIVE cte AS
(
SELECT c.category_id, c.name AS cat_name, c.parent, p.name AS prod_name
FROM category c JOIN product p ON c.category_id=p.category_id
UNION ALL
SELECT c.category_id, c.name, c.parent, cte.prod_name
FROM cte JOIN category c ON c.category_id=cte.parent
)
SELECT cat_name, COUNT(*) AS prod_in_cat FROM cte
GROUP BY cat_name;
+----------------------+-------------+
| cat_name | prod_in_cat |
+----------------------+-------------+
| 2 WAY RADIOS | 1 |
| CD PLAYERS | 2 |
| ELECTRONICS | 10 |
| FLASH | 1 |
| LCD | 1 |
| MP3 PLAYERS | 2 |
| PLASMA | 2 |
| PORTABLE ELECTRONICS | 5 |
| TELEVISIONS | 5 |
| TUBE | 2 |
+----------------------+-------------+
10 rows in set (0,01 sec)
Заключение
Сегодня с помощью рекурсивных ОТВ можно ответить на сложные вопросы по иерархическим данным, представленным в виде списков смежности: получение всех потомков/предков заданного узла, определение уровня вложенности, обход всего дерева, сортировка "в глубину" или "в ширину" и т.д.
Значит ли это, что модель вложенных множеств больше не актуальна? Нет. Если вы сравните запросы Майка с моими, то заметите, что его часто короче. С другой стороны, в модели вложенных множеств при добавлении/удалении узла требуются несколько запросов и управление конкурентным доступом (подробнее смотрите разделы “Adding new nodes” и “Deleting nodes” в статье Майка). В то время как в модели списков смежности добавление нового узла - это один короткий INSERT. Более легкие вставки и сложные чтения в этой модели легко объяснить тем, что в таблице не содержится вспомогательных данных (есть только одна колонка указывающая на непосредственного родителя). В модели вложенных множеств хранится больше дополнительной информации в виде числовых интервалов lft и rgt (с каждой строкой в таблице могут быть сопоставлены 2 другие); это облегчает чтение, так как доступно больше информации, но усложняет изменение данных, так как для сохранения согласованности данных требуется обработать и изменить сразу много строк.
Пища для размышлений...
Это была длинная статья... будет уместно сказать:
select uncompress(x'1F000000789C0BC948CCCB56A8CC2F5548CB2F52284A4D4CC9CC4B5728C9C82C56484B2C520400B5BD0B27') as final_words;
+---------------------------------+
| final_words |
+---------------------------------+
| Thank you for reading this far! |
+---------------------------------+
Дата публикации: 3.11.2016
© Все права на данную статью принадлежат порталу SQLInfo.ru. Перепечатка в интернет-изданиях разрешается только с указанием автора и прямой ссылки на оригинальную статью. Перепечатка в бумажных изданиях допускается только с разрешения редакции.
|
