Comment extraire efficacement le nombre de chaque élément d'un grand ensemble de données?

Question

Le problème est le suivant:

• Entrée: Tous les articles de Wikipedia (33GB de texte)
  
• Sortie: Nombre de chaque skipgram mots (n-grammes avec skips maximum de k) de Wikipedia dans le fichier SQLite.

schéma de la table de sortie est:

CREATE TABLE [tokens] ([token] TEXT UNIQUE NOT NULL PRIMARY KEY, [count] INTEGER NOT NULL 

L'approche naïve est que pour chaque skipgram nous créons un nouveau record dans le compteur de table ou incrément dans le dossier existant:

INSERT OR REPLACE INTO [tokens] VALUES (@token, COALESCE((SELECT count FROM [tokens] WHERE token=@token), 0) + 1) 

Le problème avec cette approche est que l'index est constamment mis à jour et lorsque la base de données passe à plusieurs giga, ces mises à jour sont très lentes. Nous pouvons résoudre cela en créant la table "jetons" sans index et en ajoutant l'index à la fin du traitement.

Le problème est que l'instruction select SELECT count FROM [tokens] WHERE token=@token qui doit analyser la table réduit considérablement les performances.

La meilleure méthode que je l'ai trouvé à ce jour est la suite (j'utilise C#):

1. Créer une Dictionary<string,int> pour compter les jetons.

2. Ajoutez des jetons à ce dictionnaire jusqu'à ce qu'il devienne trop grand pour tenir dans la RAM.

3. Insérer (ne pas mettre à jour) les jetons du dictionnaire pour une table temporaire sans index. Le tableau a suivant le schéma:

   CREATE TABLE [temp] ([token] TEXT, [count] INTEGER) 
   

4. S'il y a plus de jetons, désactivez le dictionnaire et passez à l'étape 2.

5. jetons de copie de table temporaire à la table des jetons:

   INSERT INTO [tokens] SELECT [token], SUM([count]) AS [count] FROM [temp] GROUP BY [token] 
   

Cette méthode prend seulement "24 heures" pour traiter l'ensemble de données, mais je crois que ce n'est pas la meilleure approche parce que l'étape 5 prend 22 heures sur 24.

Connaissez-vous une approche alternative qui peut résoudre ce problème?

P.S. Mon application est à un seul thread et je fais les insertions ci-dessus en lots (100000 par lot) dans la transaction.

Answer 1

Je suggère d'ajouter SET TRANSACTION ISOLATION READ UNCOMMITTED. Cela signifie qu'il est possible que les comptes soient légèrement décalés, en particulier dans un environnement threadé où plusieurs essayent d'insérer/de mettre à jour en même temps.

Answer 2

Je suggère de créer une autre table avec la même définition, de remplir la table dans un certain état, de fusionner les résultats à la table principale, de purger la table et de commencer à traiter le prochain ensemble d'éléments.

Answer 3

Si vous avez beaucoup de concerts à ...

Je vous suggère de ne pas compter les jetons au fur et à mesure, mais plutôt d'ajouter tous les jetons dans une seule table et de créer un index qui organise les jetons.

CREATE TABLE tokens (token TEXT); 
CREATE INDEX tokens_token ON tokens (token ASC); 

puis ajoutez tous jeton un à la fois ...

INSERT INTO tokens VALUES ('Global Warming'); 
INSERT INTO tokens VALUES ('Global Cooling'); 

execute enfin un SELECT ... GROUP BY

SELECT token, COUNT(0) token_count FROM tokens GROUP BY token 

Answer 4

Cela sonne comme un bon endroit pour utiliser un « comptage fleurs filtre "pour moi.

Il faudrait deux passages sur vos données, et c'est un peu heuristique, mais cela devrait être rapide. Les filtres Bloom permettent des tests d'insertion et de présence en temps constant. Un filtre de bloom de comptage compte combien d'une valeur particulière a été trouvée, par opposition au filtre de bloom habituel qui ne garde que la trace de la présence/absence.