Обзор рекурсивных общих табличных выражений

Общие табличные выражения (CTE) — стандартная функция SQL, представляющая собой по существу временные именованные наборы результатов. CTE впервые появились в стандарте SQL в 1999 году, а первые реализации появились в 2007 году.

Существует два вида CTE:

• Нерекурсивные
• Рекурсивные, о которых идёт речь в этой статье.

SQL в целом плохо справляется с рекурсивными структурами.

CTE позволяют запросу ссылаться на себя. Рекурсивное CTE многократно выполняет подмножества данных до получения полного набора результатов. Это делает его особенно полезным для обработки иерархических или древовидных данных. max_recursive_iterations предотвращает бесконечные циклы.

Пример синтаксиса

WITH RECURSIVE обозначает рекурсивное CTE. Ему присваивается имя, за которым следует тело (основной запрос) следующим образом:

Вычисление

Учитывая следующую структуру:

Сначала выполняется якорная часть запроса:

Затем выполняется рекурсивная часть запроса:

Резюме

with recursive R as (
  select anchor_data
  union [all]
  select recursive_part
  from R, ...
)
select ...

1. Вычислить anchor_data
2. Вычислить recursive_part, чтобы получить новые данные
3. если (новые данные не пустые) перейти к 2;

Преобразование для предотвращения усечения данных

Как реализовано в настоящее время MariaDB и в соответствии со стандартом SQL, данные могут быть усечены, если не преобразованы должным образом. Необходимо преобразовать столбец к соответствующей ширине, если рекурсивная часть CTE создаёт более широкие значения для столбца, чем нерекурсивная часть CTE. Некоторые другие СУБД в этой ситуации выдают ошибку, а поведение MariaDB может измениться в будущем — см. MDEV-12325. См. примеры ниже.

Примеры

Транзитивное замыкание — определение пунктов назначения автобуса

Образцы данных:

CREATE TABLE bus_routes (origin varchar(50), dst varchar(50));
INSERT INTO bus_routes VALUES 
  ('New York', 'Boston'), 
  ('Boston', 'New York'), 
  ('New York', 'Washington'), 
  ('Washington', 'Boston'), 
  ('Washington', 'Raleigh');

Теперь мы хотим вернуть пункты назначения автобуса с Нью-Йорком в качестве отправной точки:

WITH RECURSIVE bus_dst as ( 
    SELECT origin as dst FROM bus_routes WHERE origin='New York' 
  UNION
    SELECT bus_routes.dst FROM bus_routes JOIN bus_dst ON bus_dst.dst= bus_routes.origin 
) 
SELECT * FROM bus_dst;
+------------+
| dst        |
+------------+
| New York   |
| Boston     |
| Washington |
| Raleigh    |
+------------+

Вышеупомянутый пример вычисляется следующим образом:

Сначала вычисляются якорные данные:

• Начинаем с Нью-Йорка
• Добавляются Бостон и Вашингтон

Затем рекурсивная часть:

• Начинаем с Бостона и затем Вашингтона
• Добавляется Роли
• UNION исключает узлы, которые уже присутствуют.

Вычисление путей — определение маршрутов автобусов

На этот раз мы пытаемся получить маршруты автобусов, такие как «Нью-Йорк -> Вашингтон -> Роли».

Используя те же образцы данных, что и в предыдущем примере:

WITH RECURSIVE paths (cur_path, cur_dest) AS (
    SELECT origin, origin FROM bus_routes WHERE origin='New York' 
  UNION
    SELECT CONCAT(paths.cur_path, ',', bus_routes.dst), bus_routes.dst 
     FROM paths
     JOIN bus_routes 
       ON paths.cur_dest = bus_routes.origin AND 
         NOT FIND_IN_SET(bus_routes.dst, paths.cur_path)
) 
SELECT * FROM paths;
+-----------------------------+------------+
| cur_path                    | cur_dest   |
+-----------------------------+------------+
| New York                    | New York   |
| New York,Boston             | Boston     |
| New York,Washington         | Washington |
| New York,Washington,Boston  | Boston     |
| New York,Washington,Raleigh | Raleigh    |
+-----------------------------+------------+

Преобразование для предотвращения усечения данных

В следующем примере данные усекаются, потому что результаты не явно преобразованы к достаточно широкому типу:

WITH RECURSIVE tbl AS (
  SELECT NULL AS col
  UNION
  SELECT "THIS NEVER SHOWS UP" AS col FROM tbl
)
SELECT col FROM tbl
+------+
| col  |
+------+
| NULL |
|      |
+------+

Для устранения этого используйте явное преобразование CAST:

WITH RECURSIVE tbl AS (
  SELECT CAST(NULL AS CHAR(50)) AS col
  UNION SELECT "THIS NEVER SHOWS UP" AS col FROM tbl
)  
SELECT * FROM tbl;
+---------------------+
| col                 |
+---------------------+
| NULL                |
| THIS NEVER SHOWS UP |
+---------------------+