5
votes

Supprimer les sous-ensembles dupliqués d'une très grande table

Les données avec lesquelles je travaille sont assez compliquées, je vais donc simplement donner un exemple plus simple pour pouvoir, espérons-le, étendre cela à ce sur quoi je travaille.

Remarque: j'ai déjà trouvé un moyen de le faire, mais c'est extrêmement lent et non évolutif. Cela fonctionne très bien sur de petits ensembles de données, mais si je l'appliquais aux tables réelles sur lesquelles il doit fonctionner, cela prendrait une éternité.

Je dois supprimer des sous-ensembles de données en double entiers dans une table. La suppression des lignes en double est facile, mais je ne peux pas trouver un moyen efficace de supprimer les sous-ensembles en double.

Exemple:

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

Dans cet exemple, à partir de GroupID 1, j'aurais besoin de supprimer le sous-ensemble «b» ou le sous-ensemble «c», peu importe lequel puisque les deux contiennent les valeurs 1, 2, 3. Pour GroupID 2, aucun des ensembles n'est dupliqué, donc aucun n'est supprimé.

Voici le code que j'ai utilisé pour résoudre ce problème à petite échelle. Cela fonctionne très bien, mais appliqué à plus de 10 millions d'enregistrements ... vous pouvez imaginer que ce serait très lent (j'ai été informé plus tard du nombre d'enregistrements, l'échantillon de données qui m'a été donné était beaucoup plus petit) ...: p>

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

Tout ce que je fais ici, c'est de grouper par GroupID et sous-ensemble et de concaténer toutes les valeurs dans une chaîne délimitée par des virgules ... puis de prendre cela et de grouper sur GroupID et Value list et en prenant le sous-ensemble MIN.


2 commentaires

Salut, avez-vous essayé d'effectuer cette requête en même temps, mais avec l'utilisation de cte? Juste pour proposer des performances comparatives.


@pascalsanchez non, je ne l'ai pas fait, mais je vais essayer. Je me demandais s'il y avait un moyen d'accomplir cela avec un CTE récursif, mais je ne pense pas que ce serait plus efficace avec une grande table.


3 Réponses :


1
votes

Vous pouvez utiliser checksum_agg () sur un ensemble de lignes. Si les sommes de contrôle sont les mêmes, c'est une preuve solide que les colonnes 'values' sont égales dans les champs groupés.

Dans le cte 'getChecksums' ci-dessous, je regroupe par groupe et sous-ensemble, avec une somme de contrôle basée sur votre ' valeur ».

Dans le cte 'MaybeBadSubsets', je mets un row_number sur chaque agrégation juste pour identifier la 2ème + ligne dans le cas où les sommes de contrôle correspondent.

Enfin, je supprime tous les sous-groupes ainsi identifiés.

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

Je ne sais pas quelle est la probabilité exacte que les sommes de contrôle correspondent. Si vous n'êtes pas à l'aise avec le taux de faux positifs, vous pouvez toujours l'utiliser pour éliminer certaines branches dans une approche plus algorithmique afin d'améliorer considérablement les performances.

Remarque: les CTE peuvent avoir une bizarrerie en termes de performances . Si vous constatez que le moteur de requête exécute «mightBadSubsets» pour chaque ligne de @values, vous devrez peut-être placer ses résultats dans une table temporaire ou une variable de table avant de l'utiliser. Mais je crois qu'avec «existe», vous êtes d'accord pour autant.

EDIT:

Je n'ai pas compris, mais comme le OP remarqué, checksum_agg semble fonctionner très mal en termes de faux succès / échecs. Je soupçonne que cela pourrait être dû à la simplicité de l'entrée. J'ai changé

cs = checksum_agg(value)

ci-dessus en

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
            );

et j'ai obtenu de meilleurs résultats. Mais je ne sais pas comment cela fonctionnerait sur des ensembles de données plus volumineux.


9 commentaires

Merci! Je vais essayer et voir comment cela fonctionne. Pour mon utilisation spécifique, cela n'a pas besoin d'être parfait, nous essayons simplement de réduire les données. S'il reste encore des dups, ce sera probablement bien. J'ai en fait pensé à utiliser la somme de contrôle, mais je ne savais pas comment le faire fonctionner, j'avais complètement oublié la fonction d'agrégation pour cela.


Hmm, il semble y avoir un bug là-dedans, car il a supprimé le sous-ensemble 'b' de GroupID 2, alors qu'il n'aurait pas dû. Je vais essayer de comprendre pourquoi.


Ahh, d'accord, j'ai compris, on dirait que non seulement CHECKSUM_AGG produira de faux négatifs, mais je n'ai pas pensé aux faux positifs. Il a supprimé les sous-ensembles avec des valeurs de somme de contrôle correspondantes, mais n'étaient pas en fait des sous-ensembles équivalents.


