[Erledigt] Dubletten

louis · 18.02.2010, 10:03

Hi,

ich habe folgendes Problem: ich habe Dateien mit kommaseparierten Daten pro Zeile in jeder Datei. Die Dateien sind alle so ca. 30 - 40 MB gross, insgesamt sind es ca. 20 Mio Datensätze, die ich in eine Tabelle einer MySQL DB einfügen möchte.

Eine "Spalte" in diesen Dateien ist ein 40-stelliger Hashwert. Dummerweise können hier Dubletten auftreten, die ich ausfiltern muss. Derjenige, der die Dateien erstellt, kommt leider nicht dahinter, warum die Dubletten auftreten, bei einem 40stelligen Hash können bei den Datenmengen wohl Kollisionen auftreten?!? Leider hat der besagte Mensch keine Zeit und Lust, sich um dieses Problem zu kümmern, und ich habe auch keine Möglichkeit, ihn dahin zu pushen, also muss ich das irgendwie auf meiner Seite lösen.

Mein erster Gedanke war, auf die entspechende Spalte in der DB einen UNIQUE Key zu legen...schön und gut, aber nach ca. 1 Mio Zeilen in der DB wurde der Insert dermassen langsam (was bei der Größe des Hashes und der Datenmenge auch verständlich ist), dass ich damit nicht mehr arbeiten konnte. Also habe ich den UNIQUE Index wieder entfernt, damit das Einfügen wenigstens einigermaßen flutscht...

Ein Versuch, mit einem Query á la

Code:

select a.hash
from tabelle a
inner join tabelle b
on a.hash = b.hash
where a.id != b.id

kommt bei der Datenmenge auch nicht in Frage, wenn man bedenkt, dass DB intern das kartesische Produkt der Tabelle mit sich selbst zur Auswertung gebildet werden muss. Bei 20 Mio Zeilen sind das mal locker 4*10^14 Zeilen

Mir fällt nix gescheites ein, was einigermassen performant ist...mein armes Laptop schaltet schon gar nicht mehr den Lüfter ab...irgendwann wird es wohl platzen

Hat einer von euch eine Idee, wie ich das Problem datenbanktechnisch angehen könnte?

Eine Alternative wäre, bereits die zugrundelegenden Textdateien mit betriebssystemmitteln (Windows) oder speziellen auf sowas optimierten Prögrämmchen nach Dubletten zu durchforsten. Hat da einer ne schlaue Idee? Wenn's unter Unix mit grep, pipes und Konsorten vielleicht eine bessere Möglichkeit geben würde (damit kenne ich mich leider nicht wirklich aus), wäre das natürlich auch eine Möglichkeit...ein Linux ist ja auch schnell installiert.

Vielen Dank für's mitdenken...

18.02.2010, 10:28

Da gibt es wie immer verschiedene Lösungswege. Am besten das Ganze in kleine Schritte unterteilen

Eine Strategie wäre:

a) Die Tabellen ohne jeden Index anlegen
b) Alle Datensätze ohne Prüfung einlesen
c) nun für jede Tabelle einen normalen Index auf die Spalte "hash" anlegen ( CREATE INDEX sx_tabelleX_01 ON tabelleX (hash); )
d) Jetzt per SQL auf Doppelte prüfen und doppelte löschen

Vorsicht: Hinter Punkt d) verstecken sich allerdings noch diverse Detailprobleme.

Grüße
Thomas

louis · 18.02.2010, 11:48

Zitat:

Zitat von thomas_w

c) nun für jede Tabelle einen normalen Index auf die Spalte "hash" anlegen ( CREATE INDEX sx_tabelleX_01 ON tabelleX (hash); )
d) Jetzt per SQL auf Doppelte prüfen und doppelte löschen

Vorsicht: Hinter Punkt d) verstecken sich allerdings noch diverse Detailprobleme.

Hi Thomas,

danke für deine Antwort. Sowas ähnliches habe ich auch schon versucht...das nachträgliche Anlagen eines Indexes hat ewig gedauert, ich habe den Query nach ca. einer halben Stunde abgebrochen. Würde deiner Ansicht nach ein Index die SQL basierte Lösung der Dublettensuche so beschleunigen, dass es einigermaßen rennt? Das Problem des Kreuzprodukts bestünde ja immer noch, oder wäre das durch den Index nicht mehr der Fall?

