Hab ein kleine WebApp in der ich eine Datenbank mit 50000 Städten durchsuchen muss. Bei der Suche gebe ich einfach die Stadt zurück, deren Name am Ähnlichsten zum Suchbegriff ist (Ähnlichkeit errechnet mit Levenshtein-Distanz).
Auf meinem Laptop dauert eine Suchanfrage 1 Sekunde. Ich muss aber 60 Suchanfragen hintereinder ausführen. Ob das schneller gehen wird auf einem echten Server bezweifle ich, da ich das allerbilligste Hosting Angebot nehmen werde.
Wie kann ich hier die Performance steigern?
(Habe vollen Zugriff auf Datenbank und deren Inhalt, benutzte Spring+Hibernate)
Auf meinem Laptop dauert eine Suchanfrage 1 Sekunde. Ich muss aber 60 Suchanfragen hintereinder ausführen. Ob das schneller gehen wird auf einem echten Server bezweifle ich, da ich das allerbilligste Hosting Angebot nehmen werde.
Wie kann ich hier die Performance steigern?
(Habe vollen Zugriff auf Datenbank und deren Inhalt, benutzte Spring+Hibernate)
|
1,2k ● 1 ● 6 |
3 Antworten
Da es nur 50k Städte sind, kannst du einfach alle Stadtnamen runterladen, dann in-memory deinen Algorithmus durchführen und schon hast du deine Antwort. SQL ist für algorithmische Berechnungen 100 mal langsamer als die Programmiersprache deiner Wahl.
|
28 ● 2 |
Ich kann dir da nicht viel Hoffnung machen. Der "Levenshtein distance" Algorithmus läßt sich auf Ebene der Datenbank nicht unterstützen (z.B. mit einem Index). Aber das ganze sollte mit vielen schnellen CPUs skalieren und sollte auf einem Server mit 64 CPUs ausreichenend Durchsatz erreichen. Wenn das nicht geht, sollte man versuchen, die Implementierung des Algorithmus optimieren.
Folgender Ansatz läuft den meisten Datenbankabfragesprachen zuwider, aber vieleicht kenne ich mich nur nicht genug mit Spring+Hibernate aus! Der übliche Abfrage wäre grob
select Name from City
where LevenshteinDistanz(Name,'Humburg')
= (select min(LevenshteinDistanz(Name,'Humburg')) from City)
Die Datenbank würde dann für jeden der 50,000 Datensätze die genaue LevenshteinDistanz bestimmen, auch wenn die Levenshtein-Distanz eines Satzes wesentlich höher ist, als das bereits gefundene Minimum. Anders gesagt es gibt keine Abbruch bzw. Filterkriterien.
So etwas müßte es aber geben, um die Abfrage zu beschleunigen:
1) Abbruchkriterium, sobald eine Distanz = 0
2) Abbruchkriterium, wenn dass vorläufige Minimum z.B. 2 ist, muß die Levenshtein-Distanz für einen Datensatz nicht weiter berechnet werden, wenn sie mindestens 2 ist; z.B. alle Datensätze mit Längendifferenz >2 fallen dann aus.
Wenn du die Levenshtein-Distanz nicht mit einer Datenbankfunktion realisierst (die sich in vielen DB_System nachrüchsten läßt) sondern mit Java und z.B. einem Cursor, ließen sich sicherlich Abbruchkriterien definieren. Z.B. sollte die DB die Datensätze sortiert in einer Reichenfolge liefern, die die Anfangbuchstaben und Gesamtlänge berücksichtigt. Die Funktion zur Berechnung der Levenshtein-Distanz bekommt ein Abbruchkriterium, ab dem die Funktion nur zurückgibt 'mindestens 4' aber nicht den genauen Wert '17'.
Folgender Ansatz läuft den meisten Datenbankabfragesprachen zuwider, aber vieleicht kenne ich mich nur nicht genug mit Spring+Hibernate aus! Der übliche Abfrage wäre grob
select Name from City
where LevenshteinDistanz(Name,'Humburg')
= (select min(LevenshteinDistanz(Name,'Humburg')) from City)
Die Datenbank würde dann für jeden der 50,000 Datensätze die genaue LevenshteinDistanz bestimmen, auch wenn die Levenshtein-Distanz eines Satzes wesentlich höher ist, als das bereits gefundene Minimum. Anders gesagt es gibt keine Abbruch bzw. Filterkriterien.
So etwas müßte es aber geben, um die Abfrage zu beschleunigen:
1) Abbruchkriterium, sobald eine Distanz = 0
2) Abbruchkriterium, wenn dass vorläufige Minimum z.B. 2 ist, muß die Levenshtein-Distanz für einen Datensatz nicht weiter berechnet werden, wenn sie mindestens 2 ist; z.B. alle Datensätze mit Längendifferenz >2 fallen dann aus.
Wenn du die Levenshtein-Distanz nicht mit einer Datenbankfunktion realisierst (die sich in vielen DB_System nachrüchsten läßt) sondern mit Java und z.B. einem Cursor, ließen sich sicherlich Abbruchkriterien definieren. Z.B. sollte die DB die Datensätze sortiert in einer Reichenfolge liefern, die die Anfangbuchstaben und Gesamtlänge berücksichtigt. Die Funktion zur Berechnung der Levenshtein-Distanz bekommt ein Abbruchkriterium, ab dem die Funktion nur zurückgibt 'mindestens 4' aber nicht den genauen Wert '17'.
|
447 ● 3 |
Wie mein Vorredner schon sagt:
Das ganze wird für jede Zeile berechnet. Anders als bei einer einfach Where Klausel, die sich nicht den kompletten Wert anschaut, sondern direkt ab dem ersten Punkt vergleicht, wird hier die komplette Tabelle abgefragt.
Wenn du das ganze noch weiteroptimieren willst, ohne da Hardwarepower hinten "reinzustecken", dann nur mit weiteren Bedingungen. (Also where Klauseln, z.B.: Nur bestimmtes Bundesland, nur bestimmte gefundene Menge, nur bestimmte Anfangsbuchstaben, usw). Quasi irgendeine Berechnung, die vorher schon eine Bedingung setzt, wobei die Berechnung viel weniger kompliziert sein darf, als deine Vergleichsfunktion.
Bsp:
Liebe Grüße
Das ganze wird für jede Zeile berechnet. Anders als bei einer einfach Where Klausel, die sich nicht den kompletten Wert anschaut, sondern direkt ab dem ersten Punkt vergleicht, wird hier die komplette Tabelle abgefragt.
Wenn du das ganze noch weiteroptimieren willst, ohne da Hardwarepower hinten "reinzustecken", dann nur mit weiteren Bedingungen. (Also where Klauseln, z.B.: Nur bestimmtes Bundesland, nur bestimmte gefundene Menge, nur bestimmte Anfangsbuchstaben, usw). Quasi irgendeine Berechnung, die vorher schon eine Bedingung setzt, wobei die Berechnung viel weniger kompliziert sein darf, als deine Vergleichsfunktion.
Bsp:
where name like 'H%' and LevenshteinDistanz(Name,'Humburg')geht wesentlich schneller als
where LevenshteinDistanz(Name,'Humburg')
Liebe Grüße
|
426 ● 6 |
