SQLinfo.ru - Все о MySQL

WITH RECURSIVE и MySQL

Дата: 8.10.2016

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

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

Предположим, что таблица Т1 имеет 3 колонки:


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. Таким образом, при вызове процедуры мы должны изменить последний запрос в её аргументах:


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 ID, NAME, MANAGER_ID, SUM(REPORTS)
  FROM EMPLOYEES_EXTENDED
  GROUP BY ID, NAME, MANAGER_ID
"
,
0,
""
);
 

И вот, наконец, правильный результат:


+------+---------+------------+--------------+
| 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 ;
 
Дата публикации: 8.10.2016

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

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