如何在一个非常大的表中找到行之间的配对关系

Question

我有一个非常大的表(60m行)，其中包含带两列的行：set_id和object_id。set_id用于标识object_id的组。在我的情况下，这些object_id可以出现在多个集合中。

示例：

set_id | object_id
1 | 100
1 | 101
1 | 102
2 | 100
2 | 201
3 | 300
4 | 102
4 | 300
5 | 500

我需要的是检索一个至少共享一个object_id的set_id对的列表。每个set_id也将与其自身配对。成对只出现一次(即：(1,2)，但不出现(2,1))。对于上面的例子：

set_id_A | set_id_B
1 | 1
1 | 2
1 | 4
2 | 2
3 | 3
3 | 4
4 | 4
5 | 5

编写一个查询来实现这一点非常简单。问题是我的解决方案不能很好地扩展。这是我的代码：

-- #original_sets table created
CREATE TABLE #original_sets
(
[set_id] INT,
[object_id]       BIGINT
);
-- #original_sets populated here from other data
-- removed
-- index created on table:
CREATE CLUSTERED INDEX cx_original_sets
ON #original_sets ([object_id], [set_id]);
-- code to create the pairs:
SELECT
ck1.[set_id] AS set_id_A,
ck2.[set_id] AS set_id_B
FROM
#original_sets ck1
INNER JOIN
#original_sets ck2
ON ck1.[object_id] = ck2.[object_id]
AND ck1.[set_id] <= ck2.[set_id]
GROUP BY
ck1.[set_id],
ck2.[set_id];

如果original_sets表是小的甚至中等大小的，它会非常快，但一旦我达到60米的行，它就会非常慢。10个小时后我就取消了，所以我不确定它是否会结束。

我知道，在这么大的桌子上自顾自就是在找麻烦。有没有其他方法可以做得更好？谢谢

