我有一个可以使用以下代码创建和填充的表:
CREATE TABLE dbo.Example(GroupKey int NOT NULL, RecordKey varchar(12) NOT NULL);
ALTER TABLE dbo.Example
ADD CONSTRAINT iExample PRIMARY KEY CLUSTERED(GroupKey ASC, RecordKey ASC);
INSERT INTO dbo.Example(GroupKey, RecordKey)
VALUES (1, 'Archimedes'), (1, 'Newton'), (1, 'Euler'), (2, 'Euler'), (2, 'Gauss'),
(3, 'Gauss'), (3, 'Poincaré'), (4, 'Ramanujan'), (5, 'Neumann'),
(5, 'Grothendieck'), (6, 'Grothendieck'), (6, 'Tao');
对于基于另一行具有有限协作距离RecordKey
的所有行,我想分配一个唯一值——我不关心唯一值是什么数据类型或数据类型。
可以使用以下查询生成符合我要求的正确结果集:
SELECT 1 AS SupergroupKey, GroupKey, RecordKey
FROM dbo.Example
WHERE GroupKey IN(1, 2, 3)
UNION ALL
SELECT 2 AS SupergroupKey, GroupKey, RecordKey
FROM dbo.Example
WHERE GroupKey = 4
UNION ALL
SELECT 3 AS SupergroupKey, GroupKey, RecordKey
FROM dbo.Example
WHERE GroupKey IN(5, 6)
ORDER BY SupergroupKey ASC, GroupKey ASC, RecordKey ASC;
为了更好地帮助我解决问题,我将解释为什么GroupKey
s 1–3 具有相同的内容SupergroupKey
:
GroupKey
1 包含RecordKey
欧拉,而欧拉又包含在GroupKey
2 中;因此GroupKey
s 1 和 2 必须具有相同的SupergroupKey
.- 因为 Gauss 包含在
GroupKey
s 2 和 3 中,所以它们也必须具有相同的SupergroupKey
. 这导致GroupKey
s 1–3 具有相同的SupergroupKey
. - 由于
GroupKey
s 1–3 不RecordKey
与其余GroupKey
s 共享任何 s,因此它们是唯一分配SupergroupKey
值为 1 的。
我应该补充一点,解决方案需要是通用的。上表和结果集只是一个例子。
附录
我删除了解决方案是非迭代的要求。虽然我更喜欢这样的解决方案,但我认为这是一个不合理的限制。不幸的是,我无法使用任何基于 CLR 的解决方案;但是如果你想包含这样的解决方案,请随意。不过,我可能不会接受它作为答案。
我的真实表中的行数高达 500 万,但有时行数“仅”在一万左右。平均有 8 RecordKey
s perGroupKey
和 4 GroupKey
s per RecordKey
。我想一个解决方案将具有指数级的时间复杂度,但我仍然对解决方案感兴趣。
这个问题是关于跟踪项目之间的链接。这将其置于图形和图形处理领域。具体来说,整个数据集形成一个图,我们正在寻找该图的组成部分。这可以通过问题样本数据的图表来说明。
问题说我们可以按照 GroupKey 或 RecordKey 来查找共享该值的其他行。所以我们可以将两者都视为图中的顶点。问题继续解释 GroupKeys 1-3 如何具有相同的 SupergroupKey。这可以看作是左侧由细线连接的集群。图片还显示了由原始数据形成的另外两个组件(SupergroupKey)。
SQL Server 在 T-SQL 中内置了一些图形处理能力。然而,此时它非常微不足道,对解决这个问题没有帮助。SQL Server 还能够调出 R 和 Python,以及可供它们使用的丰富而强大的软件包套件。igraph就是其中之一。它是为“快速处理具有数百万个顶点和边(链接)的大型图形”而编写的。
在本地测试1中,使用 R 和 igraph 我能够在 2 分 22 秒内处理一百万行。这是它与当前最佳解决方案的比较:
当处理 1M 行时,1 分 40 秒用于加载和处理图形,以及更新表格。用输出填充 SSMS 结果表需要 42 秒。
Observation of Task Manager while 1M rows were processed suggest about 3GB of working memory were required. This was available on this system without paging.
I can confirm Ypercube's assessment of the recursive CTE approach. With a few hundred record keys it consumed 100% of CPU and all available RAM. Eventually tempdb grew to over 80GB and the SPID crashed.
I used Paul's table with the SupergroupKey column so there's a fair comparison between the solutions.
For some reason R objected to the accent on Poincaré. Changing it to a plain "e" allowed it to run. I didn't investigate since it's not germane to the problem at hand. I'm sure there's a solution.
Here is the code
This is what the R code does
@input_data_1
is how SQL Server transfers data from a table to R code and translates it to an R dataframe called InputDataSet.library(igraph)
imports the library into the R execution environment.df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)
load the data into an igraph object. This is an undirected graph since we can follow links from group to record or record to group. InputDataSet is SQL Server's default name for the dataset sent to R.cpts <- components(df.g, mode = c("weak"))
process the graph to find discrete sub-graphs (components) and other measures.OutputDataSet <- data.frame(cpts$membership)
SQL Server expects a data frame back from R. Its default name is OutputDataSet. The components are stored in a vector called "membership". This statement translates the vector to a data frame.OutputDataSet$VertexName <- V(df.g)$name
V() is a vector of vertices in the graph - a list of GroupKeys and RecordKeys. This copies them into the ouput data frame, creating a new column called VertexName. This is the key used to match to the source table for updating SupergroupKey.I'm not an R expert. Likely this could be optimised.
Test Data
The OP's data was used for validation. For scale tests I used the following script.
I've just now realised I've gotten the ratios the wrong way around from the OP's definition. I don't believe this will affect the timings. Records & Groups are symmetrical to this process. To the algorithm they're all just nodes in a graph.
In testing the data invariably formed a single component. I believe this is due to the uniform distribution of the data. If instead of the static 1:8 ratio hard-coded into the generation routine I had allowed the ratio to vary there would more likely have been further components.
1机器规格:Microsoft SQL Server 2017 (RTM-CU12),开发人员版(64 位),Windows 10 家庭版。16GB RAM,SSD,4 核超线程 i7,标称 2.8GHz。除了正常的系统活动(大约 4% CPU)之外,测试是当时唯一运行的项目。
这是用于性能比较的迭代 T-SQL 解决方案。
它假设可以向表中添加一个额外的列来存储超级组键,并且可以更改索引:
设置
如果您能够反转当前主键的键顺序,则不需要额外的唯一索引。
大纲
该解决方案的方法是:
执行
内联评论:
执行计划
对于密钥更新:
结果
表的最终状态是:
演示:数据库<>小提琴
性能测试
使用 Michael Green 的回答中提供的扩展测试数据集,我的笔记本电脑上的时间*是:
* Microsoft SQL Server 2017 (RTM-CU13),开发人员版(64 位),Windows 10 Pro,16GB RAM,SSD,4 核超线程 i7,标称 2.4GHz。
递归 CTE 方法——在大表中可能效率极低:
在dbfiddle.uk测试