sql-server - 用于确定对象层次结构深度的 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

等等

我首先根据 this answer 编写一个查询类似的问题:

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 解决此问题的典型结果，或者是否有一些我忽略的东西可以解释它？也许是索引？ (我现在 table 上没有)

Answer 1

您需要 parent_id 上的索引。 CTE 的递归部分将始终使用嵌套循环连接，并且不受连接提示的影响(结果将添加到 stack spool 中，并且按 LIFO 顺序逐一处理行)

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

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