nikosch · 18.02.2010, 12:47

Wie oft kommt denn so ein Insert vor? Ansonsten würde ich in einer geeigneten Sprache einen Bubblesort o.ä. für die Datei (oder eine Menge von Files - man könnte ja bspw. nach Anfangsbuchstaben der Hashes verteilen) schreiben, das auf einer schnellen Maschine drüberlaufen lassen (und wenns nen Tag dauert) und anschliessend durch linearen Vergleich des Vorgängers die Dubletten rauswerfen.

18.02.2010, 12:55

Ein normaler Index hilft der Datenbank beim schnellen Suchen, Sortieren und Vergleichen. Genau dass muss ja die Dublettensuche machen. Mit den speziellen Indices wie UNIQUE INDEX und PRIMARY KEY kann zudem Eindeutigkeit erzwungen werden. So betrachtet kommt Du um einen normalen Index nicht herum, ausser die Daten werden schon ausserhalb bereinigt. Das Problem eines Kreuzproduktes hat ja nichts mit dem Index, sondern mit dem "falschen" SQL zu tun.

Eine andere Möglichkeit wäre der 'LOAD' von Daten. Dass ist bei Massendaten sinnvoll, da müsstest Du Dich aber mal selbst einlesen.

MySQL :: MySQL 5.0 Reference Manual :: 12.2.6 LOAD DATA INFILE Syntax

Damit lassen sich eventuell auch 'Dubletten' in eine Exception-Tabelle aussortieren. Das habe ich aber mit MySQL noch nie probiert.

Grüße
Thomas

louis · 18.02.2010, 15:20

Zitat:

Zitat von nikosch

Wie oft kommt denn so ein Insert vor? Ansonsten würde ich in einer geeigneten Sprache einen Bubblesort o.ä. für die Datei (oder eine Menge von Files - man könnte ja bspw. nach Anfangsbuchstaben der Hashes verteilen) schreiben, das auf einer schnellen Maschine drüberlaufen lassen (und wenns nen Tag dauert) und anschliessend durch linearen Vergleich des Vorgängers die Dubletten rauswerfen.

Hi,

prinzipiell muss ich den Insert jetzt einmal machen...so ca. alle halbe Jahre kommen dann ein paar Millionen weitere Daten hinzu. Das wäre mit deinem Vorschlag theoretisch auch vereinbar, würde das ganze aber noch etwas verkomplizieren. Mit Java könnte ich das ganze umsetzen...an der schnellen Maschine wird es allerdings ein bisschen hapern, aber du hast recht, das kann ja dann so vor sich hin laufen. Hmmm...alles nicht so einfach

louis · 18.02.2010, 15:24

Zitat:

Zitat von thomas_w

Eine andere Möglichkeit wäre der 'LOAD' von Daten. Dass ist bei Massendaten sinnvoll, da müsstest Du Dich aber mal selbst einlesen.

MySQL :: MySQL 5.0 Reference Manual :: 12.2.6 LOAD DATA INFILE Syntax

Damit lassen sich eventuell auch 'Dubletten' in eine Exception-Tabelle aussortieren. Das habe ich aber mit MySQL noch nie probiert.

Diese Methode scheidet leider aus, da ich die Daten vor dem Schreiben in die DB noch ein bisschen modifizieren muss...das könnte ich allerdings auch machen, indem ich die Daten von der ursprünglichen Tabelle in eine weitere Tabelle transferiere. Wie ich mit einem LOAD Dubletten ohne einen UNIQUE Index ausschließe, habe ich allerdings noch nicht verstanden.

erc · 18.02.2010, 17:43

Zitat:

Zitat von louis

Ein Versuch, mit einem Query á la

Code:

select a.hash
from tabelle a
inner join tabelle b
on a.hash = b.hash
where a.id != b.id

kommt bei der Datenmenge auch nicht in Frage, wenn man bedenkt, dass DB intern das kartesische Produkt der Tabelle mit sich selbst zur Auswertung gebildet werden muss. Bei 20 Mio Zeilen sind das mal locker 4*10^14 Zeilen

