SQL Abfrage mit priorisiertem Ergbenis

[Nevada208]

Hallo zusammen,

für einen Online-Shop möchte ich eine Suchfunktion erstellen die mir das Ergebnis mit einen bestimmten Priorität zurückgibt.

Beispiel Tabelle:

marke | Bezeichnung | Text

SAECO | SAECO Kaffeemaschine | Formschöne SAECO Kaffeemaschine mit Messbecher
SAECO | SAECO Entkalker | SAECO Entkalker für Kaffeemaschinen
Noname | Messbecher | Für Entkalker zur besseren Dosierung

Im Ergbnis möchte jetzt das die Sortierung wie folgt priorisiert ist:

- ist das Suchwort in Marke und Bezeichnung dann Prio 1
- ist das Suchwort in der Bezeichnung und im Text dann Prio 2
- ist das Suchwort in der Spalte Bezeichnung dann Prio 3
- ist das Suchwort nur im Text Prio 4

Wenn ich also nach SAECO Entkalker suche muss das Ergebnis so aussehen:

SAECO | SAECO Entkalker | SAECO Entkalker für Kaffeemaschinen
Noname | Messbecher | Für Entkalker zur besseren Dosierung

Wenn ich also nach Messbecher suche muss das Ergebnis so aussehen:

Noname | Messbecher | Für Entkalker zur besseren Dosierung
SAECO | SAECO Kaffeemaschine | Formschöne SAECO Kaffeemaschine mit Messbecher


Wenn ich also nach SAECO Messbecher suche muss das Ergebnis so aussehen:

SAECO | SAECO Kaffeemaschine | Formschöne SAECO Kaffeemaschine mit Messbecher
Noname | Messbecher | Für Entkalker zur besseren Dosierung


Im Ergebnis sollten auch die Prio-Stufen mit aufgelistet sein

Ich möchte es wenn es geht nur in MySQL machen, Gern aber auch andere Ideen. Bitte auch die Variante mehrerer Suchbegriffe
berücksichtigen.

Gruß
Nevada

-

[Christian Marquardt]

Ich möchte es wenn es geht nur in MS-SQL machen,

Warum ist die Frage dann in MySQL?

[Nevada208]

sorry meine MySQL

[defo]

für einen Online-Shop möchte ich eine Suchfunktion erstellen ..

Das ist eine brauchbare Beschreibung der Anforderung. Was hast Du denn schon erstellt?
Die Anforderung ließe sich erstmal in 2 Teile zerlegen,
der erste wäre das finden selbst,
der zweite die Sortierung.

Mit welchen Mitteln willst Du da dran gehen?
Wie groß ist der Datenbestand?

[Nevada208]

Hallo defo,

der Datenbestand sind derzeit ca. 15.000 Artikel. Wie ich dran gehe weiß ich noch nicht.
Ich möche noch eine zusätzliche Ähnlichkeitssuche mittels Levenshtein implementieren.

Zu Test habe ich die Felder Marke, Bezeichnung und Text zerlegt und in eine gesonderte Tabelle abgelegt:

aus

SAECO | SAECO Kaffeemaschine | Formschöne SAECO Kaffeemaschine mit Messbecher wird

id | artikel_nr | word | ranking

1 | 10001 | saeco | 1
2 | 10001 | Kaffeemaschine | 1
3 | 10001 | Formschöne | 4
4 | 10001 | saeco | 4
5 | 10001 | kaffeemaschine | 4
6 | 10001 | messbecher | 4

Wörter wie der, die, das usw. werden vorher entfernt.

Damit erhoffte ich mir eine schnellere Suche. Das Problem ist die Geschwindigkeit wenn ich die Daten sortiere.

select artikel_nr FROM words WHERE levenshtein('$this->q', word) BETWEEN 0 AND 5 limit 0,32

funktioniert sehr schnell.

Wenn ich aber das Ergbnis sortiert haben möchte:

select artikel_nr FROM words WHERE levenshtein('$this->q', word) BETWEEN 0 AND 5 order by ranking limit 0,32

warte ich ewig, aber das Ergebnis passt

Eventuell ist mein Ansatz falsch?

Gruß Nevada

[Ralf Jansen]

Nach kurzes googlen nach levenshtein und mysql scheint das eher keine eingebaute Funktion zu sein. Und die stored functions zum Thema sahen eher nicht nach ~schnell~ aus.
Hat MySql keinen Volltextindex? Wenn nicht vielleicht ein Volltextindex zusätzlich zur Datenbank selbst verwalten zum Beispiel mit Lucene.

[defo]