编辑1:另一件可能有助于提高性能的事情是：在我获得集合对之后，我有另一个过程，然后创建包含与原始集合相关的所有对象id的超级集合(请参见：传递闭包集群http://sqlblog.com/blogs/davide_mauri/archive/2017/11/12/lateral-thinking-transitive-closure-clustering-with-sql-server-uda-and-json.aspx顶部的图表很好地显示了它)

因为我在这之后会这样做，所以我并不真正关心set_id本身，只关心它们如何将object_id组合在一起。因此可以安全地消除重复集。也许先这样做是缩小桌子整体尺寸的好方法。

编辑2:

新版本尝试缩小原始表的大小

-- #original_sets table created
CREATE TABLE #original_sets
(
[set_id] INT,
[object_id]       BIGINT
);
-- #original_sets populated here from other data
-- removed
-- index created on table:
CREATE CLUSTERED INDEX cx_original_sets
ON #original_sets ([object_id], [set_id]);
--added this index:
CREATE CLUSTERED INDEX IDX_original_sets
ON #original_sets ([set_id], [object_id]);
-- added this part to identify sets with only one object_id 
CREATE TABLE #lonely_sets
(
[set_id] INT PRIMARY KEY
);
INSERT INTO #lonely_sets
SELECT  
[set_id]
FROM 
#original_sets
GROUP BY 
[set_id]
HAVING 
COUNT(*) = 1
--then use that data to eliminate duplicate single object sets (see edit 1 for why)
DELETE FROM #original_sets
WHERE set_id IN 
(
SELECT
[set_id ]
FROM
#lonely_sets lonely_sets
WHERE
[set_id ] NOT IN
(
SELECT
MIN(original_sets.[set_id ])
FROM
#original_sets original_sets
INNER join #lonely_sets lonely_sets
ON original_sets.set_id  =  lonely_sets.set_id 
GROUP BY
original_sets.[object_id]
)
)
-- then run this 
-- code to create the pairs as before:
SELECT
ck1.[set_id] AS set_id_A,
ck2.[set_id] AS set_id_B
FROM
#original_sets ck1
INNER JOIN
#original_sets ck2
ON ck1.[object_id] = ck2.[object_id]
AND ck1.[set_id] <= ck2.[set_id]
GROUP BY
ck1.[set_id],
ck2.[set_id];

额外的工作量将original_set减少到约1600万行。具有~1m个唯一对象ID和~7m个唯一集ID。

以下是每组对象的细分：

object_count_per_set | sets_with_that_count
67  32
49  8
42  197
41  120
38  1
37  101
35  16
30  23
29  18
28  109
27  1643
26  382
25  43
24  35
23  8
22  492
21  703
20  339
19  1548
18  2176
17  358
16  1156
15  852
14  1755
13  1845
12  2452
11  3073
10  4570
9   4723
8   9726
7   16178
6   35493
5   81091
4   211305
3   724627
2   5360781
1   789573

因此，总的来说，要处理的表要小得多，但只花了一个多小时就完成了(1035212815行受到影响)，运行起来仍然很慢。

我知道有很多重复集可以安全地消除，我只需要一个好的方法来做到这一点

Answer 1

您说表中有60米的行，大约有50米的唯一set_id和100公里的唯一object_id。

因此，平均每个object_id有600行。平均而言，ck1.[object_id] = ck2.[object_id] AND ck1.[set_id] <= ck2.[set_id]将为每一个外层行匹配300行，因此目前您的查询正在生成和聚合180亿行的内容

5000万个集合ID和6000万行意味着大多数集合将只与它们自己配对，

作为第一步，我只想找到这些具有简单GROUP BY ... COUNT的有保证的不成对集，然后在具有三角形自连接的更昂贵的部分将它们排除在考虑之外。

如果此查询仍然太慢，请提供有关#paired_sets的行数、不同object_id和set_id的数量以及其中最大object_id的大小(行数)的信息

CREATE TABLE #lonely_sets
(
[set_id] INT PRIMARY KEY
);
INSERT INTO #lonely_sets
SELECT  [set_id]
FROM #original_sets
GROUP BY [set_id]
HAVING COUNT(*) = 1;

CREATE TABLE #paired_sets
(
[set_id] INT,
[object_id] INT,
PRIMARY KEY  ([object_id], [set_id])
);
INSERT INTO #paired_sets
SELECT [set_id], [object_id]
FROM #original_sets
WHERE [set_id] NOT IN (SELECT ls.set_id FROM #lonely_sets ls);
--Final Select
SELECT [set_id] AS set_id_A, [set_id] AS set_id_B
FROM #lonely_sets
UNION ALL
SELECT
ck1.[set_id] AS set_id_A,
ck2.[set_id] AS set_id_B
FROM
#paired_sets ck1
INNER JOIN
#paired_sets ck2
ON ck1.[object_id] = ck2.[object_id]
AND ck1.[set_id] <= ck2.[set_id]
GROUP BY
ck1.[set_id],
ck2.[set_id];

Answer 2

因此，根据Martin的建议，我被指向了减少要连接的表的大小的方向，这就是我最终的目标：

我决定尝试消除重复的集合(请参阅上面我原始帖子中的编辑1)。在我的情况下，这应该做两件事：降低稍后运行自联接的表的大小，并帮助随着时间的推移进行扩展(每周都会引入新的集合，但它们通常是以前集合的副本)。

我使用了旧的XML PATH行串联技巧(我没有运行2017，否则STRING_AGG可能工作得更快？)来创建一个分号分隔的列表，列表中包含每个set_id中的所有object_id。

然后，它被用来识别包含相同对象id集的set_id，因此可以安全地消除。这将行数从60米减少到了1米。就我而言，这大约需要50分钟。有没有更快的方法来识别相同的集合？我不确定。

然后创建一个过滤后的集合表，并基于自联接创建关系表。有了新的过滤数据，运行该部分查询的时间现在只有几分钟。

这个过程中最慢的部分是XMLPATH行concat查询，时间不到一个小时。这并不理想，但因为这个过程是紧急维护程序的一部分，我愿意接受运行所需的时间。

代码：

-- #original_sets table created
CREATE TABLE #original_sets
(
[set_id] INT,
[object_id]       BIGINT
);
-- #original_sets populated here from other data
-- removed
-- index created on table:
CREATE CLUSTERED INDEX cx_original_sets
ON #original_sets ([object_id], [set_id]);
CREATE CLUSTERED INDEX IDX_original_sets
ON #original_sets ([set_id], [object_id]);
----------------------------------------------------------
CREATE TABLE #filtered_sets
(
[set_id] INT,
[object_id]       BIGINT
);
INSERT INTO #filtered_sets
SELECT
original_sets.set_id,
original_sets.[object_id]
FROM
#original_sets original_sets
INNER JOIN
(
SELECT
MIN(set_id) AS set_id
FROM
(
SELECT DISTINCT
set_id,
STUFF(
(
SELECT
'; ' +  CAST(original_sets.object_id AS VARCHAR(20))
FROM
#original_sets original_sets 
WHERE
original_sets.set_id = s2.set_id
ORDER BY
original_sets.object_id
FOR XML PATH('')
), 1, 2, ''
)                                            AS object_id_list
FROM
#original_sets s2
GROUP BY
set_id
) a
GROUP BY
object_id_list
) unique_sets
ON original_clusters.cluster_id = unique_sets.cluster_id

CREATE CLUSTERED INDEX cx_filtered_sets
ON #filtered_sets ([object_id], [set_id]);
CREATE NONCLUSTERED INDEX IDX_filtered_sets
ON #filtered_sets ([set_id],[object_id]);
----------------------------------------------------------
-- then run this 
-- code to create the pairs as before:
SELECT
ck1.[set_id] AS set_id_A,
ck2.[set_id] AS set_id_B
FROM
#filtered_sets ck1
INNER JOIN
#filtered_sets  ck2
ON ck1.[object_id] = ck2.[object_id]
AND ck1.[set_id] <= ck2.[set_id]
GROUP BY
ck1.[set_id],
ck2.[set_id];

我接受了马丁的回答，因为它对我指明我需要去的地方很有用。谢谢