Рекурсивный CTE, выполняющий медленнее, чем жесткое кодирование рекурсивных действий

Question

У меня есть список уведомлений (заметок), которые отправляются пользователям для проверки. Эти заметки могут быть связаны друг с другом родительским / дочерним образом, где одно уведомление является дочерним по отношению к более раннему уведомлению. Не у каждой заметки есть родитель. Всего около 22 000 записей.

Note  Parent Note   
1     NULL   
2     NULL
3     1
4     NULL  
5     NULL
6     3 
7     4

Я хотел бы построить дерево этих уведомлений, проследив до самого начала, чтобы показать, насколько глубоки «дочерние» уведомления и сколько других уведомлений применяются к этому конкретному. Желаемый результат работы приведенной выше таблицы будет выглядеть примерно так:

Note  Parent Note  Level  Full List
1     NULL         1      1
2     NULL         1      2
3     1            2      1/3
4     NULL         1      4
5     NULL         1      5
6     3            3      1/3/6
7     4            2      4/7

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

Я пытался использовать рекурсивный CTE для достижения этой цели. Вот как выглядит запрос.

WITH CTE AS (
SELECT Note,
       Parent_Note,
       1 as Level,
       --Cast as nvarchar to keep data types the same
       CAST(QNote as nvarchar(MAX)) as Full_List
FROM Notifications
WHERE Parent_Note IS NULL
UNION ALL
SELECT Notifications.Note,
       CTE.Note as Parent_Note,
       Level = CTE.Level + 1,
       CAST(Full_List + '/' + Notifications.Note as nvarchar(MAX)) as Full_List
FROM CTE INNER JOIN Notifications ON CTE.Note = Notifications.Parent_Note)

SELECT * FROM CTE

К сожалению, этот запрос занимает около 15 минут, чтобы пройти через 5 записей на втором «уровне» уведомлений.

Однако, если я жестко закодирую каждую рекурсию, я могу получить полный набор данных для загрузки менее чем за 30 секунд.

WITH CTE1 AS (
SELECT Note,
       Parent_Note,
       1 as Level,
       --Cast as nvarchar to keep data types the same
       CAST(QNote as nvarchar(MAX)) as Full_List
FROM Notifications
WHERE Parent_Note IS NULL
),

CTE2 AS (
SELECT Notifications.Note,
       CTE1.Note as Parent_Note,
       Level = CTE1.Level + 1,
       CAST(Full_List + '/' + Notifications.Note as nvarchar(MAX)) as Full_List
FROM CTE1 INNER JOIN Notifications ON CTE1.Note = Notifications.Parent_Note
),

CTE3 AS (
SELECT Notifications.Note,
       CTE2.Note as Parent_Note,
       Level = CTE2.Level + 1,
       CAST(Full_List + '/' + Notifications.Note as nvarchar(MAX)) as Full_List
FROM CTE2 INNER JOIN Notifications ON CTE2.Note = Notifications.Parent_Note
)

SELECT * FROM CTE1 UNION SELECT * FROM CTE2 UNION SELECT * FROM CTE3

Я не совсем понимаю, почему рекурсивный запрос настолько медленный, что не загружается, а жестко запрограммированный запрос загружает данные менее чем за 30 секунд. Я также не хочу использовать жестко запрограммированный запрос, потому что я не уверен, сколько «уровней» в конечном итоге будет существовать, хотя текущий максимум составляет всего шесть.

Буду признателен за любую информацию, которой может поделиться кто-либо, и, хотя я, возможно, не смогу полностью предоставить информацию, чтобы помочь ответить на вопрос (задавая этот вопрос для запросов на работе, поэтому не могу поделиться данными / планами запросов), я буду обязательно предоставлю то, что могу.

Answer 1

Если вы получаете такую ​​производительность только на 22K строках, я бы сказал, что с вашей схемой таблицы что-то не так. Ваш стол случайно не нагроможден?

Вот тестовая установка, которую я выполнил, с 100K строками фиктивных данных:

-- Table with clustered PK and parent-child FK
create table dbo.Notes (
  Id int identity(1,1) primary key,
  ParentId int null references dbo.Notes(Id)
);
go
-- Generate data
insert into dbo.Notes (ParentId)
select top (100000) null
from sys.all_objects a, sys.all_objects b;
go
-- Introduce random parent-child hierarchy between rows
update sq set ParentId = sq.NewParent
from (
  select n.*,
    case when left(cast(newid() as binary(16)), 1) < 0xC0 then 1 else 0 end as [HasParent],
    abs(nullif(checksum(newid()) % (n.Id - 1), 0)) as [NewParent]
  from dbo.Notes n
  where n.Id > 1
    and n.ParentId is null
) sq
where sq.NewParent > 0
  and sq.HasParent = 1;
go
-- Create an index on ParentId
create index IX_Notes_ParentId on dbo.Notes (ParentId);
go

Вот запрос CTE, который я тестировал:

set statistics time on;
go
set statistics io on;
go

with cte as (
  select n.*, cast(n.Id as varchar(max)) as [NotePath]
  from dbo.Notes n where n.ParentId is null
  union all
  select n.*, c.NotePath + '/' + cast(n.Id as varchar(max))
  from dbo.Notes n
    inner join cte c on c.Id = n.ParentId
)
select c.*
from cte c
order by c.Id
option (recompile);
go

set statistics time off;
go
set statistics io off;
go

Здесь время и процессор без индекса в столбце ParentId:

(затронуто 100000 строк)

Таблица «Рабочий стол». Количество сканирований 100002, логическое читает 1295309, физическое чтение 0, чтение с опережением читает 0, логическое чтение lob 0, физическое чтение lob 0, упреждающее чтение lob 0.

Таблица «Примечания». сканирование число 2, логическое чтение 426, физическое чтение 0, чтение с опережением 0, lob логическое чтение 0, физическое чтение - 0, предварительное чтение - 0. - 1017 *

Время выполнения SQL Server: время ЦП = 1032 мс, прошедшее время = 1522 мс.

А вот с индексом:

(затронуто 100000 строк)

Стол «Рабочий стол». Сканирование 2, логическое чтение 736852, физическое чтение 0, чтение с опережением 0, lob логическое чтение 0, lob физическое чтение 0, чтение опережающего чтения 0. 0. 1027 *

Таблица «Примечания». Количество сканирований 100001, логическое чтение 200338, физическое чтение 0, чтение с опережением 0, lob логическое чтение 0, lob физическое чтение 0, lob read-forward читает 0.

Время выполнения SQL Server: время ЦП = 781 мс, прошедшее время = 1313 мс.

Как видите, разница между ними не так уж и значительна, что приводит к выводу, что важен кластерный индекс в столбце Id.

P.S. Я также попробовал индекс (ParentId, Id), предложенный другими, и он не показал какой-либо статистически значимой разницы с индексом, который охватывает только ParentId. Что является ожидаемым поведением, потому что все некластеризованные индексы всегда включают записи из кластерного индекса в качестве ссылок; нет необходимости добавлять столбцы кластерного индекса в них, за исключением некоторых крайних случаев.

Answer 2

Я бы удостоверился, что таблица имеет следующий индекс:

create index ix2 on notifications (parent_note, note);