如何在SQL Server中高效合并两个层级结构？

Question

我有两个带有hierarchyid字段的表，其中一个是暂存表，包含需要合并到另一个表中的新数据（即一组需要添加到主树中的节点，其中某些节点可能已经存在）。

除了定义树结构（父/子关系）的hierarchyid列外，每个表都有一个单独的列，其中包含唯一标识每个节点的节点标识符。也就是说，判断暂存表中的节点是否已经存在于主表中的方法是通过节点ID而不是通过hierarchyid列。

实现上，需要执行以下处理：

For each row, RS, in the staging table:
    If there is not already a row with the same Id as RS in the main table:
         Find the parent, PS, of the staging row
         Find the row, PM, in the main table that has the same node ID as PS
         Create a new child, RM of row PM
         Set PM's ID equal to the ID of RS

重要的是，这种方法只有在分期表中的树以广度优先顺序排序/遍历时才能起作用-这样当遇到RS时，可以保证其父级PS已经在主表中具有相应的行。

到目前为止，我唯一看到的在SQL Server中实现这一点的方法是使用游标遍历分期表（已经排序），并为每一行调用一个存储过程，该存储过程基本上完全执行上述操作，包括使用SELECT MAX()查找已存在于PM下的最高层次结构ID，以便可以唯一地添加子项。

虽然这是一种效率极低的方法，但对于我的目的来说太慢了。有更好的方法吗？

背景是，这是我正在进行的可行性检查。我需要弄清楚是否可以在SQL Server内快速执行此操作。如果结果发现我不能这样做，我将不得不以其他方式在数据库外执行它。合并树是问题领域固有的（实际上，在某种意义上，它就是问题领域），因此不可能采用不同的数据结构或采用更广泛的视角，尝试以某种方式完全避免执行此操作。

更新

如请求所示，这里有一个具体的例子。

"分期"和"主"表都有相同的两列：

   hierarchy_id of type hierarchyid
   node_id of type bigint

初始内容

主函数：

 hierarchy_id    node_id
 /1/             1
 /1/1/           2
 /1/2/           3
 /1/3/           4

预发布环境：

 hierarchy_id    node_id
 /1/             1
 /1/1/           3
 /1/2/           5
 /1/1/1/         6

期望的内容

主要内容：

 hierarchy_id    node_id
 /1/             1
 /1/1/           2
 /1/2/           3
 /1/3/           4
 /1/4/           5
 /1/2/1/         6

请注意，暂存表中层次ID为/1/1/的节点对应于目标表中层次ID为/1/2/的节点（这就是为什么节点ID很重要——不能仅复制层次ID值）。此外，请注意新的节点ID 6 被添加为正确父节点（节点ID为3），这也是为什么层次ID很重要的原因——它定义了任何新节点的树形结构（父子关系）。任何解决方案都需要考虑这两个方面。

- Tom

---

顺便提一下，我也接受不使用hierarchyid的解决方案。然而，我的理解是在没有它们的情况下处理任意深度的树需要使用公共表达式，这些表达式在语法上看起来很丑陋，而且我阅读的资料表明它们比hierarchyid慢。 - Tom

@Aaronought - 我已经添加了一个示例。也许可以使用简单的MERGE语句来完成它（我不是SQL专家）。但是，我不能简单地合并hierarchyid列。将hierarchyid值复制到目标表中是无效的，因为暂存表中的值仅定义了暂存表内的树形结构。对于已经存在的节点，不需要进行任何操作。任何不存在的分支都需要保持其层次结构完整，并与目标中匹配的节点拼接。希望这样更清楚一些-描述起来很棘手。 - Tom

@Mikael Eriksson，暂存表中仅包含已存在于目标表中的新分支和节点。此外，暂存表中不会有没有父节点的节点。暂存表中的每个节点都将具有完整的节点路径，一直到根节点。 - Tom

嗯，好的，我会再试着问一遍，因为我还不确定。在暂存表中是否可能存在一个节点，而该节点已经存在于目标表中，但是该节点的父节点在暂存和目标中是不同的？这意味着应该使用新的父节点更新目标中的现有节点？ - Mikael Eriksson

啊，抱歉 - 误解了你的问题。不，那是不可能的。 - Tom

Answer 1

用这种方式建立您的层次结构会导致问题。hierarchy_id列违反了第一范式，如果您不对访问进行串行化/瓶颈处理，则合并过程容易出现更新异常。

您应该考虑一个只有node_id和parent_id的表，看看它如何使您的合并问题变得简单。

node_id   parent_id
1         NULL
2         1
3         2
4         3

node_id   parent_id
1         NULL
3         1
5         2
6         1

您可以使用递归查询来实现这一点，您可能会惊讶于执行计划的效率。如果您必须要有扁平化层次结构列，则可以使用递归查询创建一个索引视图。

