查询父子 table 的所有祖先的递归 CTE 很慢

Question

我们有一个这样的自引用table

CREATE TABLE Categories(
Id int IDENTITY(1,1) NOT NULL,
Title nvarchar(200) NOT NULL,
ParentId int NULL,
CONSTRAINT PK_Structures PRIMARY KEY CLUSTERED 
(
    Id ASC
)
CREATE NONCLUSTERED INDEX IX_Structures_ParentId ON Categories
(
    ParentId ASC
)

以及获取所有祖先的递归 cte：

Create View Ancestors
as
with A(Id, ParentId) as 
(
    select Id, Id from Categories 
    union all
    select e.Id, p.ParentId from Categories e 
    join A p on e.ParentId = p.Id
)
select * from A

现在我们查询给定类别的所有祖先，例如：

select * from Ancestors where Id = 1234

只包含100000个类别的table需要11秒，执行计划是。查询 returns 5 行给定 Id

我知道我可以通过使用 hierarchyid 大大提高性能，我也知道有时使用 while 可以提高性能，但在像这样的简单情况下，我希望看到更好的表现。另外请注意，我已经在 ParentId

上建立了索引

(图中的tablestructure是问题中提到的Categorytable的真实姓名

是否有调整可以大大提高此性能？

Answer 1

如果将过滤条件放在 CTE 中，执行计划会是什么样子？

with A(Id, ParentId) as 
(
    select Id, Id 
    from Categories 
    WHERE Categories.ID = 1234

    union all

    select e.Id, p.ParentId 
    from Categories e 
    join A p on e.ParentId = p.Id
)
select * 
from A;

Answer 2

嗯。原来是慢的原因，而且修复比预期的更有趣。

Sql 服务器根据查询的定义而不是它们可能具有的语义来优化查询。有问题的视图从所有类别开始，并通过从 CTE 本身及其 children 中查找元素来添加新行。现在查找所有行中某行出现为 child 的方法，您需要计算整个查询，然后将其过滤掉。只有人类 reader 知道查询计算任何类别的所有后代，当然也有任何类别的所有祖先。然后你知道你可以从底部开始递归地找到 parents 。这从查询定义中看不出来，仅从其语义上看。

按如下方式重写视图会使其变快：

Create View Ancestors
as
with A(Id, ParentId) as 
(
    select Id, Id from Categories 
    union all
    select p.Id, e.ParentId from Categories e 
    join A p on e.Id = p.ParentId
)
select * from A

此视图创建的结果与所讨论的视图几乎相同。唯一的区别是它还显示 null 作为所有类别的祖先，这对我们的使用没有影响。

这个视图从下往上构建层次结构，符合我们打算查询的方式

查询父子 table 的所有祖先的递归 CTE 很慢

The Recursive CTE to query all ancestors of a Parent-Child table is slow

sql-server

performance

common-table-expression

hierarchical-data

recursive-cte