SQLinfo.ru - Все о MySQL

Релиз MySQL 8.0 Labs: [Рекурсивные] Обобщенные Табличные Выражения в MySQL, часть 2 - как генерировать последовательность

Дата: 29.10.2016

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

Это вторая статья из цикла, посвященного обобщенным табличным выражениям (ОТВ), новой функциональности MySQL 8.0 доступной в этом Labs релизе. Первая статья заканчивается словами:

Внутри определения рекурсивного ОТВ (то, что находится в AS (…)) существуют некоторые ограничения синтаксиса [...]

  • рекурсивный SELECT не может содержать GROUP BY, агрегатные функции (например, SUM), ORDER BY, LIMIT, DISTINCT (это ограничение не распространяется на нерекурсивный SELECT)
  • рекурсивный SELECT должен ссылаться на ОТВ, в котором определен, только один раз и только в части FROM, а не в любом подзапросе. Конечно он может ссылаться также и на другие таблицы и объединять их со своим ОТВ с помощью join, что очень удобно для построения иерархий (например, если у нас есть таблица боссов и сотрудников, и мы хотим узнать "кто подчиняется прямо или косвенно миссис Х?"). Если соединение происходит с помощью LEFT JOIN, то ОТВ не должно быть на правой стороне.

Пришло время дать объяснения этих ограничений, происходящих из стандарта SQL (за исключением запрета использования ORDER BY, LIMIT и DISTINCT, который специфичен для MySQL, хотя также присутствует и в некоторых других популярных СУБД). Рассмотрим пример, производящий целые числа от 1 до 10:

WITH RECURSIVE my_cte AS
(
  SELECT 1 AS n
  UNION ALL
  SELECT 1+n FROM my_cte WHERE n<10  # <- рекурсивный SELECT (он же элемент рекурсии)
)
SELECT * FROM my_cte;

Глядя на рекурсивный SELECT, складывается впечатление, что процесс получения новых строк оперирует набором строк из my_cte, так как делает select .. from my_cte. Но это не так, в действительности, он последовательно действует на каждую строку изолированно от других строк из my_cte. Вы можете рассматривать рекурсивный SELECT как процесс, который на основании одной строки из промежуточного набора N без информации о других строках этого набора получает новые строки для промежуточного набора N+1, и повторяет действие для других строк из N до тех пор пока не пройдет их все, после чего переходит к строке из набора N+1 и т.д.

Учитывая это правило, обратим внимание на то, что:

  • GROUP BY требует наличия всех строк, чтобы разбить их на группы,
  • также это необходимо для агрегатных функций, например, SUM,
  • ORDER BY нужны все строки, чтобы отсортировать их,
  • LIMIT отбрасывает строки на основе подсчета других строк,
  • DISTINCT исключает строки на основании наличия других строк,
  • при двукратном упоминании my_cte в части FROM для строки из my_cte нужна другая строка из my_cte для их соединения,
  • при использовании my_cte в части FROM и в подзапросе для каждой строки из my_cte в части FROM потребуются другие строки из my_cte для вычисления подзапроса,
  • при использовании my_cte на правой стороне LEFT JOIN нужны будут все строки из my_cte, чтобы узнать есть ли соответствие со значением на левой стороне.

Учитывая, что рекурсивный SELECT имеет доступ только к одной строке за раз, становится понятно почему все вышеперечисленные варианты запрещено использовать в элементе рекурсии.

Это правило SQL дает два преимущества: во-первых, СУБД имеет возможность генерировать строки в произвольной последовательности; во-вторых, запрещает немало необоснованных запросов.

Чтобы увидеть как это влияет на шаблоны запросов, давайте напишем рекурсивный запрос для генерации чисел Фибоначи - последовательности, которая начинается с двух единиц, и каждый следующий член которой является суммой двух предыдущих. Т.е. 1, 1, 2, 3, 5, 8, ... , (N+2)= (N+1) + N.

Сначала положим первые два числа (1 и 1) в источник рекурсии:


SELECT 1 as f # первое число; "f"  означает число Фибоначи
UNION ALL
SELECT 1 # второе число
 
затем генерируем остальные числа с помощью:

SELECT cte_n.f + cte_n_plus_1.f
FROM my_cte AS cte_n JOIN my_cte AS cte_n_plus_1
ON ... какое условие здесь поставить?
 

Моя идея: взять N-ый и (N+1)-ый элементы, которые уже присутствуют в my_cte, и просуммировать их; следовательно: берем строку из my_cte, содержащую N-ый элемент, и строку из my_cte, содержащую (N+1)-ый элемент и суммируем их; чтобы взять две строки одновременно, я использую SQL JOIN, но возникает вопрос - как убедится, что соединяются нужные пары чисел? Мне нужно добавить в условие соединения что-то вроде - "строка из cte_n_plus_1 должна содержать число, которое следует сразу после числа, содержащегося в строке из cte_n". В противном случае, я также буду суммировать 5-ый и 9-ый элементы и любые другие! Т.е. мне необходимо добавить в таблицу поле, содержащее порядковый номер. Хорошо, давайте добавим порядковые номера в источник рекурсии:


