时间戳

首页 > 解决方案 > 如何在非常大的表中查找行之间的配对关系

sql-server - 如何在非常大的表中查找行之间的配对关系

问题描述

我有一个非常大的表（60m 行），其中包含两列的行：set_id 和 object_id。set_id 用于标识 object_id 组。就我而言，这些 object_ids 可以出现在多个集合中。

例子：

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 表很小甚至中等大小，它会非常快，但是一旦我达到 60m 行，它真的很慢。我最终在 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_ids 本身，只关心它们如何将 object_ids 组合在一起。因此可以安全地消除重复集。也许首先这样做是减小表格整体大小的好方法。

编辑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 减少到 ~16m 行。具有 ~1m 唯一 object_ids 和 ~7m 唯一 set_ids。

以下是每组对象的细分：

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

所以总体上要处理一个小得多的表，但只花了一个多小时就完成了（受影响的 1,035,212,815 行），它运行起来仍然很慢。

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

标签： sql-server

解决方案

你说你在表中有 60m 行和大约 50m 唯一 set_ids 和 100k 唯一 object_ids。

所以平均每个 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];

推荐阅读