Wie ich dran gehe weiß ich noch nicht.
Ich möche noch eine zusätzliche Ähnlichkeitssuche mittels Levenshtein implementieren.

Wörter wie der, die, das usw. werden vorher entfernt.

Damit erhoffte ich mir eine schnellere Suche. Das Problem ist die Geschwindigkeit wenn ich die Daten sortiere.

select artikel_nr FROM words WHERE levenshtein('$this->q', word) BETWEEN 0 AND 5 limit 0,32

funktioniert sehr schnell.

Wenn ich aber das Ergbnis sortiert haben möchte:

select artikel_nr FROM words WHERE levenshtein('$this->q', word) BETWEEN 0 AND 5 order by ranking limit 0,32

warte ich ewig, aber das Ergebnis passt

Eventuell ist mein Ansatz falsch?

Der Ansatz ist gut! Levensthein ist ja schon fast Luxus.
Ich kenne mich nicht so gut mit mysql aus, aber da läuft irgendwas schief. Gedanke: Wenn 3 oder auch 300 Datensätze rauskommen, kann es nicht sehr lange dauern, die zu sortieren oder?
Also was macht die ranking order? Wieso produzierst Du kein Sortierkriterium, wie Du es selbst in der Anforderung definiert hast, oder warum sortierst Du nicht explizit nach LV Distanz?

Ich bin ein Depp, hab das "Ranking" Feld in der Wordtabelle nicht erkannt.
Das Ranking kann sich doch erst aus der Kombi ergeben oder?

[defo]

Also bevor ich das noch mal bearbeite:
Eine eigener Suchindex scheint mir jedenfalls effizienter als ein externer.
Die Umsetzung ist allerdings etwas eigenartig, da pro Artikel einige Wörter mehrfach auftauchen und das Ranking vordefiniert wird.
Das kann natürlich genutzt werden, damit ein Hersteller seine Suchbegriffe etwas pushed , aber darum geht's hier nicht oder?

Also nochmal, das eine ist das Finden (guter Ansatz mit Worttabelle)
das andere ist die Priorisierung, den Ansatz verstehe ich nicht.
Die Priorisierung ergibt sich m.E. erst im 2. Schritt, wenn man im Ergebnis auf den verschiedenen Feldern erneut abgleicht, wo das Suchwort und in welcher Kombi erscheint.
Da das Ergebnis relativ klein sein dürfte verglichen mit der Gesamtartikelliste darf / sollte man hier einfach die FindeFunktion je Feld erneut anwenden und die Treffer decodieren zur Prio und danach sortieren.

[Ralf Jansen]

Eine eigener Suchindex scheint mir jedenfalls effizienter als ein externer

Wenn die Funktionalität ausreicht Was leider oft genug nicht der Fall ist. Wie indexierst du zum Beispiel die Word Spalte so das die levenshtein Methode keinen FullScan auf die ganze Tabelle macht?
Ich sehe nicht wie eine klassische relationale DB mit klassischen Indexierungsmöglichkeiten da ~effizient~ sein soll. Da sind spezialisierte Volltexter besser aufgestellt. Insbesondere da man an das ~wie~ indexiert wird besser dran kommt als bei einer relationalen Datenbank. Dinge wie Suche nach ~Ähnlichkeit~ und ~Gewichtung~ bekommt man da fast geschenkt.

Aber ich war eh auf dem falschen Dampfer. Scheint ja das sortieren das Problem zu sein und nicht das Filtern bei der angedachten Datenmenge.

Edit: Vielleicht bin ich doch nicht auf dem falschen Dampfer Möglicherweise bricht durch das Limit die Abfrage nach entsprechend n Treffern ab und muss gar nicht für die ganze Tabelle die Levenshteindistanz berechnen. Durch das Order by aber doch weil ja erst ~gerankt~ und dann ~gelimited~ wird. Dann ist der levenshtein Algo das Problem. Gibts einen MySql Profiler?

[defo]

Wenn die Funktionalität ausreicht Was leider oft genug nicht der Fall ist. Wie indexierst du zum Beispiel die Word Spalte so das die levenshtein Methode keinen FullScan auf die ganze Tabelle macht?
Ich sehe nicht wie eine klassische relationale DB mit klassischen Indexierungsmöglichkeiten da ~effizient~ sein soll. Da sind spezialisierte Volltexter besser aufgestellt. Insbesondere da man an das ~wie~ indexiert wird besser dran kommt als bei einer relationalen Datenbank. Dinge wie Suche nach ~Ähnlichkeit~ und ~Gewichtung~ bekommt man da fast geschenkt.