SELECT 1 as f, 1 as n UNION ALL SELECT 1, 2
# "f" : число Фибоначи; "n": порядковый номер,
# первая строка: содержит значение 1 и её порядковый номер - 1
# вторая строка: содержит значение 1 и её порядковый номер - 2
 
и теперь мы можем написать рекурсивный SELECT:

SELECT cte_n.f + cte_n_plus_1.f
FROM my_cte AS cte_n JOIN my_cte AS cte_n_plus_1
ON cte_n.n + 1 = cte_n_plus_1.n # Pair (N)th with (N+1)th to add them
 

Увы, но данный запрос не будет работать, так как my_cte дважды упоминается в части FROM, а это запрещено, потому что нарушает правило: "обрабатывать по одной строке за раз". Следовательно я должен изменить запрос таким образом, чтобы вся информация, необходимая для вычисления нового элемента, содержалась в одной строке и не требовалось использовать 2 строки; для этого я просто буду хранить N-ый и (N+1)-ый элементы в одной строке:


SELECT 1 as f, 1 as next_f
# "f" : число Фибоначи в этой строке,
# "next_f": следующее после "f" число Фибоначи,
# порядковые номера больше не нужны
и использую следующий рекурсивный SELECT:

SELECT next_f, f+next_f FROM my_cte
 

Собираем все вместе и добавляем условие для остановки в районе 500:


WITH RECURSIVE my_cte AS
(
  SELECT 1 as f, 1 as next_f
  UNION ALL
  SELECT next_f, f+next_f FROM my_cte WHERE f < 500
)
SELECT * FROM my_cte;
+------+--------+
| f    | next_f |
+------+--------+
|    1 |      1 |
|    1 |      2 |
|    2 |      3 |
|    3 |      5 |
|    5 |      8 |
|    8 |     13 |
|   13 |     21 |
|   21 |     34 |
|   34 |     55 |
|   55 |     89 |
|   89 |    144 |
|  144 |    233 |
|  233 |    377 |
|  377 |    610 |
|  610 |    987 |
+------+--------+
 

Вот и всё, колонка f содержит последовательность Фибоначи.

Несмотря на то, что рекурсивные ОТВ не могут быть соединены сами с собой, их можно соединять с другими таблицами. Давайте используем это, чтобы сгенерировать все 4-разрядные битовые строки:


WITH RECURSIVE
digits AS
(
  SELECT '0' AS d UNION ALL SELECT '1'
),
strings AS
(
  SELECT '' AS s
  UNION ALL
  SELECT CONCAT(strings.s, digits.d)
  FROM strings, digits
  WHERE LENGTH(strings.s) < 4
)
SELECT s FROM strings WHERE LENGTH(s)=4;
 

Первое нерекурсивное ОТВ digits содержит два строительных блока: 0 и 1. Второе рекурсивное ОТВ strings начинается с пустой строки и новые строки получаются путем слияния с 0 и 1 из digits, таким образом ожидаемый результат: пустая строка, 0, 1, 00, 01, 10, 11, 000, и т.д. до 1111.

Реальным результатом будет ERROR 1406 (22001): Data too long for column ‘s’ at row 2.

Данный момент описан в конце предыдущей статьи (ищите по "все более длинных и длинных"), где упоминается, что тип поля strings.s определяется на основании источника рекурсии, т.е. SELECT ” AS s: а тип данных пустой строки это CHAR(0). Вставка '0' в поле типа CHAR(0) приведет к обрезанию строки, отсюда и ошибка!

Точнее ошибка происходит потому, что я использую strict mode, который включен по умолчанию начиная с MySQL 5.7, и не позволяет проводить обрезание. Раньше strict mode генерировал предупреждение, если обрезание происходило во время работы оператора SELECT, и ошибку при INSERT/UPDATE/DELETE, но мы думаем есть смысл в будущем сделать поведение для SELECT столь же строгим как и для других операторов, поэтому ошибка!

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


WITH RECURSIVE
digits AS
(
  SELECT '0' AS d UNION ALL SELECT '1'
),
strings AS
(
  SELECT CAST('' AS CHAR(4)) AS s
  UNION ALL
  SELECT CONCAT(strings.s, digits.d)
  FROM strings, digits
  WHERE LENGTH(strings.s) < 4
)
SELECT * FROM strings WHERE LENGTH(s)=4;
+------+
| s    |
+------+
| 0000 |
| 1000 |
| 0100 |
| 1100 |
| 0010 |
| 1010 |
| 0110 |
| 1110 |
| 0001 |
| 1001 |
| 0101 |
| 1101 |
| 0011 |
| 1011 |
| 0111 |
| 1111 |
+------+
16 rows in set (0,00 sec)
 

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

И, как всегда:


select from_base64('VGhhbmsgeW91IGZvciB0cnlpbmcgcmVjdXJzaXZlIENURXMh') as final_words;
+--------------------------------------+
| final_words                          |
+--------------------------------------+
| Thank you for trying recursive CTEs! |
+--------------------------------------+
 
Дата публикации: 29.10.2016

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

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