Оптимизация CTE для возврата потомков на определенном уровне родительско-дочерней иерархии

Question

У меня есть простая временная таблица, определенная в SQL Server 2008 R2, представляющая отношения родитель-потомок. Может быть несколько уровней иерархии (скажем, до 10). Я использую CTE, чтобы найти детей в моей таблице, которые имеют по крайней мере уровень 3 в иерархии происхождения - другими словами, есть по крайней мере родитель И дедушка.

Вот скрипт для демонстрации установки и CTE, который я использую:

set nocount on
create table #linkage(entity_key bigint, parent_key bigint)
--alter table #linkage add foreign key (parent_key) references #linkage(entity_key)

insert into #linkage values(1, 1), (2, 2), (3, 3), (4, 1), (5, 4), (6, 5)
print 'all data:' select * from #linkage

print 'level 3+ descendents:' 
;with r(entity_key, parent_key, level) as
(
    select entity_key, parent_key, 1
        from #linkage
        where entity_key = parent_key
    union all
    select p.entity_key, r.parent_key, r.level + 1
        from #linkage p
        inner join r on p.parent_key = r.entity_key 
        where p.entity_key <> r.entity_key
)
select entity_key, parent_key as ultimate_parent_key
from r
where r.level > 2

Правильно выводит следующее:

all data:
entity_key           parent_key
-------------------- --------------------
1                    1
2                    2
3                    3
4                    1
5                    4
6                    5

level 3+ descendents:
entity_key           ultimate_parent_key  level
-------------------- -------------------- -----------
5                    1                    3
6                    1                    4

Проблема в том, что мне нужно это для работы с большими наборами данных. Когда я запускаю это с 12 миллионами строк, это занимает более 3 минут, что я надеюсь значительно сократить.

Я пытался создать различные комбинации кластеризованных и некластеризованных индексов (entity_key), (entity_key, parent_key) и т. Д., Но ничто не помогает (в действительности, некоторые, кажется, замедляют его).

Вот план выполнения для 12 миллионов строк без индексов:

  |--Filter(WHERE:([Recr1014]>(2)))
       |--Index Spool(WITH STACK)
            |--Concatenation
                 |--Compute Scalar(DEFINE:([Expr1015]=(0)))
                 |    |--Compute Scalar(DEFINE:([Expr1004]=(1)))
                 |         |--Table Scan(OBJECT:([tempdb].[dbo].[#linkage]), WHERE:([tempdb].[dbo].[#linkage].[entity_key]=[tempdb].[dbo].[#linkage].[parent_key]))
                 |--Assert(WHERE:(CASE WHEN [Expr1017]>(100) THEN (0) ELSE NULL END))
                      |--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1017], [Recr1008], [Recr1009], [Recr1010]))
                           |--Compute Scalar(DEFINE:([Expr1017]=[Expr1016]+(1)))
                           |    |--Table Spool(WITH STACK)
                           |--Compute Scalar(DEFINE:([Expr1011]=[Recr1010]+(1)))
                                |--Filter(WHERE:([tempdb].[dbo].[#linkage].[entity_key] as [p].[entity_key]<>[Recr1008]))
                                     |--Index Spool(SEEK:([p].[parent_key]=[Recr1008]))
                                          |--Table Scan(OBJECT:([tempdb].[dbo].[#linkage] AS [p]))

Вот тот же план в формате XML на случай, если вы в такой вещи:

http://pastebin.com/Kx559C10

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

Кто-нибудь может порекомендовать метод, чтобы ускорить это?

Answer 1

Вы пробовали индекс на parent_key и добавление entity_key как включенный столбец?

Маркировка корневых узлов с родителями NULL, а не указание на себя, должна помочь:

declare @linkage table (entity_key bigint, parent_key bigint null) 

insert into @linkage values
  (1, NULL), (2, NULL), (3, NULL), (4, 1), (5, 4), (6, 5), (7, 3), (8, 7), (9, 5) 

;with r(entity_key, immediate_parent, root, level) as 
(
  -- Faster search for NULL to find roots.
  select entity_key, entity_key as immediate_parent, entity_key as root, 1 
    from @linkage 
    where parent_key is NULL
  union all
  -- No WHERE clause needed.
  select p.entity_key, r.entity_key, r.root, r.level + 1 
    from r inner join
      @linkage as p on p.parent_key = r.entity_key  
) 
select *
  from r