Запрос рекурсивный sql: Рекурсивные SQL запросы / Хабр

Рекурсивные SQL запросы / Хабр

Anthony

17 июн 2008 в 00:33

Время на прочтение
2 мин

Количество просмотров

138K

Рекурсивны SQL запросы являются одним из способов решения проблемы дерева и других проблем, требующих рекурсивную обработку. Они были добавлены в стандарт SQL 99. До этого они уже существовали в Oracle. Несмотря на то, что стандарт вышел так давно, реализации запоздали. Например, в MS SQL они появились только в 2005-ом сервере.

Рекурсивные запросы используют довольно редко, прежде всего, из-за их сложного и непонятного синтаксиса:

with [recursive] <имя_алиаса_запроса> [ (<список столбцов>) ]
as (<запрос>)

<основной запрос>

В MS SQL нет ключевого слова recursive, а в остальном все тоже самое. Такой синтаксис поддерживается в DB2, Sybase iAnywhere, MS SQL и во всех базах данных, которые поддерживают стандарт SQL 99.

Проще разобрать на примере. Предположим, есть таблица:

create table tree_sample (

  id integer not null primary key,

  id_parent integer foreign key references tree_sample (id),

  nm varchar(31) )

id – идентификатор

id_parent – ссылка на родитель

nm – название.

Для вывода дерева:

with recursive tree (nm, id, level, pathstr)
as (select nm, id, 0, cast(» as text)

   from tree_sample

   where id_parent is null
union all

   select tree_sample.nm, tree_sample.id, t.level + 1, tree.pathstr + tree_sample.nm

   from tree_sample

     inner join tree on tree.id = tree_sample.id_parent)
select id, space( level ) + nm as nm
from tree
order by pathstr

Этот пример выведет дерево по таблице с отступами. Первый запрос из tree_sample этот запрос выдаст все корни дерева. Второй запрос соединяет между собой таблицу tree_sample и tree, которая определяется этим же запросом. Этот запрос дополняет таблицу узлами дерева.

Сначала выполняется первый запрос. Потом к его результатам добавляются результаты второго запроса, где данные таблица tree – это результат первого запроса. Затем снова выполняется второй запрос, но данные таблицы tree – это уже результат предыдущего выполнения второго запроса. И так далее. На самом деле база данных работает не совсем так, но результат будет таким же, как результат работы описанного алгоритма.

После этого данные этой таблицы можно использовать в основном запросе как обычно.

Хочу заметить, что я не говорю о применимости конкретно этого примера, а лишь пишу его для демонстрации возможностей рекурсивных запросов. Этот запрос реально будет работать достаточно медленно из-за order by.

Теги:

• SQL
• рекурсия

Хабы:

• SQL

Всего голосов 37: ↑35 и ↓2 +33

Комментарии
51

Антон Жердев
@Anthony

Пользователь

Рекурсия в MS SQL — Быстрые отчеты

10 января 2019 г.

Иногда, в хранимой процедуре или функции требуется использовать результаты выборки несколько раз. В таких случаях мы часто используем временные таблицы. Однако, стоит учитывать некоторые преимущества и недостатки временных таблиц. Преимущества:

• Временные таблицы являются полноценными таблицами. Поэтому для них можно создавать индексы и статистику. Это может существенно ускорить работу с ними.

Недостатки:

• Заполнение временной таблицы связано с перемещением данных. Хоть это и простая операция Insert, все же при больших объемах данных есть нагрузка на диски;
• Существует риск увеличения времени выполнения запросов. Временные таблицы создаются в базе tempdb. А нагрузка на эту базу существенная.

Учитывая риски использования временных таблиц, гораздо привлекательнее выглядит применение обобщенного табличного выражения.

Обобщённое табличное выражение

Common Table Expression (CTE) выражение с общей таблицей, которую можно использовать множество раз в запросе. CTE не сохраняет данные, а создает нечто вроде временного представления.  Кто-то может сказать, что CTE – это подзапрос, который предшествует основному запросу. Но это не совсем так, ведь подзапрос нельзя использовать несколько раз, а CTE можно.

Когда же стоит использовать обобщенное табличное выражение?

1. Для создания рекурсивных запросов, с помощью которых можно получить данные в иерархическом виде;
2. При многократных ссылках на набор данных в пределах одного запроса;
3. С целью заменить представления, временные таблицы, табличные переменные.

К преимуществам CTE можно отнести: рекурсию, высокую скорость работы запроса, лаконичность запроса.

