如何使用这种模式有效地遍历图形数据？

Question

我有一些体现有向无环图的关系，其中包括类似于以下内容的模式：

我正在寻找一种有效的方法来遍历此图形数据。下面是计算节点 0 的后代的看似简单任务的示例：

数据库<>小提琴

DROP TABLE IF EXISTS #edges;
CREATE TABLE #edges(tail int, head int);
INSERT INTO #edges(tail,head) VALUES
    (0,1), (5, 6),  (10,11), (15,16),
    (0,2), (5, 7),  (10,12), (15,17),
    (1,2), (6, 7),  (11,12), (16,17),
    (1,3), (7, 8),  (11,13), (17,18),
    (2,3), (7, 9),  (12,13), (17,19),
    (2,4), (8, 9),  (12,14), (18,19),
    (3,4), (8,10),  (13,14),
    (3,5), (9,10),  (13,15),
    (4,5), (9,11),  (14,15),
    (4,6),          (14,16);
WITH descendents(node)
AS(
    SELECT 0 as node
    UNION ALL
    SELECT head as node FROM descendents as prior
    JOIN #edges ON prior.node = tail
)
SELECT
    (SELECT COUNT(node) FROM descendents)             as total_nodes,
    (SELECT COUNT(node) FROM
        (SELECT DISTINCT node FROM descendents) as d) as distinct_nodes

结果如下：

total_nodes | distinct_nodes
      10512 |             20

每条路径都被访问一次，而不是每个节点一次

total_nodes似乎以大约 2^n 的速度增长，其中 n 是示例中的节点数。这是因为每个可能的路径都会被遍历而不是每个节点都被遍历一次。 此 n=29 示例的结果为 1,305,729 total_nodes，在我的 SQL Server Express 本地实例上花了 75 秒才能完成。

显而易见的策略是在每次迭代中仅访问以前未访问过的节点。

WHERE...NOT IN似乎不支持使用排除冗余添加

防止访问先前访问过的节点的最直接方法似乎是在 CTE 的递归成员中进行右侧过滤，如下所示：

SELECT head as node FROM descendents as prior
JOIN #edges ON prior.node = tail
WHERE head NOT IN (SELECT node from descendents)

这会产生错误“公用表表达式‘后代’的递归成员具有多个递归引用。” 我怀疑这是文档 中此限制的一个示例：

递归成员的 FROM 子句必须仅引用 CTE expression_name 一次。

未能成功避免 CTE 递归成员中先前访问过的节点

我尝试了几种不同的技术来避免在 CTE 中进行递归时访问先前访问过的节点。然而，我还没有找到适用于这种图形模式的技术。该限制似乎可以归结为文档中的以下声明：

...CTE 递归部分中的聚合函数应用于当前递归级别的集合，而不是 CTE 的集合。ROW_NUMBER 等函数仅对当前递归级别传递给它们的数据子集进行操作，而不是对传递给 CTE 递归部分的整个数据集进行操作。

先前访问过的节点出现在不同的递归级别。上述限制似乎排除了使该查询高效所需的跨递归级别的重复数据删除。

查询分析

以下是在我的 SQL Server Express 本地实例上调用的42 个节点上运行的查询。（请注意，一半的节点在 fiddle 中被注释掉，因为运行所有 42 个节点会导致 fiddle 超时。）

查询运行如下：

set statistics xml on;
SET STATISTICS IO ON;
SET STATISTICS TIME ON;
WITH descendents(node)
AS(
    SELECT 0 as node
    UNION ALL
    SELECT head as node FROM descendents as prior
    JOIN #edges ON prior.node = tail
)
SELECT DISTINCT
    node
FROM descendents
SET STATISTICS TIME OFF;
SET STATISTICS IO OFF;
set statistics xml off;

这导致了以下消息：

开始在第 1 行执行查询（受影响的 76 行）

SQL Server 解析和编译时间：CPU 时间 = 0 毫秒，运行时间 = 14 毫秒。（受影响的 42 行）

表“工作台”。扫描计数 2、逻辑读取 943777243、物理读取 0、预读读取 12117、lob 逻辑读取 0、lob 物理读取 0、lob 预读读取 0。

表“#edges______________________________________________________________________________________________________________000000002516”。扫描计数 1、逻辑读取 157296207、物理读取 0、预读读取 0、lob 逻辑读取 0、lob 物理读取 0、lob 预读读取 0。

