通过物化路径查询SQL中的邻接列表

Question

我在Microsoft SQL Server(2019(中使用邻接列表模型(例如Id、ParentId(存储了一个大型层次结构(2500多条记录(。我正在寻找一种有效的方法来根据层次结构中的特定路径查找记录。换句话说，给定路径(例如/Root/FolderA/SubfolderA(，我想检索与最终节点相关联的Id(在这种情况下为SubfolderA(。

注意：节点名称不是全局唯一的。也就是说，我们不能只查找SubfolderA并假设它映射到/Root/FolderA/SubfolderA。在该层次结构中可能存在多个名为SubfolderA的节点。

设置

层次结构

/Root
/FolderA
/SubfolderA
/SubfolderB
/FolderB
/SubfolderA
/SubfolderB

结构

CREATE 
TABLE   [dbo].[Tree] (
[Id]            INT             NOT NULL PRIMARY KEY, 
[ParentId]      INT             NULL, 
[Name]          VARCHAR(255)    NOT NULL, 
CONSTRAINT      [FK_Hierarchy]  
FOREIGN KEY     (ParentId) 
REFERENCES      [Tree]([Id])
)

数据

INSERT INTO Tree VALUES (1,    NULL, 'Root');
INSERT INTO Tree VALUES (2,    1,    'FolderA');
INSERT INTO Tree VALUES (3,    2,    'SubfolderA');
INSERT INTO Tree VALUES (4,    2,    'SubfolderB');
INSERT INTO Tree VALUES (5,    1,    'FolderB');
INSERT INTO Tree VALUES (6,    5,    'SubfolderA');
INSERT INTO Tree VALUES (7,    5,    'SubfolderB');

天真的方法

关于如何将邻接列表转换为物化路径，有很多线程，包括：

• SQL-将非空邻接列表转换为路径
• 从SQL中的相邻列表生成枚举路径
• 将相邻列表层次展平为所有路径的列表
• 使用递归公用表表达式从MSSQL加载分层数据

视图

我们可以使用其中一种方法，使用rCTE:将整个邻接列表转换为物化路径

CREATE 
VIEW            [dbo].[MaterializedPaths]
WITH            SCHEMABINDING
AS 
WITH RCTE AS (
SELECT        Id,
ParentId,
CAST('/' + Name AS VARCHAR(255)) AS Path
FROM          [dbo].[Tree] root
WHERE         root.Id = 1
UNION ALL
SELECT        this.Id,
this.ParentId,
CAST(parent.Path + '/' + this.Name AS VARCHAR(255)) AS Path
FROM          [dbo].[Tree] AS this
INNER JOIN    RCTE parent
ON          this.ParentId = parent.Id
)
SELECT          Id,
Path
FROM            RCTE as hierarchy

输出

这会产生以下输出：

Id    Path
1     /Root
2     /Root/FolderA
3     /Root/FolderA/SubfolderA
4     /Root/FolderA/SubfolderB
5     /Root/FolderB
6     /Root/FolderB/SubfolderA
7     /Root/FolderB/SubfolderB

查询

我们可以使用一个简单的WHERE子句来过滤输出：

SELECT          Id
FROM            MaterializedPaths
WHERE           Path = '/Root/FolderA/SubfolderA'

问题

这种天真的方法效果很好。问题是，对于查询大型层次结构，效率极低，因此速度较慢，因为每次调用都需要动态重建整个物化路径集。就我而言，这需要8-9秒。显然，我可以将这些数据存储在一个表中，并在数据发生变化时通过触发器重新生成。但我宁愿找到一个更高效的查询，避免额外的复杂性。

问题

构造此查询的有效方法是什么？或者，冒着将其变成XY问题的风险，有没有一种方法可以限制rCTE，使其只需要评估层次结构中的节点，而不是每次重建整个层次结构？

Answer 1

有没有办法限制rCTE，使其只需要评估层次结构中的节点，而不是每次都重构整个层次结构？

限制rCTE

有几种方法可以限制每个递归查询的范围，使其只评估层次结构中的相关节点。一种相当有效的方法是简单地将rCTE限制为源路径(让我们称之为@Path(开始的记录：

INNER JOIN  RCTE recursive
ON        this.ParentId = recursive.Id
AND       @Path LIKE CAST(recursive.Path + '/' + this.Name AS VARCHAR(MAX)) + '%'

这将限制查询到您路径中的每个记录：

Id    Path
1     /Root
2     /Root/FolderA
3     /Root/FolderA/SubfolderA

然后可以根据一个简单的WHERE子句很容易地过滤到最终记录：

WHERE Path = @Path

将其包装为功能

我们可以将其与原始rCTE组合成一个函数。综合起来，它可能看起来像：

CREATE
FUNCTION        [dbo].[GetIdFromPath]
(
@Path       VARCHAR(MAX)
)
RETURNS         INT
AS
BEGIN
DECLARE       @Id         INT = -1

;WITH RCTE AS (
SELECT      Id,
ParentId,
CAST('/' + Name AS VARCHAR(MAX)) AS Path
FROM        [dbo].[Tree] root
WHERE       root.Id = 1
UNION ALL
SELECT      this.Id,
this.ParentId,
CAST(parent.Path + '/' + this.Name AS VARCHAR(MAX)) AS Path
FROM        [dbo].[Tree] AS this
INNER JOIN  RCTE parent
ON        Tree.ParentId = parent.Id
AND       @Path LIKE CAST(parent.Path + '/' + this.Name AS VARCHAR(MAX)) + '%'
)
SELECT        @Id = Id
FROM          RCTE as hierarchy
WHERE         Path = @Path
RETURN        @Id
END

按路径查询

给定上面的函数，您现在可以通过简单地将完整路径传递给GetIdFromPath()函数来查询邻接列表：

SELECT          dbo.GetIdFromPath('/Root/FolderA/SubfolderA') AS Id

给定原始帖子的样本数据，它将返回3。

性能

我已经在一个具有2500个样本记录的类似大小的表中测试了这种方法，它在一秒钟内始终执行良好，这比天真的方法有了显著的改进。显然，您需要根据自己的数据库和性能要求对此进行评估，以确定其效率是否足够。