А к недостаткам отнесем ограниченность использования. CTE может использоваться только для запроса, к которому он принадлежит. Невозможно использовать его в других запросах. В этом случае придется использовать временные таблицы или табличные переменные.

Обобщенные табличные выражения бывают простые и рекурсивные.

Простые не включают ссылки на самого себя, а рекурсивные соответственно включают.

Рекурсивные CTE используются для возвращения иерархических данных

Рассмотрим пример простого CTE предложения:

1
2
3
4
5
6

 WITH CTEQuery (Field1, Field2)
 AS
 (
 SELECT (Field1, Field2) FROM TABLE
 )
 SELECT * FROM CTEQuery

 Здесь CTEQuery — имя CTE;

                Field1, Field2 – имена полей запроса;

                Table – некая таблица, из которой выбираются данные для использования в основном запросе.

В это примере можно и не указывать явно поля выборки, так как мы выбираем все поля из таблицы TestTable:

1
2
3
4
5
6

WITH CTEQuery
 AS
 (
 SELECT * FROM Table
 )
SELECT * FROM CTEQuery

С помощью CTE можно оптимизировать основной запрос если вынести часть логики в CTE. Дело в том, что CTE позволяет создавать сразу несколько выражений (запросов). Таким образом вы можете разбить сложный запрос на несколько предварительных «представлений» с помощью CTE, а затем связать их в общем запросе:

1
2
3
4
5
6
7
8
9
10
11
12

WITH CTEQuery1 (Field1, Field2) AS
(
 SELECT Field1 AS ID, Field2 FROM Table1
 WHERE Field2 >= 1000
),
CTEQuery2 (Field3, Field4) AS
(
 SELECT Field3 AS ID, Field4 FROM Table2
 WHERE Field4 = 'Москва'
)
 
SELECT * FROM CTEQuery1 INNER JOIN CTEQuery2 ON CTEQuery2.ID = CTEQuery1.ID

Как было сказано выше, основное назначение CTE – рекурсия. Типовая задача для рекурсии – обход дерева. Так что мы можем строить дерево с помощью with. Структура рекурсивного запроса впервые появилась в SQL Server 2005.

Взгляните на инструкцию WITH:

1
2
3
4
5
6
7

WITH RecursiveQuery AS
(
 {Anchor}
 UNION ALL
 {Joined TO RecursiveQuery}
)
SELECT * FROM RecursiveQuery

{Anchor} – якорь, запрос, который определяет начальный элемент дерева (иерархического списка). Обычно в якоре есть условие WHERE определяющее конкретные строки таблицы.

После UNION ALL следует запрос к целевой таблице с JOIN к CTE выражению.

{Joined to RecursiveQuery}- SELECT из целевой таблицы. Обычно это та же таблица, которая используется в якоре. Но в этом запросе она соединяется с CTE выражением, образуя рекурсию.  Условие этого соединения определяет отношение родитель – ребенок. От этого зависит переходите ли вы на верхние уровни дерева или на нижние.

Давайте посмотрим на рекурсивный запрос, который возвращает список подразделений организации. Подготовим данные для этого запроса:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

CREATE TABLE Department
(
ID INT,
ParentID INT,
Name VARCHAR(50)
)
 
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (1, 0, 'Finance Director')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (2, 1, 'Deputy Finance Director')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (3, 1, 'Assistance Finance Director')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (4, 3, 'Executive Bodget Office')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (5, 3, 'Comptroller')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (6, 3, 'Purchasing')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (7, 3, 'Debt Management')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (8, 3, 'Risk Management')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (9, 2, 'Public Relations')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (10, 2, 'Finance Personnel')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (11, 2, 'Finance Accounting')
INSERT INTO Department ( ID, ParentID, Name ) 
VALUES (12, 2, 'Liasion to Boards and Commissions')

Уже сейчас понятно, что структура подразделений в организации иерархическая. Наша задача получить список подразделений, подчиненных помощнику финансового директора. Если рассуждать в контексте иерархического дерева, то мы должны найти ветвь и ее листья.

Но сначала давайте посмотрим весь список подразделений:

Во главе стоит финансовый директор, ему подчиняются заместитель и помощник. Каждый из них имеет в своем ведении группу подразделений. Поле ParentID указывает на идентификатор «хозяина». Таким образом мы имеем уже готовую связь master-slave.

Давайте напишем рекурсивный запрос с помощью WITH.

1
2
3
4
5
6
7
8
9
10
11
12
13

