[Перевод] Рекурсивные CTE
Одним из наиболее важных применений CTE являются рекурсивные запросы, для которых CTE является фактически единственным средством реализации. Как отмечалось в предыдущей статье, в Books Online есть несколько примеров использования CTE, включая и рекурсивный CTE. Тут мы будем использовать эти примеры из Books Online, используя один из ранних образов базы данных AdventureWorks.
Рекурсивные CTE все сделаны по одному шаблону. Тело CTE представляет собой запрос с UNION ALL, который объединяет один или несколько подзапросов называемых закреплёнными элементами, которые заполняют набор результатов. Кроме закреплённых элементов есть один или несколько рекурсивных подзапросов, называемых рекурсивными элементами, которые возвращают оставшуюся часть результирующего набора. Эти рекурсивные подзапросы ссылаются на сам рекурсивный CTE. Получается, у нас есть один или несколько закреплённых подзапросов и один или несколько рекурсивных подзапросов, объединенных UNION ALL. Аналогично, все планы рекурсивных запросов следуют одному и тому же шаблону, который выглядит следующим образом:
|--Index Spool(WITH STACK)
|--Concatenation
|--Compute Scalar(DEFINE:([Expr10XX]=(0)))
| |-- ... anchor sub-select plan(s) ...
|--Assert(WHERE:(CASE WHEN [Expr10ZZ]>(100) THEN (0) ELSE NULL END))
|--Nested Loops(Inner Join, OUTER REFERENCES:([Expr10YY], [Recr10XX], ...))
|--Compute Scalar(DEFINE:([Expr10ZZ]=[Expr10YY]+(1)))
| |--Table Spool(WITH STACK)
|-- ... recursive sub-select plan(s) ...
Давайте рассмотрим простой пример, который возвращает список сотрудников и их уровень подчинения в организации. Определить уровень подчинения в организации можно с помощью рекурсивного CTE, поскольку для этого потребуется подсчитать количество соединений, необходимых для достижения уровня каждого сотрудника:
WITH DirectReports (ManagerID, EmployeeID, EmployeeLevel) AS
(
SELECT ManagerID, EmployeeID, 0 AS EmployeeLevel
FROM HumanResources.Employee
WHERE ManagerID IS NULL
UNION ALL
SELECT e.ManagerID, e.EmployeeID, EmployeeLevel + 1
FROM HumanResources.Employee e
INNER JOIN DirectReports d
ON e.ManagerID = d.EmployeeID
)
SELECT ManagerID, EmployeeID, EmployeeLevel
FROM DirectReportsВ этом примере есть один закреплённый подзапрос и один рекурсивный подзапрос. Закреплённый подзапрос возвращает список сотрудников верхнего уровня, у которых нет менеджера (в данном случае есть только один такой сотрудник), и присваивает этим сотрудникам уровень 0. Затем рекурсивный подзапрос находит сотрудников, которые подчинены каждому сотруднику самого верхнего уровня и присваивает этим сотрудникам уровень 1. Затем процесс повторяется с рекурсивным подзапросом, который ищет сотрудников ещё ниже по уровню подчинения в организации. Запрос завершается, когда он достигает сотрудников, не являющихся менеджерами никому. На этом этапе рекурсивный подзапрос уже не возвращает ни одного сотрудника.
Теперь давайте посмотрим на план, используемый этим рекурсивным запросом:
|--Index Spool(WITH STACK)
|--Concatenation
|--Compute Scalar(DEFINE:([Expr1013]=(0)))
| |--Compute Scalar(DEFINE:([Expr1003]=(0)))
| |--Index Seek(OBJECT:([HumanResources].[Employee].[IX_Employee_ManagerID]), SEEK:([HumanResources].[Employee].[ManagerID]=NULL) ORDERED FORWARD)
|--Assert(WHERE:(CASE WHEN [Expr1015]>(100) THEN (0) ELSE NULL END))
|--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1015], [Recr1006], [Recr1007], [Recr1008]))
|--Compute Scalar(DEFINE:([Expr1015]=[Expr1014]+(1)))
| |--Table Spool(WITH STACK)
|--Compute Scalar(DEFINE:([Expr1009]=[Recr1008]+(1)))
|--Index Seek(OBJECT:([HumanResources].[Employee].[IX_Employee_ManagerID] AS [e]), SEEK:([e].[ManagerID]=[Recr1007]) ORDERED FORWARD)Как и сам запрос, этот план состоит из двух частей: закреплённой и рекурсивной. Эти части «склеиваются» с помощью оператора конкатенации, реализующего UNION ALL.
Самый интересный оператор в этом плане — это Spool, ещё его называют STACK SPOOL. Этот спул немного похож на обычную очередь с подзапросом и имеет первичный экземпляр, загружающий строки в промежуточную таблицу, и второй, который возвращает строки из промежуточной таблицы. У основного оператора SPOOL есть дочерний элемент, поскольку он загружает строки, а у второго оператора SPOOL нет дочернего элемента, поскольку он просто читает и возвращает строки, загруженные основным оператором SPOOL. (Примеры распространенных случаев такого поведения оператора можно посмотреть в статье Внутренняя оптимизация для индексов в «широком» плане запроса и Агрегат WITH CUB).
В отличие от обычных подвыражений с буферизацией, которые могут быстро загрузить все строки в промежуточную таблицу, а уже потом их возвращают, STACK SPOOL, по сути, является LAZY SPOOL, а это означает, что строки начнут возвращаться сразу. Первый SPOOL (самый верхний оператор в плане), как и типичный LAZY SPOOL, читает строку, вставляет её в очередь и затем возвращает. Второй STACK SPOOL (нижнее соединения вложенных циклов) как раз и делает всё самое интересное. Каждый раз, когда соединение вложенных циклов запрашивает строку у второго STACK SPOOL, будет прочитана его последняя строка, потом она будет возвращена, и затем удалена, чтобы гарантировать невозможность её повторного возврата. Обратите внимание что STACK SPOOL подчиняется правилу «последним пришел — первым вышел». Первый STACK SPOOL помещает строки в стек, а второй STACK SPOOL извлекает строки из стека.
Теперь, когда мы понимаем, как устроен STACK SPOOL, давайте посмотрим на план и разберём как это работает. Процессор запросов начинает выполнение с оператора конкатенации, который является опорной частью плана. В этой части используется поиск по индексу всех сотрудников, у которых нет менеджера. Поиск по индексу возвращает очередную строку, которую основной STACK SPOOL вставляет в промежуточную таблицу:
ManagerID EmployeeID EmployeeLevel
----------- ----------- -------------
NULL 109 0После завершения выполнения опорной части плана процессор запросов продолжает обработку строки оператора конкатенации, который обеспечивает рекурсивность в плане запроса. Эта часть плана включает соединение вложенных циклов со вторым STACK SPOOL, который получает эту строку на входе. Соединение вложенных циклов запрашивает строку из STACK SPOOL, который на данный момент содержит только одну строку для сотрудника 109. STACK SPOOL, после того, как вернёт эту строку, удаляет её из промежуточной таблицы. Затем соединение выполняет поиск по индексу по данным в строке, чтобы найти всех сотрудников, которые работают на сотрудника 109. Этот поиск по индексу возвращает следующие строки, которые основной STACK SPOOL вставляет в промежуточную таблицу:
ManagerID EmployeeID EmployeeLevel
----------- ----------- -------------
109 6 1
109 12 1
109 42 1
109 140 1
109 148 1
109 273 1Затем соединение вложенных циклов запрашивает еще одну строку из второго STACK SPOOL. На этот раз рабочая таблица содержит шесть строк, показанных выше, поэтому STACK SPOOL возвращает (и удаляет) последнюю строку, соответствующую сотруднику 273. Соединение вложенных циклов снова выполняет поиск по индексу и возвращает следующие строки:
ManagerID EmployeeID EmployeeLevel
----------- ----------- -------------
273 268 2
273 284 2
273 288 2Теперь буферная таблица содержит следующие строки:
ManagerID EmployeeID EmployeeLevel
----------- ----------- -------------
109 6 1
109 12 1
109 42 1
109 140 1
109 148 1
273 268 2
273 284 2
273 288 2Этот процесс повторяется и продолжается с сотрудником 288. В конце концов буфер возвращает строку, соответствующую сотруднику, который не является менеджером. Этот происходит, когда поиск по индексу не возвращает ни одной строки. После того как соединение получит последнюю строку из STACK SPOOL, запрос завершается.
В этом плане есть ещё интересные моменты, на которые стоит обратить внимание. Во-первых, план включает два набора скалярных вычислений для определения уровня рекурсии. Один набор ([Expr1003] и [Expr1009]) используется для вычисления уровня сотрудника. Другой набор ([Expr1013] и [Expr1015]) генерируется внутри и используется оператором Assert, для гарантии того, что запрос завершится и не попадет в бесконечный цикл. Если выполнить этот запрос без параметра «EmployeeLevel», вы увидите, что один набор скалярных вычислений из плана исчезнет.
Мы можем контролировать максимальный уровень рекурсии. Например, если выполнить запрос с хинтом OPTION (MAXRECURSION 2), можно увидеть, что константа в операторе Assert изменится со 100 (значение по умолчанию) на 2. Поскольку для этого запроса требуется больше двух уровней рекурсии, то попытка выполнения с этим хинтом приведёт к ошибке:
Msg 530, Level 16, State 1, Line 1
The statement terminated. The maximum recursion 2 has been exhausted before statement completion.
Из-за этого способа формирования плана запроса, который будем называть базовой формой, SQL Server не может использовать для рекурсивных запросов план с параллелизмом. Тут есть две основные проблемы. Во-первых, очередь стека не поддерживает параллельное выполнение. Во-вторых, соединение вложенных циклов не поддерживает параллельное выполнение на внутренней стороне (входе).
Давайте теперь продемонстрируем, что размещение предложения WHERE может оказать сильное влияние на производительность рекурсивного запроса. Предположим, мы хотим выполнить запрос в начале статьи, но ограничить результаты сотрудниками первых двух уровней. Мы могли бы добавить в этот запрос из Books Online дополнительное предложение WHERE, чтобы ограничить выводимый результаты:
WITH DirectReports(ManagerID, EmployeeID, EmployeeLevel) AS
(
SELECT ManagerID, EmployeeID, 0 AS EmployeeLevel
FROM HumanResources.Employee
WHERE ManagerID IS NULL
UNION ALL
SELECT e.ManagerID, e.EmployeeID, EmployeeLevel + 1
FROM HumanResources.Employee e
INNER JOIN DirectReports d
ON e.ManagerID = d.EmployeeID
)
SELECT ManagerID, EmployeeID, EmployeeLevel
FROM DirectReports
WHERE EmployeeLevel <= 2Этот запрос по существу пользуется тем же планом, что и запрос без дополнительного предложения WHERE. Предложение WHERE просто добавляет оператор фильтра в корне плана:
Rows Executes
34 1 |--Filter(WHERE:([Recr1012]<=(2)))
290 1 |--Index Spool(WITH STACK)
290 1 |--Concatenation
0 0 |--Compute Scalar(DEFINE:([Expr1013]=(0)))
0 0 | |--Compute Scalar(DEFINE:([Expr1003]=(0)))
1 1 | |--Index Seek(OBJECT:([Employee].[IX_Employee_ManagerID]), SEEK:([ManagerID]=NULL) ...)
289 1 |--Assert(WHERE:(CASE WHEN [Expr1015]>(100) THEN (0) ELSE NULL END))
289 1 |--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1015], [Recr1006], [Recr1007], [Recr1008]))
0 0 |--Compute Scalar(DEFINE:([Expr1015]=[Expr1014]+(1)))
290 1 | |--Table Spool(WITH STACK)
0 0 |--Compute Scalar(DEFINE:([Expr1009]=[Recr1008]+(1)))
289 290 |--Index Seek(OBJECT:([Employee].[IX_Employee_ManagerID]), SEEK:([ManagerID]=[Recr1007]) ...)Как видно по количеству строк, этот запрос определяет уровень для каждого сотрудника организации, и только после этого отфильтровывает ненужные результаты. Теперь предположим, что вместо этого мы переместили предложение WHERE в рекурсивный подзапрос:
WITH DirectReports(ManagerID, EmployeeID, EmployeeLevel) AS
(
SELECT ManagerID, EmployeeID, 0 AS EmployeeLevel
FROM HumanResources.Employee
WHERE ManagerID IS NULL
UNION ALL
SELECT e.ManagerID, e.EmployeeID, EmployeeLevel + 1
FROM HumanResources.Employee e
INNER JOIN DirectReports d
ON e.ManagerID = d.EmployeeID
WHERE EmployeeLevel < 2
)
SELECT ManagerID, EmployeeID, EmployeeLevel
FROM DirectReportsЭтот запрос семантически идентичен предыдущему запросу, но если мы посмотрим на план, то увидим, что фильтр переходит в рекурсивную часть плана:
Rows Executes
34 1 |--Index Spool(WITH STACK)
34 1 |--Concatenation
0 0 |--Compute Scalar(DEFINE:([Expr1013]=(0)))
0 0 | |--Compute Scalar(DEFINE:([Expr1003]=(0)))
1 1 | |--Index Seek(OBJECT:([Employee].[IX_Employee_ManagerID]), SEEK:([ManagerID]=NULL) ...)
33 1 |--Assert(WHERE:(CASE WHEN [Expr1015]>(100) THEN (0) ELSE NULL END))
33 1 |--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1015], [Recr1006], [Recr1007], [Recr1008]))
0 0 |--Compute Scalar(DEFINE:([Expr1015]=[Expr1014]+(1)))
34 1 | |--Table Spool(WITH STACK)
0 0 |--Compute Scalar(DEFINE:([Expr1009]=[Recr1008]+(1)))
33 34 |--Nested Loops(Inner Join)
7 34 |--Filter(WHERE:(STARTUP EXPR([Recr1008]<(2))))
7 7 | |--Constant Scan
33 7 |--Index Seek(OBJECT:([Employee].[IX_Employee_ManagerID]), SEEK:([ManagerID]=[Recr1007]) ...)Обратите внимание на количество строк, новый план оперирует только той частью результирующего набора, которая нас действительно интересует, а затем завершает рекурсию.
Также можно заметить, что план теперь использует так называемый STARTUP FILTER. Обычный фильтр считывает строки из дерева на входе, а затем оценивает логическое выражение для каждой получаемой строки, чтобы определить, нужно ли её возвращать дальше. STARTUP FILTER оценивает собственное выражение только один раз за всё исполнение. Выражение не зависит от строк на входе. Если выражение оценивается, как true, STARTUP FILTER возвращает все строки на входе. Если выражение имеет значение false, STARTUP FILTER не будет возвращать ничего.
В последнем примере, если выражение STARTUP FILTER имеет значение true, оператор Constant Scan вернёт одну строку в соединение вложенных циклов, которое непосредственно над фильтром, и это соединение затем выполняет поиск по индексу на своем внутреннем входе. Однако если выражение STARTUP FILTER будет оценено как ложь, фильтр, а затем соединение вложенных циклов не вернут ни одной строки.
Хотя существует множество сценариев, в которых STARTUP FILTER действительно полезен, этот план получается чересчур запутанным. В плане можно было бы использовать и обычный фильтр:
|--Index Spool(WITH STACK)
|--Concatenation
|--Compute Scalar(DEFINE:([Expr1013]=(0)))
| |--Compute Scalar(DEFINE:([Expr1003]=(0)))
| |--Index Seek(OBJECT:([HumanResources].[Employee].[IX_Employee_ManagerID]), SEEK:([HumanResources].[Employee].[ManagerID]=NULL) ORDERED FORWARD)
|--Assert(WHERE:(CASE WHEN [Expr1015]>(100) THEN (0) ELSE NULL END))
|--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1015], [Recr1006], [Recr1007], [Recr1008]))
|--Filter(WHERE:([Recr1008]<(2)))
| |--Compute Scalar(DEFINE:([Expr1015]=[Expr1014]+(1)))
| |--Table Spool(WITH STACK)
|--Compute Scalar(DEFINE:([Expr1009]=[Recr1008]+(1)))
|--Index Seek(OBJECT:([HumanResources].[Employee].[IX_Employee_ManagerID] AS [e]), SEEK:([e].[ManagerID]=[Recr1007]) ORDERED FORWARD)
Обратите внимание, что этот план является выдуманным и пока мы не придумали способ заставить SQL Server использовать его, а не тот, что имеем в действительности.