Dann würde ich dringend die Datenbank wechseln. Wenn die Datenbank so arbeitet wie du denkst, würde damit kein JOIN mehr "funktionieren". Der Query ist aber auch zu kompliziert gedacht, ein COUNT und GROUP BY hash tuns auch.

18.02.2010, 22:02

Zitat:

Zitat von louis

Diese Methode scheidet leider aus, da ich die Daten vor dem Schreiben in die DB noch ein bisschen modifizieren muss...

Im Prinzip muss die Original-CSV per Programm eingelesen, nach Deinen Regeln bearbeitet und anschließend wieder als CSV rausgeschrieben werden. Diese CSV-Datei könntest Du dann in die Datenbank per LOAD einlesen.

Nochmal eine etwas andere Vorgehensweise:

Gesetzt die Daten sind in der Datenbank und die Tabellen sehe so aus:

Code:

CREATE TABLE tabelle (
 id INT NOT NULL AUTO_INCEMENT,
 hash CHAR(40) NOT NULL,
 ..weitere Spalten...

)

Für den eigentlichen Dublettenvergleich, werden die Datenmengen in eine kleinere Tabelle eingelesen und damit für die Dublettensuche reduziert.

Code:

CREATE TABLE tabelle_klein (
 id INT NOT NULL,
 hash CHAR(40) NOT NULL
)

INSERT INTO tabelle_klein
SELECT id, hash FROM tabelle;

Jetzt den Index auf die "kleine" Tabelle setzen.

Code:

CREATE INDEX sx_tabelle_klein ON tabelle_klein(hash);

Prüfen ob innerhalb der Tabelle_klein doppelte "hash" vorhanden sind.

Code:

SELECT hash, COUNT(*) As Anzahl FROM tabelle_klein
GROUP BY hash
HAVING COUNT(*) > 1

Die "Dubletten" ermitteln und (je nach Menge) manuell oder automatisch in der "grossen" Tabelle löschen.

Grüße
Thomas

louis · 19.02.2010, 08:43

Moin,

vielen Dank Jungs für die verschiedenen Denkanstöße...jetzt habe ich erst mal genug "Futter" und kann ein bisschen experimentieren, welche Methode die beste für mich ist.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
2 Tabellen, 1 Ausgabe (+Dubletten abfangen)	madSoul	Datenbanken	2	04.09.2006 10:37
Dubletten - aber anders	Lampe	Datenbanken	3	23.03.2006 20:32
Multi-Array Dubletten löschen und sortieren		PHP Tipps 2005-2	3	11.06.2005 00:25
Dubletten herausfiltern mit verbinden 2er tabellen.	robo47	Datenbanken	2	12.05.2005 11:59

18.02.2010, 10:03
louis Erfahrener Benutzer Registriert seit: 17.07.2006 Beiträge: 140	[Erledigt] Dubletten Hi, ich habe folgendes Problem: ich habe Dateien mit kommaseparierten Daten pro Zeile in jeder Datei. Die Dateien sind alle so ca. 30 - 40 MB gross, insgesamt sind es ca. 20 Mio Datensätze, die ich in eine Tabelle einer MySQL DB einfügen möchte. Eine "Spalte" in diesen Dateien ist ein 40-stelliger Hashwert. Dummerweise können hier Dubletten auftreten, die ich ausfiltern muss. Derjenige, der die Dateien erstellt, kommt leider nicht dahinter, warum die Dubletten auftreten, bei einem 40stelligen Hash können bei den Datenmengen wohl Kollisionen auftreten?!? Leider hat der besagte Mensch keine Zeit und Lust, sich um dieses Problem zu kümmern, und ich habe auch keine Möglichkeit, ihn dahin zu pushen, also muss ich das irgendwie auf meiner Seite lösen. Mein erster Gedanke war, auf die entspechende Spalte in der DB einen UNIQUE Key zu legen...schön und gut, aber nach ca. 1 Mio Zeilen in der DB wurde der Insert dermassen langsam (was bei der Größe des Hashes und der Datenmenge auch verständlich ist), dass ich damit nicht mehr arbeiten konnte. Also habe ich den UNIQUE Index wieder entfernt, damit das Einfügen wenigstens einigermaßen flutscht... Ein Versuch, mit einem Query á la Code: select a.hash from tabelle a inner join tabelle b on a.hash = b.hash where a.id != b.id kommt bei der Datenmenge auch nicht in Frage, wenn man bedenkt, dass DB intern das kartesische Produkt der Tabelle mit sich selbst zur Auswertung gebildet werden muss. Bei 20 Mio Zeilen sind das mal locker 4*10^14 Zeilen Mir fällt nix gescheites ein, was einigermassen performant ist...mein armes Laptop schaltet schon gar nicht mehr den Lüfter ab...irgendwann wird es wohl platzen Hat einer von euch eine Idee, wie ich das Problem datenbanktechnisch angehen könnte? Eine Alternative wäre, bereits die zugrundelegenden Textdateien mit betriebssystemmitteln (Windows) oder speziellen auf sowas optimierten Prögrämmchen nach Dubletten zu durchforsten. Hat da einer ne schlaue Idee? Wenn's unter Unix mit grep, pipes und Konsorten vielleicht eine bessere Möglichkeit geben würde (damit kenne ich mich leider nicht wirklich aus), wäre das natürlich auch eine Möglichkeit...ein Linux ist ja auch schnell installiert. Vielen Dank für's mitdenken... __________________ mfg louis


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