- gordy

---

有趣的想法。我的合并是串行的，所以我对此并不太担心，但这看起来确实会使合并变得更容易。我猜这是以使查询变得更棘手和更慢的代价为代价的。我会尝试一下，谢谢！ - Tom

这肯定快多了，但对于我的使用情况来说还不够快。至少用这种方法我认为我没有人为地限制SQL服务器。如果像这样直接合并速度太慢，我怀疑我必须寻找其他方法。 - Tom

Answer 2

我们一直在研究一个需要类似解决方案的产品。经过对这种和其他方法的大量研究，我们得出结论，层次结构ID方法不适合我们。

因此，作为对你问题的直接回答：没有更好的方法来使用这种方法进行操作。

看一下嵌套集模型和相邻列表模型。

这两种方法都比这个特定的设计挑战的解决方案更加优雅和高效。 编辑： 作为事后思考，如果你不想使用SQL，那么这个问题可以通过使用非关系数据库得到更好的解决。 我们不能走这条路，因为没有人有足够的专业知识来设计非关系数据库，但是如果SQL是可选的，那么你可以在MongoDB等数据库中以更好、更有效的方式使用你当前的方法。

- vvohra87

---

谢谢 - 我倾向于这个方向。我有一个使用非关系数据库（基于HDF5）的原型，但由于它是保守的企业环境，我想确保我已经公平地测试了更传统/支持的技术。 - Tom

顺便提一下，谢谢你提供的链接。对我来说，嵌套集模型看起来有些问题，因为每次合并新节点集时，都需要重新编号目标树。如果想让邻接列表模型允许任意深层次的分层结构（我需要这个功能），我认为我需要使用公共表达式（Common Table Expressions），但它们看起来很丑陋。我看到的关于层次 ID 的文档声称它们比公共表达式更快。 - Tom

嘿，我听到你的话了。保守的客户浪费我的时间。为什么在合并时重新编号会有问题？此外，请参见Joe关于邻接列表的链接。模式的创建者写了一本书，其中摘录了您可以应用于简单邻接模式以使其更加耐用的修复方法。此外，我在这里看不到使用CTE的必要性，我错过了什么吗？ - vvohra87

@Tom：如果你必须坚持这个，我有一个可行的解决方案，但我并不为此感到自豪。我只保留了一张表，没有自动增量主键，也没有父ID和子ID。它很简单。我将节点ID存储为来自常规有序列表的字符串。所以我有nodeID = 1，nodeID = 1.1，nodeID = 1.1.1，nodeID = 1.1.2等。当时我使用了我发现令人昏昏欲睡的查询来完成这个过程。也许你可以试试 :) - vvohra87

Answer 3

这里有一个解决方案，可以逐级将源@S中的行移动到目标@T。为了简化一些操作，我添加了一个根节点，以便始终存在一个父节点，用于创建新的HierarchyID。

我从未使用过HierarchyID，因此可能有更有效的方法来完成此操作，但至少比逐行处理要更高效。

-- Target table
declare @T table 
(
  hierarchy_id hierarchyid primary key,
  node_id bigint
)

insert into @T values
('/',             0), -- Needed for simplicity
('/1/',           1),
('/1/1/',         2),
('/1/2/',         3),
('/1/3/',         4)

-- Source table
declare @S table 
(
  hierarchy_id hierarchyid primary key,
  node_id bigint
)

insert into @S values
('/',               0),
('/1/',             1),
('/1/1/',           3),
('/1/2/',           5),
('/1/1/1/',         6)

declare @lvl int = 1

-- Move rows from @S to @T for each level
while exists(select *
             from @S
             where hierarchy_id.GetLevel() = @lvl)
begin

  insert into @T
  select T.hierarchy_id.GetDescendant(C.MaxID, null),
         S.node_id
  from (select S1.node_id, S2.node_id as ParentID
        from @S as S1
          inner join @S as S2
            on S1.hierarchy_id.GetAncestor(1) = S2.hierarchy_id
        where S1.hierarchy_id.GetLevel() = @lvl and
              S1.node_id not in (select node_id
                                 from @T)
       ) as S
    inner join @T as T
      on S.ParentID = T.node_id
    outer apply (select max(hierarchy_id) as MaxID
                 from @T as T2
                 where T.hierarchy_id = T2.hierarchy_id.GetAncestor(1)) as C       

    set @lvl = @lvl + 1
end

select *, hierarchy_id.ToString()
from @T
where hierarchy_id <> hierarchyid::GetRoot()  

结果：

hierarchy_id  node_id  (No column name)
------------  -------  ----------------
0x58          1        /1/
0x5AC0        2        /1/1/
0x5B40        3        /1/2/
0x5B56        6        /1/2/1/
0x5BC0        4        /1/3/
0x5C20        5        /1/4/

- Mikael Eriksson