CTE与T-SQL循环：确定对象层次结构深度的比较

Question

我有一个表格，包含大约70,000行和两列（都是VARCHAR(16)类型）：id和parent_id。

我想要填充一个“depth”列，显示特定记录距离“根”节点的距离。

例如：

id,parent_id,depth
A,NULL,0
B,A,1
C,A,1
D,B,2
E,D,3

我开始根据这个回答中类似问题的写法编写查询语句：

WITH myCTE(id, depth) AS
(
    SELECT id, 0 FROM objects where id = 'A'
    UNION ALL
    SELECT objects.id, depth + 1 FROM myCTE JOIN objects ON objects.parent_id = myCTE.id
)
SELECT id, depth FROM myCTE

使用我的数据集（约80,000行），上述操作需要近两个小时才能执行完毕！

我随后将查询作为一个循环编写，并获得了更好的性能：

ALTER TABLE objects ADD depth INT NULL
DECLARE @counter int
DECLARE @total int
SET @counter = 0
UPDATE objects SET depth = 0 WHERE id = 'A'

SELECT @total = COUNT(*) FROM objects WHERE depth IS NULL

WHILE (@total > 0)
BEGIN
    UPDATE objects SET depth = @counter + 1 WHERE parent_id IN (
        SELECT id FROM objects WHERE depth = @counter
    )
    SELECT @total = COUNT(*) FROM objects WHERE depth IS NULL
    SET @counter = @counter + 1
END

以上代码只需要几分钟就可以完成（它还有一个好处，即将结果添加到现有表格中）。

我的问题是，使用CTE解决此问题是否会产生与我相似的结果，或者是否有一些我忽略的东西可能会解释这个问题？也许是索引吗？（目前我没有在表格上创建任何索引）

- Catchwa

---

哇，根据我的经验，这听起来相当不典型。你是否打开了执行计划以比较这两个？ - Matt

@Matt - 即使是中等大小的表，CTE 的递归部分能够通过索引查找来满足非常关键，否则性能可能会严重下降。 - Martin Smith

Answer 1

您需要在parent_id上创建索引。CTE的递归部分将始终使用嵌套循环连接，并且不受连接提示的影响（结果添加到堆栈溢出中，行按LIFO顺序逐个处理）。

如果没有在parent_id上创建索引，则需要在嵌套循环的内部多次扫描表格。随着行数的增加，性能会呈指数级下降。

您的非递归查询将能够使用不同的连接类型（哈希或合并），每个递归级别仅扫描两次表格。在这种情况下，最可能使用哈希连接，因为您没有有用的索引可以避免排序。

- Martin Smith

Answer 2

你考虑过使用HierarchyID数据类型吗？这会让你的生活变得轻松很多。

CREATE TABLE Groups.tblHierarchyNode
(
        NodeID              Int IDENTITY (0,1),
        NodeHID             HierarchyID NOT NULL,   -- DB Hierarchy ID of where I am in a tree
        HierarchyLevel      AS NodeHID.GetLevel(),  -- Numerical level of where I am in tree
)

我现在在很多分层表格中都使用这个。你需要在填充表格时更加聪明，但是生成报告非常容易，上下移动层次结构、获取祖先、后代等操作也很简单。

- Janine Rawnsley