Рекурсия в MS SQL

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

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

Недостатки:

• Заполнение временной таблицы связано с перемещением данных. Хоть это и простая операция 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.