WITH RecursiveQuery (ID, ParentID, Name)
AS
(
 SELECT ID, ParentID, Name
 FROM Department dep
 WHERE dep.ID = 3
 UNION ALL
 SELECT dep.ID, dep.ParentID, dep.Name
 FROM Department dep
 JOIN RecursiveQuery rec ON dep.ParentID = rec.ID
)
SELECT ID, ParentID, Name
FROM RecursiveQuery

В этом примере явно указаны названия полей, которые нужно выбрать в CTE. Однако, внутренние запросы имеют такие же поля. Так что можно просто убрать это перечисление вместе со скобками.

Внутри CTE мы имеем два похожих запроса. Первый выбирает корневой элемент дерева, которое мы строим. Второй – все последующие подчиненные элементы, благодаря связи с самим CTE. «Рекурсия» в SQL на самом деле не рекурсия, а итерация. Нужно представить запрос с JOIN как цикл, и тогда сразу все станет понятно. В каждой итерации мы знаем значение предыдущей выборки и получаем подчиненные элементы. На следующем шаге мы получим подчиненные элементы для предыдущей выборки. То есть каждая итерация – переход по дереву вниз, или вверх, в зависимости от условия связи.

Результат выполнения приведенного запроса такой:

А вот как бы выглядел этот запрос без использования CTE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

DECLARE @Department TABLE (ID INT, ParentID INT, Name VARCHAR(50), Status INT DEFAULT 0)
-- Сначала мы выбираем в табличную переменную якорь – начальный элемент от которого строим дерево. 
INSERT @Department
SELECT ID, ParentID, Name, 0
 FROM Department dep
 WHERE dep.ID = 3
 
DECLARE @rowsAdded INT = @@ROWCOUNT
-- Проходим цикл пока новые отделы добавляются в предыдущем шаге
WHILE @rowsAdded > 0 
BEGIN
-- Помечаем записи в табличной переменной, как готовые к обработке
UPDATE @Department SET Status = 1 WHERE Status = 0
-- Выбираем дочерние записи для предыдущей записи
INSERT @Department 
SELECT dep.ID, dep.ParentID, dep.Name, 0
 FROM Department dep
 JOIN @Department rec ON dep.ParentID = rec.ID
AND rec. Status = 1
SET @rowsAdded = @@ROWCOUNT 
 
 --Помечаем записи, найденные на текущем шаге как обработанные 
 UPDATE @Department SET Status = 2 WHERE Status = 1 
END
SELECT * FROM @Department

 Такой цикл работает заметно медленнее CTE выражения. Да и к тому же требует создания табличной переменной. И количество кода увеличилось в два раза. Таким образом, CTE выражения являются лучшим решением для организации рекурсивного обхода дерева в MS SQL.

Dmitriy Fedyashov

Технический писатель

Fast Reports Team: Dmitriy Fedyashov — Technical Writer at Fast Reports

SQL

Добавить комментарий

Рекурсивное выражение SQL с визуальным объяснением

Рекурсия в SQL? Но почему? О, этому есть много применений. В SQL принято хранить иерархические данные, а рекурсивные запросы — удобный способ извлечения информации из таких графов. Некоторые распространенные примеры иерархических данных, с которыми вы можете столкнуться, включают организационную структуру, структуру меню приложения, набор задач с подзадачами в проекте, ссылки между веб-страницами и разбивку модуля оборудования на части и подчасти.

Что такое рекурсивное выражение общей таблицы SQL (CTE)?

Рекурсивное выражение общей таблицы SQL (CTE) — это запрос, который постоянно ссылается на предыдущий результат, пока не вернет пустой результат. Его лучше всего использовать как удобный способ извлечения информации из иерархических данных. Это достигается с помощью CTE, который в SQL известен как оператор with. Это позволяет вам назвать результат и позже ссылаться на него в других запросах.

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

Рекурсивный SQL: что это значит и как это работает?

Давайте подумаем о запросах как о функции в том смысле, что функция принимает входные данные и производит выходные данные. Запросы оперируют отношениями или, можно сказать, таблицами. Мы будем обозначать их как Rn . Запрос принимает три отношения — R1 , R2 и R3 — и выдает результат R . Достаточно просто.

Визуальное представление того, как рекурсивный запрос работает в SQL. | Изображение: Денис Лукичев

Пример SQL: ВЫБЕРИТЕ ИЗ R1, R2, R3, ГДЕ .

Запрос может принимать что-то и ничего не производить:

Визуальное представление запроса, который принимает что-то и ничего не производит. | Изображение: Денис Лукичев

Пример SQL: SELECT FROM R1 WHERE 1 = 2

Он может ничего не брать и что-то производить:

Визуальное представление запроса, который ничего не берет и что-то производит. | Изображение: Денис Лукичев