18.02.2010, 10:28
thomas_w Gast Beiträge: n/a	Da gibt es wie immer verschiedene Lösungswege. Am besten das Ganze in kleine Schritte unterteilen Eine Strategie wäre: a) Die Tabellen ohne jeden Index anlegen b) Alle Datensätze ohne Prüfung einlesen c) nun für jede Tabelle einen normalen Index auf die Spalte "hash" anlegen ( CREATE INDEX sx_tabelleX_01 ON tabelleX (hash); ) d) Jetzt per SQL auf Doppelte prüfen und doppelte löschen Vorsicht: Hinter Punkt d) verstecken sich allerdings noch diverse Detailprobleme. Grüße Thomas

18.02.2010, 12:47
nikosch moderatives Dielektrikum Registriert seit: 21.05.2008 Beiträge: 35.987 PHP-Kenntnisse: Fortgeschritten	Wie oft kommt denn so ein Insert vor? Ansonsten würde ich in einer geeigneten Sprache einen Bubblesort o.ä. für die Datei (oder eine Menge von Files - man könnte ja bspw. nach Anfangsbuchstaben der Hashes verteilen) schreiben, das auf einer schnellen Maschine drüberlaufen lassen (und wenns nen Tag dauert) und anschliessend durch linearen Vergleich des Vorgängers die Dubletten rauswerfen. __________________ -- One pixel is still too big. Please make it smaller. ASAP. Initiative Mittelstand. Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers. --

18.02.2010, 12:55
thomas_w Gast Beiträge: n/a	Ein normaler Index hilft der Datenbank beim schnellen Suchen, Sortieren und Vergleichen. Genau dass muss ja die Dublettensuche machen. Mit den speziellen Indices wie UNIQUE INDEX und PRIMARY KEY kann zudem Eindeutigkeit erzwungen werden. So betrachtet kommt Du um einen normalen Index nicht herum, ausser die Daten werden schon ausserhalb bereinigt. Das Problem eines Kreuzproduktes hat ja nichts mit dem Index, sondern mit dem "falschen" SQL zu tun. Eine andere Möglichkeit wäre der 'LOAD' von Daten. Dass ist bei Massendaten sinnvoll, da müsstest Du Dich aber mal selbst einlesen. MySQL :: MySQL 5.0 Reference Manual :: 12.2.6 LOAD DATA INFILE Syntax Damit lassen sich eventuell auch 'Dubletten' in eine Exception-Tabelle aussortieren. Das habe ich aber mit MySQL noch nie probiert. Grüße Thomas

19.02.2010, 08:43
louis Erfahrener Benutzer Registriert seit: 17.07.2006 Beiträge: 140	Moin, vielen Dank Jungs für die verschiedenen Denkanstöße...jetzt habe ich erst mal genug "Futter" und kann ein bisschen experimentieren, welche Methode die beste für mich ist. __________________ mfg louis