Hé, j'imagine que vous allez maintenant utiliser l'approche cte de Kirill. Cependant, pourriez-vous essayer le changement mentionné ci-dessus dans l'édition juste pour satisfaire ma curiosité?


ça ira! Je serai de retour au bureau vendredi, désolé de devoir vous tenir en haleine. Lol


Lors de la comparaison des sommes de contrôle, il y a toujours un risque que 2 sommes de contrôle pour différentes données soient exactement les mêmes. Et ce n'est pas seulement lié à SQL. C'est pourquoi il est plus sûr de le comparer également avec quelque chose en plus, comme un total ou une moyenne des données. Juste pour réduire les chances d'un faux positif. (Personnellement, je pense le comparer à un STRING_AGG serait plus sûr, mais cela nécessiterait MS Sql Server 2017 ou version ultérieure)


Donc, fondamentalement, une comparaison de somme de contrôle peut prouver à 100% que les données sont différentes si les sommes de contrôle sont différentes. Mais cela ne prouve pas à 100% que les données sont les mêmes si les sommes de contrôle sont les mêmes.


@LukStorms, je comprends cela, je n'étais tout simplement pas préparé à ce que la probabilité d'un match soit si forte. Je me demandais si cela avait à voir avec les entrées très petites et simples (1, 2, 3), (1, 3, 5), etc. Je voulais donc savoir si la somme de contrôle agrégée par rapport à un entier d'une valeur hachée jetterait suffisamment de clés pour que la fonction agg donne beaucoup moins de correspondances indésirables.


On dirait que cela produit les résultats corrects sur l'échantillon de données que j'ai fourni. Je vais l'appliquer au plus grand ensemble de données pour voir comment il fonctionne et s'il me donne les bons résultats. Une chose que j'aimerais noter, que j'ai découverte ce matin avec la méthode de Kirill, c'est qu'elle produit toujours de fausses correspondances, mais un très faible pourcentage. Je travaille donc sur l'utilisation d'autres combinaisons de fonctions d'agrégation pour supprimer les fausses correspondances.



4
votes

J'irais avec quelque chose comme ceci:

;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


6 commentaires

Nice, passe le premier test, me donne les résultats que je recherchais. Je vais le tester sur l'ensemble de données complet et voir comment il fonctionne sur plus de 10 millions d'enregistrements.


Je viens de l'exécuter sur le plus grand ensemble de données, fonctionne certainement plus rapidement que mon code d'origine. Merci!


@chadwin, cool. J'ai mis à jour la requête, vous pouvez essayer la nouvelle version, peut-être qu'elle peut être légèrement plus rapide.


J'ai donc plongé un peu plus profondément dans cela. Il semble que l'utilisation de CHECKSUM_AGG et AVG produise encore de fausses correspondances, mais un pourcentage très faible. Cependant, j'ai développé votre méthode et j'ai inclus d'autres champs agrégés tels que SUM, COUNT, MIN, MAX, etc. Il semble que CHECKSUM_AGG, AVG, COUNT, SUM soit le seul à ce jour à produire une correspondance parfaite avec mon code d'origine . Mais je teste d'autres combinaisons de fonctions d'agrégation pour voir lesquelles fonctionnent mieux mais produisent toujours les mêmes résultats.


Au cas où vous seriez intéressé ... J'ai effectué un test sur les 64 combinaisons possibles d'utilisation de CHECKSUM_AGG, AVG, COUNT, SUM, MIN, MAX ... les seules combinaisons de deux fonctions d'agrégation qui ont produit zéro fausses correspondances étaient SUM & (MIN ou MAX) ||| CHECKSUM_AGG & SUM.


@chadwin, je pense que cela dépend de la distribution des valeurs. Heureux que vous ayez trouvé la meilleure approche dans votre cas.



2
votes

Depuis Checksum_Agg :

Le résultat CHECKSUM_AGG ne dépend pas de l'ordre des lignes dans la table.

C'est parce qu'il s'agit d'une somme des valeurs: 1 + 2 + 3 = 3 + 2 + 1 = 3 + 3 = 6 .

HashBytes est conçu pour produire une valeur différente pour deux entrées qui ne diffèrent que dans l'ordre des octets, ainsi que d'autres différences. (Il y a une petite possibilité que deux entrées, peut-être de longueurs très différentes, puissent avoir la même valeur. Vous ne pouvez pas prendre une entrée arbitraire et la réduire à une valeur absolument unique de 16 octets.)

Le code suivant montre comment utiliser HashBytes pour renvoyer pour chaque 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;


0 commentaires