Edit: Vielleicht bin ich doch nicht auf dem falschen Dampfer Möglicherweise bricht durch das Limit die Abfrage nach entsprechend n Treffern ab und muss gar nicht für die ganze Tabelle die Levenshteindistanz berechnen. Durch das Order by aber doch weil ja erst ~gerankt~ und dann ~gelimited~ wird. Dann ist der levenshtein Algo das Problem. Gibts einen MySql Profiler?

Also das Ranking ist ja kein rank Algo sondern einfach nur eine Spalte, die so benannt ist.
Nach dem ersten Post war ich von einem simplen Like ausgegangen und hab das auch immer noch im Kopf. Hier findet fast zwangsläufig ein Index keine Anwendung, wäre aber dennoch mit einem oder 2 Scans durch. Bei 15T Artikeln auch kein Problem. Das betrifft dann allerdings die kompletten Textfelder. Die würden in einer Indextabelle ja zu einer wesentlich größeren Tabelle.

Ein (externer) Indexer hat sicher seine Stärken, vor allem, wenn nicht zuviel Bewegung in den Daten ist. Ich würde erstmal versuchen, zu Fuß klarzukommen, ich bekäme vielleicht einiges geschenkt, aber u.U. Dinge, die ich nicht haben will.
Das Limit bzw. das Order zwingt im Fall oben das System vielleicht zu einem vollständigen Durchlauf, während unorderd einfach die ersten Treffer recht zügig reinkommen.

[Ralf Jansen]

Bei 15T Artikeln auch kein Problem

Der Algorithmus läuft nicht auf die Artikelnamen sondern auf eine Tabelle mit jedem Wort jedes Artikels/Artikelbeschreibung.
Wenn sein Beispiel representativ ist dann sind es eher 100.000 Rows. Dazu steigt die Komplexität von levenshtein auch noch mit der Länge des Suchworts (linear aber immerhin er steigt). Da wird es ohne Index knapp. Ein Gefühl von ~Instant~ bekommt man da in einem Webshop oder wofür das gedacht ist vermutlich eher nicht hin.

Um so länger ich drüber nachdenke um so ungeeigneter halte ich Levenshtein um schnell Ähnlichkeiten in einem Wortstamm zu finden. Denn ich kann die Komplexität schlecht oder besser gar nicht beim Anlegen des Artikels abfrühstücken sondern kann es nur bei der Suche machen (trage die Kosten also bei jeder Suche). Da wären Algorithmen die auf der Normalisierung von Wörtern basieren besser geeigneter (Stichwort "Steeming" wie bei einem Volltextindex). Das kann man beim einfügen erledigen und muß es nicht erst beim suchen tun sondern kann sich beim suchen auf die Suche nach Gleichheit beschränken und wäre damit ~schnell~.

[defo]

Ja, Du hast Recht. Normalisierung ist sicher nicht verkehrt. Steeming kenne ich nicht, also nicht als Verfahren in dem Bereich. Ich hatte aber nie den Eindruck, dass levenshtein sehr langsam ist. Klar langsamer als ein like sicher, ich würde aber auch nicht mit Distanz 5 arbeiten, 1 bis 2 reicht eigentlich schon für sehr blödsinnige Wörter.
Die Sache mit den 15T Datensätzen hatte ich ja auch schon so ähnlich geschrieben, die reine Wortliste wäre viel länger als die Anzahl der Ausgangsrecords, zumindest für eine gewisse Anzahl von Ausgangsrecords, irgendwann dürfte die Länge der Wortliste ja nahe konstant werden.

Nachtrag:
Hab grad mal ausprobiert.
Auf 1,8 Mio DS, gefiltert auf ca 10 %, LVD über 'Meierkowski' auf Namenfeld.
Distanz 1, kein Ergebnis
Distanz 2, kein Ergebnis
Distanz 3, 16 DS
Distanz 5, ca 250 DS
Erste Antwortzeit ca 1,6 Sekunden, danach schwankend zwischen 0,6 und 0,8.
Wahrscheinlich war alles nach dem ersten Select gecached. Die Spalte ist indiziert, ist hier vermutlich aber egal. (Die Filterung ebenfalls auf indizierter Spalte, ergibt einen Rangescan.) Ansonsten unoptimiert, taugt so nicht für online feeling, aber es wäre auch schon eine sehr große Wortliste. Ich würde sagen, da geht noch was.
Eine Änderung der Abfrage auf LVD <5 mit order by LVD, Suchfeld ändert -erwartungsgemäß- nichts an den Zeiten.