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

Question

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

Note: Node names are not globally unique. I.e., we can't just look for SubfolderA and assume it maps to /Root/FolderA/SubfolderA. There may be multiple nodes named SubfolderA within the hierarchy.

设置

层次结构

/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');

天真的方法

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

Build Enumeration Path from Adjacency List in SQL
Flatten Adjacency List Hierarchy To A List Of All Paths
Load hierarchical data from MSSQL with recursive common table expressions

查看

我们可以使用这些方法之一将整个邻接列表转换为使用 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 秒。显然，我可以将这些数据存储在 table 中，并在数据发生变化时通过触发器重新生成它。但我宁愿找到更有效的查询并避免额外的复杂性。

问题

构建此查询的有效方法是什么？或者，冒着使这成为 XY 问题的风险，有没有办法限制 rCTE，以便它只需要评估层次结构中的节点，而不是每个重建 entire 层次结构时间？

Answer 1

Is there a way to limit the rCTE so that it only needs to evaluate the nodes in the hierarchy, instead of reconstructing the entire hierarchy each time?

限制 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

根据原始 post 的样本数据，return 3。

性能

我已经针对具有 2,500 个样本记录的可比较大小的 table 测试了这种方法，并且它在一秒钟内始终如一地执行良好，这是对天真的方法的显着改进。显然，您需要根据自己的数据库和性能要求对其进行评估，以确定其效率是否足够.

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

Query an adjacency list in SQL via a materialized path

sql

sql-server

recursive-query

adjacency-list

materialized-path-pattern

设置

层次结构

结构

数据

天真的方法

查看

输出

查询

问题

问题

限制 rCTE

将其打包为函数

按路径查询

性能