Пример SQL: SELECT 1 .

Или он ничего не может взять и ничего не произвести.

Визуальное представление запроса, ничего не принимающего и ничего не производящего. | Изображение: Денис Лукичев

SELECT 1 WHERE 1 = 2

Подробнее о блок-диаграммах DataUnderstanding

На жаргоне SQL это называется общим табличным выражением (CTE).

Это позволяет вам назвать результат и позже ссылаться на него в других запросах.

Именование результата и ссылка на него в других запросах

Вот пример.

 С R AS (ВЫБРАТЬ 1 КАК n)
ВЫБЕРИТЕ n + 1 ИЗ R
 

Запрос (ВЫБРАТЬ 1 КАК n) теперь имеет имя R . Мы ссылаемся на это имя в SELECT n + 1 FROM R . R — это таблица с одной строкой и одним столбцом, содержащая номер один. Результатом всего выражения является число два.

Рекурсивная версия инструкции WITH ссылается на себя при вычислении выходных данных.

Использование рекурсивного общего табличного выражения. | Скриншот: Денис Лукичев

Чтобы рекурсия работала, нам нужно с чего-то начать и решить, когда рекурсия должна остановиться. Для этого рекурсивный оператор with обычно имеет следующую форму:

Рекурсивный оператор with в SQL. | Изображение: Денис Лукичев

Важно отметить, что базовый запрос не включает R , однако рекурсивный запрос ссылается на R . На первый взгляд кажется, что это бесконечный цикл. Чтобы вычислить R , нам нужно вычислить R . Но есть одна загвоздка. R не ссылается на себя, а просто ссылается на предыдущий результат. И когда предыдущий результат — пустая таблица, рекурсия останавливается. Это может помочь думать об этом как об итерации, а не о рекурсии.

Вот что происходит. Базовый запрос выполняется первым, принимая все необходимое для вычисления результата R0. Второй рекурсивный запрос выполняется, принимая на вход R0 — это R ссылается на R0 в рекурсивном запросе при первом выполнении. Рекурсивный запрос выдает результат R1 , и это то, на что R будет ссылаться при следующем вызове, и так далее, пока рекурсивный запрос не вернет пустой результат. В этот момент все промежуточные результаты объединяются.

Блок-схема алгоритма выполнения рекурсивного запроса. | Изображение: Денис ЛукичевПоследовательность выполнения рекурсивного запроса. | Изображение: Денис Лукичев

Примеры рекурсивного SQL

Если это слишком абстрактно, давайте рассмотрим пару конкретных примеров.

Пример 1. Считаем до трех

Первый пример, который мы рассмотрим, — это счет до трех.

Запуск рекурсивного оператора с оператором для выполнения подсчета до трех команд. | Скриншот: Денис Лукичев

Базовый запрос возвращает число 1 , рекурсивный запрос берет его под именем countUp и выдает число 2 , которое является входом для следующего рекурсивного вызова. Когда рекурсивный запрос возвращает пустую таблицу n >= 3 , результаты вызовов складываются вместе.

Иллюстрация результатов вызова, сложенных вместе. | Изображение: Денис Лукичев

Однако на таких подсчетах далеко не уедешь. Есть предел рекурсии. По умолчанию он равен 100, но его можно расширить с помощью параметра MAXRECURSION (зависит от сервера Microsoft SQL). На практике, однако, было бы плохой идеей увеличить предел рекурсии. Графики могут иметь циклы, а ограниченная глубина рекурсии может быть хорошим защитным механизмом для предотвращения плохого поведения запроса:  ОПЦИЯ (MAXRECURSION 200) .

Подробнее о руководстве SQLA по разрешению расхождений данных в SQL

Пример 2. Поиск предков

Давайте рассмотрим другой пример, поиск предков человека.

Использование рекурсии для поиска предков человека. | Изображение: Денис Лукичев Рекурсивная общая таблица для поиска предков человека. | Скриншот: Денис Лукичев

Базовый запрос находит родителя Фрэнка, Мэри, а затем рекурсивный запрос берет этот результат под Имя предка и находит родителей Мэри, которых зовут Дейв и Ева. Этот процесс продолжается до тех пор, пока мы не сможем найти больше родителей.

Иллюстрация результатов рекурсии по поиску предков человека. | Изображение: Денис Лукичев Таблица данных, которая включает год рождения, чтобы найти родителей человека. | Изображение: Денис Лукичев

