Рекурсия в MS SQL
Иногда, в хранимой процедуре или функции требуется использовать результаты выборки несколько раз. В таких случаях мы часто используем временные таблицы. Однако, стоит учитывать некоторые преимущества и недостатки временных таблиц. Преимущества:
- Временные таблицы являются полноценными таблицами. Поэтому для них можно создавать индексы и статистику. Это может существенно ускорить работу с ними.
- Заполнение временной таблицы связано с перемещением данных. Хоть это и простая операция Insert, все же при больших объемах данных есть нагрузка на диски;
- Существует риск увеличения времени выполнения запросов. Временные таблицы создаются в базе tempdb. А нагрузка на эту базу существенная.
Учитывая риски использования временных таблиц, гораздо привлекательнее выглядит применение обобщенного табличного выражения.
Обобщённое табличное выражение
Common Table Expression (CTE) выражение с общей таблицей, которую можно использовать множество раз в запросе. CTE не сохраняет данные, а создает нечто вроде временного представления. Кто-то может сказать, что CTE – это подзапрос, который предшествует основному запросу. Но это не совсем так, ведь подзапрос нельзя использовать несколько раз, а CTE можно.
Когда же стоит использовать обобщенное табличное выражение?
- Для создания рекурсивных запросов, с помощью которых можно получить данные в иерархическом виде;
- При многократных ссылках на набор данных в пределах одного запроса;
- С целью заменить представления, временные таблицы, табличные переменные.
К преимуществам CTE можно отнести: рекурсию, высокую скорость работы запроса, лаконичность запроса.
А к недостаткам отнесем ограниченность использования. CTE может использоваться только для запроса, к которому он принадлежит. Невозможно использовать его в других запросах. В этом случае придется использовать временные таблицы или табличные переменные.
Обобщенные табличные выражения бывают простые и рекурсивные.
Простые не включают ссылки на самого себя, а рекурсивные соответственно включают.
Рекурсивные CTE используются для возвращения иерархических данных
Рассмотрим пример простого CTE предложения:
WITH CTEQuery (Field1, Field2) AS ( SELECT (Field1, Field2) FROM TABLE ) SELECT * FROM CTEQuery
Field1, Field2 – имена полей запроса;
Table – некая таблица, из которой выбираются данные для использования в основном запросе.
В это примере можно и не указывать явно поля выборки, так как мы выбираем все поля из таблицы TestTable:
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:
WITH RecursiveQuery AS ( Anchor> UNION ALL Joined TO RecursiveQuery> ) SELECT * FROM RecursiveQuery
– якорь, запрос, который определяет начальный элемент дерева (иерархического списка). Обычно в якоре есть условие WHERE определяющее конкретные строки таблицы.
После UNION ALL следует запрос к целевой таблице с JOIN к CTE выражению.
— 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')
Уже сейчас понятно, что структура подразделений в организации иерархическая. Наша задача получить список подразделений, подчиненных помощнику финансового директора. Если рассуждать в контексте иерархического дерева, то мы должны найти ветвь и ее листья.
Но сначала давайте посмотрим весь список подразделений:
Источник
Отображение древовидных структур на T-SQL
Тема рекурсии достаточно хорошо освещена в литературе, но, тем не менее, задача вывода «дерева» не средствами клиента, а SQL Server многих ставит в тупик. Для себя я использую подобный запрос для вывода дерева блокировок (динамическое представление — sys.processes). Возможны и другие применения, надеюсь читатель статьи сам для себя определится для чего нужен и полезен этот запрос.
Итак, ставим задачу:
Есть таблица с именем, идентификатором записи и полем указывающим на идентификатор предка. Сразу заполним эту таблицу, какими-то тестовыми значениями.
declare @tree table ( id int primary key, parent int, title varchar(100) ); insert @tree values (1,null,'Генеральный директор'), (2,1,'Финансовый директор'), (3,1,'Директор ИТ'), (4,2,'Главный бухгалтер'), (5,2,'Главный экономист'), (6,4,'Бухгалтер по ОС'), (7,4,'Бухгалтер по ЗП'), (8,7,'Кассир'), (9,3,'Ведущий программист'), (10,9,'Программист 1'), (11,9,'Программист 2'), (12,9,'Программист 3'), (13,3,'Ведущий сетевой администратор'), (14,13,'сисадмин 1'), (15,13,'сисадмин 2'), (16,13,'сисадмин 3'), (17,13,'сисадмин 4');
Необходимо вывести имена в древовидной структуре запросом на T-SQL: Генеральный директор
Директор ИТ
Ведущий программист
Программист 1
Программист 2
Программист 3
Ведущий сетевой администратор
сисадмин 1
сисадмин 2
сисадмин 3
сисадмин 4
Финансовый директор
Главный бухгалтер
Бухгалтер по ЗП
Кассир
Бухгалтер по ОС
Главный экономист
C MS-SQL 2005 появилась конструкция на T-SQL с названием «обобщенные табличные выражения (common table expression — CTE)», которая позволяет реализовывать линейную рекурсию (жаль конечно что нет каскадной рекурсии, но имея возможность линейной рекурсии мы уже можем со многими задачами справляться).
В общем, рекурсивный синтаксис CTE в том, что мы должны объявить «якорь» точку с которой старт рекурсии будет, и с помощью конструкции объединения «UNION ALL» добавить запрос который использует имя нашей CTE — запрос ссылается сам на себя, конечно не забываем второй запрос ограничивать условием выхода из рекурсии.
Пример генерации последовательности целых чисел рекурсивно выглядит примерно так:
with numbers (i) as ( select 1 union all select i+1 from numbers where i) select * from numbers
Где select 1 не что иное как «якорь», select i+1 from numbers — это рекурсивный запрос, и where i
Для решения нашей задачи, нам потребуется «глубина вложения — уровень (lev)», для того что бы понять на сколько делать отступ каждой строки (отступ будем делать с помощью функций или SPACE или REPLICATE — кому что больше нравится). И так же нам необходимо вычислить поле, по которому будем делать сортировку при выводе результата, что бы не получилось так что программист подчиняется главному бухгалтеру. Самое простое, что приходит «на ум» —это формировать текущую должность и весь список руководителей:
Генеральный директор
Генеральный директор ;Директор ИТ
Генеральный директор ;Директор ИТ ;Ведущий программист
Генеральный директор ;Директор ИТ ;Ведущий программист ;Программист 1
Генеральный директор ;Директор ИТ ;Ведущий программист ;Программист 2
Генеральный директор ;Директор ИТ ;Ведущий программист ;Программист 3
Генеральный директор ;Директор ИТ ;Ведущий сетевой администратор
Генеральный директор ;Директор ИТ ;Ведущий сетевой администратор ;сисадмин 1
Генеральный директор ;Директор ИТ ;Ведущий сетевой администратор ;сисадмин 2
Генеральный директор ;Директор ИТ ;Ведущий сетевой администратор ;сисадмин 3
Генеральный директор ;Директор ИТ ;Ведущий сетевой администратор ;сисадмин 4
Генеральный директор ;Финансовый директор
Генеральный директор ;Финансовый директор ;Главный бухгалтер
Генеральный директор ;Финансовый директор ;Главный бухгалтер ;Бухгалтер по ЗП
Генеральный директор ;Финансовый директор ;Главный бухгалтер ;Бухгалтер по ЗП ;Кассир
Генеральный директор ;Финансовый директор ;Главный бухгалтер ;Бухгалтер по ОС
Генеральный директор ;Финансовый директор ;Главный экономист
И уже сортировать по этому полю (поле назовем – «list»).
Теперь, когда мы понимаем, суть алгоритма, я представлю запрос который у меня получился:
declare @tree table ( id int primary key, parent int, title varchar(100) ); insert @tree values (1,null,'Генеральный директор'), (2,1,'Финансовый директор'), (3,1,'Директор ИТ'), (4,2,'Главный бухгалтер'), (5,2,'Главный экономист'), (6,4,'Бухгалтер по ОС'), (7,4,'Бухгалтер по ЗП'), (8,7,'Кассир'), (9,3,'Ведущий программист'), (10,9,'Программист 1'), (11,9,'Программист 2'), (12,9,'Программист 3'), (13,3,'Ведущий сетевой администратор'), (14,13,'сисадмин 1'), (15,13,'сисадмин 2'), (16,13,'сисадмин 3'), (17,13,'сисадмин 4'); with recurs as ( select *, 0 as lev, cast(title as varchar(max)) as list from @tree where parent is null union all select t.*, lev+1, c.list+' ;'+t.title from @tree t join recurs c on c.id = t.parent ) select id, parent, space(lev*10)+title as title, lev, list from recurs order by list
Источник
Рекурсивные SQL запросы
Рекурсивны SQL запросы являются одним из способов решения проблемы дерева и других проблем, требующих рекурсивную обработку. Они были добавлены в стандарт SQL 99. До этого они уже существовали в Oracle. Несмотря на то, что стандарт вышел так давно, реализации запоздали. Например, в MS SQL они появились только в 2005-ом сервере.
Рекурсивные запросы используют довольно редко, прежде всего, из-за их сложного и непонятного синтаксиса:
В 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.
Источник