CTE与T-SQL循环,用于确定对象层次结构的深度

Question

我有一个包含大约70,000行和两列(两者VARCHAR(16))的表:id和parent_id.

我想填充一个"深度"列,显示特定记录距离"根"节点的距离.

例如

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来解决这个问题,或者是否有一些我忽略的东西可以解释它？索引,也许？(我现在没有在桌子上)

Answer 1

你需要一个索引parent_id.CTE的递归部分将始终使用嵌套循环连接,并且不受连接提示的影响(结果被添加到堆栈假脱机并且行以LIFO顺序逐个处理)

如果没有索引,parent_id则需要在嵌套循环的内侧多次扫描表.性能将随着行数呈指数级下降.

没有递归的查询将能够使用不同的连接类型(散列或合并),只对每个递归级别扫描表两次.在这种情况下,很可能是散列连接,因为您没有可避免排序的有用索引.