从非常大的表中删除重复的子集

Question

我正在处理的数据相当复杂，所以我只想提供一个更简单的例子，这样我就有希望将其扩展到我正在进行的工作中。

注意：我已经找到了一种方法，但它非常慢，而且不可扩展。它在小型数据集上运行得很好，但如果我将其应用于需要运行的实际表，那将需要很长时间。

我需要删除表中所有重复的数据子集。删除重复的行很容易，但我一直在寻找一种有效的方法来删除重复的子集。

示例：

GroupID  Subset Value
-------  ----   ----
1        a      1
1        a      2
1        a      3
1        b      1
1        b      3
1        b      5
1        c      1
1        c      3
1        c      5

2        a      1
2        a      2
2        a      3
2        b      4
2        b      5
2        b      6
2        c      1
2        c      3
2        c      6

因此，在这个例子中，从GroupID 1中，我需要删除子集"b"或子集"c"，这并不重要，因为两者都包含值1,2,3。对于GroupID 2，没有任何集合是重复的，因此不会删除任何集合。

这是我用来在小范围内解决这个问题的代码。它工作得很好，但当应用于1000多万张唱片时。。。你可以想象它会非常慢(我后来被告知记录的数量，我得到的样本数据要小得多)…：

DECLARE @values TABLE (GroupID INT NOT NULL, SubSet VARCHAR(1) NOT NULL, [Value] INT NOT NULL)
INSERT INTO @values (GroupID, SubSet, [Value])
VALUES  (1,'a',1),(1,'a',2),(1,'a',3)  ,(1,'b',1),(1,'b',3),(1,'b',5)  ,(1,'c',1),(1,'c',3),(1,'c',5),
(2,'a',1),(2,'a',2),(2,'a',3)  ,(2,'b',2),(2,'b',4),(2,'b',6)  ,(2,'c',1),(2,'c',3),(2,'c',6)
SELECT *
FROM @values v
ORDER BY v.GroupID, v.SubSet, v.[Value]
SELECT x.GroupID, x.NameValues, MIN(x.SubSet)
FROM (
SELECT t1.GroupID, t1.SubSet
, NameValues = (SELECT ',' + CONVERT(VARCHAR(10), t2.[Value]) FROM @values t2 WHERE t1.GroupID = t2.GroupID AND t1.SubSet = t2.SubSet ORDER BY t2.[Value] FOR XML PATH(''))
FROM @values t1
GROUP BY t1.GroupID, t1.SubSet
) x
GROUP BY x.GroupID, x.NameValues

我在这里所做的就是按GroupID和Subset进行分组，并将所有值连接到逗号分隔的字符串中。。。然后取其在GroupID和Value列表上进行分组，并取MIN子集。

Answer 1

我会选择这样的东西：

;with cte as
(
select v.GroupID, v.SubSet, checksum_agg(v.Value) h, avg(v.Value) a
from @values v
group by v.GroupID, v.SubSet
)
delete v
from @values v
join
(
select c1.GroupID, case when c1.SubSet > c2.SubSet then c1.SubSet else c2.SubSet end SubSet
from cte c1
join cte c2 on c1.GroupID = c2.GroupID and c1.SubSet <> c2.SubSet and c1.h = c2.h and c1.a = c2.a
)x on v.GroupID = x.GroupID and v.SubSet = x.SubSet
select *
from @values

Answer 2

来自Checksum_Agg:

CHECKSUM_AGG结果不取决于桌子。

这是因为它是值的总和：1 + 2 + 3 = 3 + 2 + 1 = 3 + 3 = 6。

HashBytes被设计用于为仅在字节顺序上不同的两个输入以及其他差异产生不同的值。(两个长度可能大不相同的输入可以散列到同一个值的可能性很小。你不能把任意输入压缩到一个绝对唯一的16字节值。)

以下代码演示如何使用HashBytes为每个GroupId/Subset返回。

-- Thanks for the sample data!
DECLARE @values TABLE (GroupID INT NOT NULL, SubSet VARCHAR(1) NOT NULL, [Value] INT NOT NULL)
INSERT INTO @values (GroupID, SubSet, [Value])
VALUES  (1,'a',1),(1,'a',2),(1,'a',3)  ,(1,'b',1),(1,'b',3),(1,'b',5)  ,(1,'c',1),(1,'c',3),(1,'c',5),
(2,'a',1),(2,'a',2),(2,'a',3)  ,(2,'b',2),(2,'b',4),(2,'b',6)  ,(2,'c',1),(2,'c',3),(2,'c',6);
SELECT *
FROM @values v
ORDER BY v.GroupID, v.SubSet, v.[Value];
with
DistinctGroups as (
select distinct GroupId, Subset
from @Values ),
GroupConcatenatedValues as (
select GroupId, Subset, Convert( VarBinary(256), (
select Convert( VarChar(8000), Cast( Value as Binary(4) ), 2 ) AS [text()]
from @Values as V
where V.GroupId = DG.GroupId and V.SubSet = DG.SubSet
order by Value
for XML Path('') ), 2 ) as GroupedBinary
from DistinctGroups as DG )
-- To see the intermediate results from the CTE you can use one of the
--   following two queries instead of the last   select :
--   select * from DistinctGroups;
--   select * from GroupConcatenatedValues;
select GroupId, Subset, GroupedBinary, HashBytes( 'MD4', GroupedBinary ) as Hash
from GroupConcatenatedValues
order by GroupId, Subset;

Answer 3

您可以对一组行使用checksum_agg()。如果校验和相同，这是分组字段中"值"列相等的有力证据。

在下面的"getChecksums"cte中，我按组和子集进行分组，校验和基于您的"value"列。

在'maybeBadSubsets'cte中，我在每个聚合上加一个row_number，只是为了在校验和匹配的情况下识别第2+行。

最后，我删除了所有这样确定的子组。

with
getChecksums as (
select      groupId,
subset,
cs = checksum_agg(value)
from        @values v
group by    groupId,
subset 
),
maybeBadSubsets as (
select      groupId,
subset,
cs,
deleteSubset = 
case 
when    row_number() over (
partition by groupId, cs 
order by subset
) > 1 
then 1
end
from        getChecksums
)
delete      v 
from        @values v
where       exists (
select  0
from    maybeBadSubsets mbs
where   v.groupId = mbs.groupId
and     v.SubSet = mbs.subset
and     mbs.deleteSubset = 1
);

我不知道校验和匹配的确切可能性是多少。如果你对假阳性率不满意，你仍然可以用它以更算法的方法消除一些分支，从而大大提高性能。

注意：CTE在性能方面可能有一个怪癖。如果你发现查询引擎正在为每一行@values运行"maybeBadSubsets"，你可能需要在使用它之前将其结果放入临时表或表变量中。但我相信使用"exists"就可以了。

编辑：

我没有抓住它，但正如OP所注意到的，checksum_agg在虚假命中/未命中方面的表现似乎非常糟糕。我怀疑这可能是由于输入的简单性。我更改了

cs = checksum_agg(value)

高于

cs = checksum_agg(convert(int,hashbytes('md5', convert(char(1),value))))

取得了较好的效果。但我不知道它在更大的数据集上会如何表现。