Этот запрос обхода дерева может быть основой, на основе которой вы дополняете запрос некоторой другой интересующей вас информацией. Например, имея в таблице год рождения, мы можем вычислить, сколько лет было родителю, когда родился ребенок. Наш следующий запрос может сделать именно это, наряду с отображением родословных. Для этого он обходит дерево сверху вниз. parentAge равно нулю в первой строке, потому что по имеющимся у нас данным мы не знаем, когда родилась Алиса.

Запуск рекурсии для нахождения года рождения человека и его предков. | Скриншот: Денис Лукичев. Таблица, представляющая результаты рекурсии для нахождения года рождения и предков человека. | Изображение: Денис Лукичев

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

Понимание рекурсивного CTE SQL Server на практических примерах

Резюме : в этом руководстве вы узнаете, как использовать рекурсивное CTE SQL Server для запроса иерархических данных.

Введение в рекурсивное CTE SQL Server

Рекурсивное общее табличное выражение (CTE) — это CTE, которое ссылается на себя. Таким образом, CTE многократно выполняется, возвращает подмножества данных, пока не вернет полный набор результатов.

Рекурсивный CTE полезен при запросе иерархических данных, таких как организационные диаграммы, где один сотрудник отчитывается перед менеджером, или многоуровневая спецификация, когда продукт состоит из многих компонентов, и каждый компонент сам также состоит из многих других компонентов.

Ниже показан синтаксис рекурсивного CTE:

 WITH имя_выражения (список_столбцов)
КАК
(
    -- Якорный член
    начальный_запрос
    СОЮЗ ВСЕХ
    -- Рекурсивный элемент, который ссылается на имя_выражения.
    рекурсивный_запрос
)
-- ссылается на имя выражения
ВЫБИРАТЬ *
ОТ имя_выражения
  Язык кода: SQL (язык структурированных запросов) (sql)  

В общем, рекурсивный CTE состоит из трех частей:

1. Исходный запрос, который возвращает базовый набор результатов CTE. Первоначальный запрос называется элементом привязки.
2. Рекурсивный запрос, ссылающийся на общее табличное выражение, поэтому он называется рекурсивным членом. Рекурсивный элемент объединяется с элементом привязки с помощью оператора UNION ALL .
3. Условие завершения, указанное в рекурсивном члене, которое завершает выполнение рекурсивного члена.

Порядок выполнения рекурсивного CTE следующий:

• Сначала выполните элемент привязки для формирования базового набора результатов (R0), используйте этот результат для следующей итерации.
• Во-вторых, выполнить рекурсивный элемент с входным набором результатов из предыдущей итерации (Ri-1) и вернуть набор подрезультатов (Ri), пока не будет выполнено условие завершения.
• В-третьих, объедините все наборы результатов R0, R1, … Rn, используя оператор UNION ALL , чтобы получить окончательный набор результатов.

Следующая блок-схема иллюстрирует выполнение рекурсивного CTE:

Примеры рекурсивного CTE для SQL Server

Рассмотрим несколько примеров использования рекурсивного CTE

A) Пример простого рекурсивного CTE SQL Server

В этом примере используется рекурсивное CTE для возврата дней недели с понедельник по суббота :

 WITH cte_numbers(n, день недели)
КАК (
    ВЫБИРАТЬ
        0,
        ДАТАИМЯ(DW, 0)
    СОЮЗ ВСЕХ
    ВЫБИРАТЬ
        п + 1,
        ДАТАИМЯ(DW, n + 1)
    ОТ
        cte_numbers
    ГДЕ n < 6
)
ВЫБИРАТЬ
    будний день
ОТ
    cte_numbers;
  Язык кода: SQL (язык структурированных запросов) (sql)  

Вот набор результатов:

В этом примере:

Функция DATENAME() возвращает название дня недели на основе номера дня недели.

Элемент привязки возвращает Понедельник

 SELECT
    0,
    ДАТАИМЯ(DW, 0)
  Язык кода: SQL (язык структурированных запросов) (sql)  

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

 ВЫБОР
        п + 1,
        ДАТАИМЯ(DW, n + 1)
    ОТ
        cte_numbers
    ГДЕ n < 6
  Язык кода: SQL (язык структурированных запросов) (sql)  

Условие в предложении WHERE является условием завершения, которое останавливает выполнение рекурсивного члена, когда n равно 6

 n < 6
  Язык кода: SQL (язык структурированных запросов) (sql)  

B) Использование рекурсивного CTE SQL Server для запроса иерархических данных

См. следующую таблицу sales.staffs из примера базы данных: персонал подчиняется нулю или одному менеджеру. У менеджера может быть ноль или более сотрудников. У топ-менеджера нет менеджера.