Релиз 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. Перепечатка в интернет-изданиях разрешается только с указанием автора и прямой ссылки на оригинальную статью. Перепечатка в бумажных изданиях допускается только с разрешения редакции.
|
