WITH RECURSIVE и MySQL - статьи sqlinfo.ru

Статья является переводом статьи Гильема Бишота про эмуляцию обобщенных табличных выражений с помощью хранимой процедуры. Курсивом даны комментарии переводчика. В данный момент (октябрь 2016) рекурсивные обобщенные табличные выражения реализованы в версиях MySQL/MariaDB, находящихся в стадии разработки. До выхода стабильных версий метод, предложенный Гильямом, будет актуален.

Если вы используете определенные СУБД или читали последние версии стандарта SQL, вероятно вы слышали об операторе WITH в SQL. Некоторые используют термин Subquery Factoring, другие - обобщенные табличные выражения. В простейшей форме это своего рода "улучшенная производная таблица".

CREATE TABLE T1(
YEAR INT, # 2000, 2001, 2002 ...
MONTH INT, # January, February, ...
SALES INT # сумма продаж за месяц
);

Теперь я хочу узнать тренд продаж (увеличение/уменьшение) по годам:

SELECT D1.YEAR, (CASE WHEN D1.S<D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
(SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D1,
(SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D2
WHERE D1.YEAR = D2.YEAR-1;

Обе производные таблицы основаны на одном и том же подзапросе, но, как правило, СУБД недостаточно умны, чтобы осознать это. Таким образом, подзапрос будет вычислен дважды! Первый раз, чтобы заполнить D1, второй - D2. Это ограничение иногда указывается как "невозможно дважды обратиться к производной таблице в одном запросе".
Такие двойные вычисления могут привести к проблемам с производительностью. При использовании WITH такого ограничения не существует, и в следующем запросе подзапрос будет вычислен только один раз:

WITH D AS (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR)
SELECT D1.YEAR, (CASE WHEN D1.S<D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
D AS D1,
D AS D2
WHERE D1.YEAR = D2.YEAR-1;

Это демонстрирует одно из преимуществ WITH. В MySQL пока нет поддержки WITH, но их можно эмулировать с помощью представлений:

CREATE VIEW D AS (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR);
SELECT D1.YEAR, (CASE WHEN D1.S<D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
D AS D1,
D AS D2
WHERE D1.YEAR = D2.YEAR-1;
DROP VIEW D;

Вместо представления, я мог бы создать D как обычную таблицу. Но не временную, так как ко временной таблице невозможно дважды обратиться в одном запросе, как это указано в документации. Один из самых старых багов. Исправлен в MariaDB 10.2.1

После этого короткого введения, показывающего простейшую форму WITH, я хотел бы перейти к рассмотрению более сложной формы WITH: рекурсивной форме.
В соответствии со стандартом SQL, при использовании рекурсивной формы нужно писать WITH RECURSIVE. Однако, как показывают наблюдения, некоторые СУБД не требуют обязательного использования ключевого слова RECURSIVE.
WITH RECURSIVE - мощный инструмент. Например, с его помощью можно делать то же, что и с помощью конструкции CONNECT BY в Оракле.
Давайте разберем пример, чтобы понять как работает WITH RECURSIVE.

Предположим, у нас есть таблица сотрудников (это классический пример при иллюстрации возможностей WITH RECURSIVE):

CREATE TABLE EMPLOYEES (
ID INT PRIMARY KEY,
NAME VARCHAR(100),
MANAGER_ID INT,
INDEX (MANAGER_ID),
FOREIGN KEY (MANAGER_ID) REFERENCES EMPLOYEES(ID)
);
INSERT INTO EMPLOYEES VALUES
(333, "Yasmina", NULL),
(198, "John", 333),
(29, "Pedro", 198),
(4610, "Sarah", 29),
(72, "Pierre", 29),
(692, "Tarek", 333);

Другими словами, Yasmina директор, а John и Tarek его подчиненные. Pedro подчиняется John, а Sarah и Pierre подчиняются Pedro.
Для большой компании в такой таблице будут тысячи строк.

Теперь мы хотим узнать для каждого сотрудника - сколько людей прямо и косвенно подчиняются ему. Я бы сделал это следующим образом. Сначала я составлю список людей, которые не имеют подчиненных: подзапросом я получаю список всех руководителей и с помощью NOT IN (подзапрос) я получу список людей, которые не являются руководителями:

SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
FROM EMPLOYEES
WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL);

Затем я помещу полученный результат в новую таблицу EMPLOYEES_EXTENDED. EXTENDED означает "расширенная с дополнительной информацией", новые данные находятся в четвертой колонке REPORTS, содержащей число людей, прямо или косвенно подчиняющихся сотруднику. Так как мы получили список сотрудников, не имеющих подчиненных, то в колонке REPORTS у них будет значение 0.

Теперь можно составить список руководителей "первого уровня" (тех кто непосредственно управляет сотрудниками, не имеющих подчиненных):

SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
GROUP BY M.ID, M.NAME, M.MANAGER_ID;

Объяснение: для каждой строки из М (т.е. таблицы сотрудников) JOIN даст 0 или более строк, по одной на каждого работника, которые напрямую подчиняются сотруднику.
Каждый такой подчиненный вносит вклад в величину REPORTS его начальника с помощью двух чисел: 1 - самого себя и количества своих собственных подчиненных.
Иными словами: JOIN для каждого сотрудника из таблицы EMPLOYEES_EXTENDED добавляет информацию о его начальнике. Так как у разных сотрудников может быть один начальник, то мы производим группировку выборки по ID начальника. Для правильного подсчета количества подчиненных у начальника нужно просуммировать как его непосредственных подчиненных (те кто находятся в таблице EMPLOYEES_EXTENDED), так и подчиненных своих подчиненных (количество которых храниться в E.REPORTS); отсюда и появляется SUM(1+E.REPORTS)

Затем очистим таблицу EMPLOYEES_EXTENDED и поместим в неё полученную выборку, которая описывает руководителей "первого уровня". Повторим тот же самый запрос для получения информации о руководителях "второго уровня". И так далее.
Наступит момент, когда в таблице EMPLOYEES_EXTENDED будет только одна строка, содержащая данные на Yasmina. Выполнив наш запрос в очередной раз, мы получим пустую выборку, так как у Yasmina нет начальника (он сам директор; его E.MANAGER_ID равно NULL).

Подведем итоги: EMPLOYEES_EXTENDED - своего рода временный буфер, который последовательно содержал сотрудников, не имеющих подчиненных, руководителей первого уровня, второго и так далее. Мы использовали рекурсию. Ответом для исходной задачи будет объединение всех промежуточных состояний EMPLOYEES_EXTENDED.

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

WITH RECURSIVE
# временный буфер, который также используется для хранения объединения (UNION) всех промежуточных результатов:
EMPLOYEES_EXTENDED
AS
(
# источник рекурсии:
SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
FROM EMPLOYEES
WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
UNION ALL
# элемент рекурсии:
SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
GROUP BY M.ID, M.NAME, M.MANAGER_ID
)
# что мы хотим сделать с итоговым результатом, полученным путем объединения (UNION) всех промежуточных результатов:
SELECT * FROM EMPLOYEES_EXTENDED;

MySQL пока ещё не поддерживает WITH RECURSIVE, но можно написать универсальную хранимую процедуру, которая будет реализовывать такую функциональность. Вот как будет выглядеть вызов такой процедуры:

CALL WITH_EMULATOR(
"EMPLOYEES_EXTENDED",
"
SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
FROM EMPLOYEES
WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
",
"
SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
GROUP BY M.ID, M.NAME, M.MANAGER_ID
",
"SELECT * FROM EMPLOYEES_EXTENDED",
0,
""
);

Как вы могли уже догадаться, аргументами хранимой процедуры являются части стандартного синтаксиса WITH: имя временного буфера, источник рекурсии, элемент рекурсии, и что делать с конечным результатом. Два последних аргумента - 0 и пустая строка - это детали, на которые вы пока можете не обращать внимания.

Вот результат, возвращаемый хранимой процедурой:

+------+---------+------------+---------+
| ID | NAME | MANAGER_ID | REPORTS |
+------+---------+------------+---------+
| 72 | Pierre | 29 | 0 |
| 692 | Tarek | 333 | 0 |
| 4610 | Sarah | 29 | 0 |
| 29 | Pedro | 198 | 2 |
| 333 | Yasmina | NULL | 1 |
| 198 | John | 333 | 3 |
| 333 | Yasmina | NULL | 4 |
+------+---------+------------+---------+
7 rows in set

Обратите внимание: Pierre, Tarek и Sarah не имеют подчиненных, у Pedro их двое - это похоже на правду. Однако, Yasmina присутствует в выборке дважды! Странно? И да, и нет. Иерархия сотрудников является деревом, где Yasmina - корень, а сотрудники, не имеющие подчиненных - листья. Наш алгоритм начинается с листьев, затем проходит по руководителям первого уровня, т.е. непосредственным родителям листьев. Потом по руководителям второго уровня и т.д. Но Yasmina является одновременно и руководителем первого уровня для Tarek, и руководителем третьего уровня для Pierre и Sarah. Поэтому Yasmina появляется дважды в окончательном результате: один раз на ветке дерева, которая заканчивается листом Tarek и один раз на ветке дерева, заканчивающейся листьями Pierre и Sarah. Первая ветвь дерева содержит одного подчиненного, вторая - четырёх. Правильный ответ, который мы хотим получить, является их суммой: 5. Таким образом, при вызове процедуры мы должны изменить последний запрос в её аргументах:

+------+---------+------------+--------------+
| ID | NAME | MANAGER_ID | SUM(REPORTS) |
+------+---------+------------+--------------+
| 29 | Pedro | 198 | 2 |
| 72 | Pierre | 29 | 0 |
| 198 | John | 333 | 3 |
| 333 | Yasmina | NULL | 5 |
| 692 | Tarek | 333 | 0 |
| 4610 | Sarah | 29 | 0 |
+------+---------+------------+--------------+
6 rows in set

Давайте закончим, показав тело хранимой процедуры. В ней активно используется динамический SQL с помощью подготовленных выражений. Тело процедуры не зависит от конкретной проблемы, которую нужно решить, оно универсально и подходит для других случаев использования WITH RECURSIVE. Я добавил комментарии внутрь тела процедуры, поэтому оно должно быть самоочевидным. Если это не так, не стесняйтесь спрашивать в комментариях, и я объясню подробней. Обратите внимание, что процедура использует временные таблицы, и первое, что она делает - удаляет другие временные таблицы с такими же именами.

# вместо стандартного синтаксиса:
# WITH RECURSIVE recursive_table AS
# (initial_SELECT
# UNION ALL
# recursive_SELECT)
# final_SELECT;
# вы должны использовать
# CALL WITH_EMULATOR(recursive_table, initial_SELECT, recursive_SELECT,
# final_SELECT, 0, "").

# Алгоритм:
# 1) имеется исходная таблица T0 (настоящим именем таблицы является значение первого аргумента процедуры
# "recursive_table"), эта таблица заполняется результатом выполнения initial_SELECT.
# 2) таблица U служит для объединения промежуточных результатов, первоначально пуста.
# 3) Цикл:
# добавить строки из T0 в U,
# выполнить recursive_SELECT на основе T0 и поместить результат в таблицу T1,
# если T1 пустая
# то завершить цикл,
# иначе T0 переименовать в T1 (а Т1 в Т0) и очистить T1
# 4) удалить T0, T1
# 5) переименовать U в T0
# 6) выполнить final_SELECT, отдать результат клиенту

# Этот алгоритм рассчитан на работу с одной рекурсивной таблицей.
# Можно было бы написать хранимую процедуру, создающую несколько рекурсивных таблиц.

delimiter |

CREATE PROCEDURE WITH_EMULATOR(
recursive_table varchar(100), # имя рекурсивной таблицы
initial_SELECT varchar(65530), # источник рекурсии
recursive_SELECT varchar(65530), # элемент рекурсии
final_SELECT varchar(65530), # финальный SELECT, выполняющийся над объединенным результатом
max_recursion int unsigned, # защита от бесконечного цикла, используйте 0 по умолчанию
create_table_options varchar(65530) # тут можно задать опции, которые будут использоваться в
# операторе CREATE TABLE при создании рекурсивной таблицы с целью ускорения
# запросов (initial_SELECT/recursive_SELECT/final_SELECT; например:
# "(KEY(some_column)) ENGINE=MEMORY"
)

BEGIN
declare new_rows int unsigned;
declare show_progress int default 0; # установите 1 при отладке выполнения
declare recursive_table_next varchar(120);
declare recursive_table_union varchar(120);
declare recursive_table_tmp varchar(120);
set recursive_table_next = concat(recursive_table, "_next");
set recursive_table_union = concat(recursive_table, "_union");
set recursive_table_tmp = concat(recursive_table, "_tmp");

# Удаление всех временных таблиц с именами, которые будут использоваться в этой процедуре
SET @str =
CONCAT("DROP TEMPORARY TABLE IF EXISTS ", recursive_table, ",",
recursive_table_next, ",", recursive_table_union,
",", recursive_table_tmp);
PREPARE stmt FROM @str;
EXECUTE stmt;

# Если нужно ссылаться на recursive_table более
# одного раза в recursive_SELECT, удалите ключевое слово TEMPORARY .
SET @str = # создание и заполнение T0
CONCAT("CREATE TEMPORARY TABLE ", recursive_table, " ",
create_table_options, " AS ", initial_SELECT);
PREPARE stmt FROM @str;
EXECUTE stmt;
SET @str = # создание U
CONCAT("CREATE TEMPORARY TABLE ", recursive_table_union, " LIKE ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
SET @str = # создание T1
CONCAT("CREATE TEMPORARY TABLE ", recursive_table_next, " LIKE ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
if max_recursion = 0 then
set max_recursion = 100; # по умолчанию для предотвращения бесконечного цикла
end if;
recursion: repeat
# добавляем строки из T0 в U (всегда с помощью UNION ALL)
SET @str =
CONCAT("INSERT INTO ", recursive_table_union, " SELECT * FROM ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
# цикл будет прерван как только счетчик max_recursion уменьшится до 0
set max_recursion = max_recursion - 1;
if not max_recursion then
if show_progress then
select concat("max recursion exceeded"); # вероятно select "max recursion exceeded";
end if;
leave recursion;
end if;
# выполняем recursive_SELECT на основе T0 и помещаем результат в Т1
SET @str =
CONCAT("INSERT INTO ", recursive_table_next, " ", recursive_SELECT);
PREPARE stmt FROM @str;
EXECUTE stmt;
# прерываем цикл, если в T1 нет строк
select row_count() into new_rows;
if show_progress then
select concat(new_rows, " new rows found");
end if;
if not new_rows then
leave recursion;
end if;
# Подготовка к следующей итерации:
# T1 становится T0, чтобы стать источником получения новых строк при выполнении recursive_SELECT,
# T0 становится T1.
SET @str =
CONCAT("ALTER TABLE ", recursive_table, " RENAME ", recursive_table_tmp);
PREPARE stmt FROM @str;
EXECUTE stmt;
# используется ALTER TABLE RENAME, так как RENAME TABLE не поддерживает временные таблицы
SET @str =
CONCAT("ALTER TABLE ", recursive_table_next, " RENAME ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
SET @str =
CONCAT("ALTER TABLE ", recursive_table_tmp, " RENAME ", recursive_table_next);
PREPARE stmt FROM @str;
EXECUTE stmt;
# очищается T1
SET @str =
CONCAT("TRUNCATE TABLE ", recursive_table_next);
PREPARE stmt FROM @str;
EXECUTE stmt;
until 0 end repeat;
# удаляются T0 и T1
SET @str =
CONCAT("DROP TEMPORARY TABLE ", recursive_table_next, ", ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
# Объединению промежуточных результатов присваивается имя recursive_table
SET @str =
CONCAT("ALTER TABLE ", recursive_table_union, " RENAME ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
# Выполнение окончательного запроса
SET @str = final_SELECT;
PREPARE stmt FROM @str;
EXECUTE stmt;
# Удаление ненужных временных таблиц:
SET @str =
CONCAT("DROP TEMPORARY TABLE ", recursive_table);
PREPARE stmt FROM @str;
EXECUTE stmt;
# Мы сделали это :-)
END|

delimiter ;

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