（1 行受影响）

SQL Server 执行时间：CPU 时间 = 2972​​344 毫秒，运行时间 = 3319271 毫秒。总执行时间：00:55:19.424

这是执行计划：

这些是似乎最耗时的步骤的工具提示屏幕截图：

可能的替代方案

我可以想到一些无需依赖 CTE 递归即可实现节点遍历的编程方法。鉴于有大量建议尽可能选择集合逻辑，我不愿意过早放弃 CTE。我希望有一些内置的 SQL Server 功能可以支持一些改进的方法。我考虑过的其他方法如下：

• 以编程方式实现递归的存储过程
• 层次结构ID
• SQL图

我对这些方法的经验有限或没有经验，因此对上述示例中这些方法的权衡建议很感兴趣。

问题

1. 是否有更有效的方法使用递归 CTE 来遍历上面示例中的图？
2. 在上述替代方案中，有哪些权衡？
3. 我还应该考虑其他选择吗？

Answer 1

问题确实是，您的图形图像与示例数据并不完全一一对应#edges。在您的图形图像中，node 2是独一无二的。在#edges表中，存在两次，因为它是和node 2的子项。所以这实际上隐式地最终将你的图分解成一棵树，并且是重复的。node 0node 1node 2

1. 是否有更有效的方法使用递归 CTE 来遍历上面示例中的图？

目前的实施效率是否低得令人无法接受？仅仅因为它遍历重复的节点并不一定意味着到达那里的过程效率低下。执行计划显示幕后发生了什么？关于运行时计算，TIME和IO STATISTICS表示什么？我通常发现递归 CTE 的性能相当好，即使在迭代大小合适的数据集合时也是如此。

对于循环图，如果您只想访问每个节点一次，那么您可以通过在递归的每次迭代中跟踪已访问过的节点来解决冗余问题。一种方法是使用分隔符构建一串已访问过的节点，并执行通配符包含搜索，如下所示：

WITH descendents(node)
AS(
    SELECT 0 as node, CONVERT(VARCHAR(MAX), '0') AS NodesVisited
    UNION ALL
    SELECT head as node, CONCAT(prior.NodesVisited, '|', head) AS NodesVisited
    FROM descendents as prior
    JOIN #edges ON prior.node = tail
    WHERE prior.NodesVisited NOT LIKE CONCAT('%|', #edges.head, '|%')
)
...

但这种方法本身效率较低，因为在每次迭代的子句中进行通配符包含搜索会产生开销WHERE。这与NOT LIKE子句相结合还使得谓词不可控制，这实际上意味着它不能使用索引来有效地服务于该谓词。根据#edges数据的大小，这也可能会对性能产生负面影响。

一个稍微替代的选项（假设您使用的是 SQL Server 2016 或更高版本）是构建已访问节点的字符串，然后CROSS APPLY与内置函数一起STRING_SPLIT()使用以将已访问节点的集合作为数据集加入，而不是使用通配符包含搜索。不过，这也可能是资源密集型的（来自对函数的重复调用STRING_SPLIT()）。

不幸的是，这些解决方案都不适用于您的非循环图问题，因为您的问题不是循环后代链，而是具有重复子项的兄弟姐妹（如评论中所述）。

在一天结束时，您将需要查看执行计划和运行时统计信息（如前所述），以确定每个实现的性能如何，并对它们进行比较。

• 以编程方式实现递归的存储过程
• 层次结构ID
• SQL图

2. 在上述替代方案中，有哪些权衡？

存储过程路由的效率可能低于递归 CTE 实现。它更像是一种过程代码方法，而不是关系代码方法。通过将递归存储过程实现为递归 CTE，我将需要 1 个小时以上的计算时间的递归存储过程转换为不到 1 秒。

我对这种hierarchyid数据类型没有经验，但我猜您仍然需要实现基于递归的解决方案才能获得您想要的最终结果，无论哪种方式。我认为这种数据类型并不常用。

使用 SQL Graph 功能会很有趣。我也只有很少的使用经验。但同样，我认为这是 SQL Server 中很少使用的一个功能，因此关于如何正确有效地使用它的信息可能较少。

3. 我还应该考虑其他选择吗？

目前我想不到。一般来说，最常见的解决方案是递归 CTE。