Relevanzsortierung bei Fulltext-Select

[Codehunter]

Moin!

Ich habe vor, Suchergebnisse von Artikelnamen sortiert nach Relevanz auszugeben. Hat jetzt nichts mit Delphi zu tun, diesmal PHP. Aber das Kernproblem liegt bei der Datenbankabfrage. In einer Tabelle liegen Artikeltexte (Namen, Beschreibungen, Keywords etc.). Auf einer Ajax-Webseite gibt es ein Suchfeld, welches interaktiv während der Eingabe von Suchbegriffen eine Vorschlagsliste als Dropdownmenü anzeigt und laufend bei Keypresses aktualisiert. Die Ausgabe dieser Suchvorschläge möchte ich relevanzsortieren, sodass die passendsten Ergebnisse immer oben stehen. Dazu habe ich mir folgende Query ausgedacht:

Code:

SELECT name
FROM products_description
WHERE language_id=2
  AND MATCH(name) AGAINST ('optiset standard' IN NATURAL LANGUAGE MODE)
ORDER BY MATCH (name) AGAINST ('optiset standard' IN NATURAL LANGUAGE MODE) DESC

Dabei kommt folgendes Ergebnis heraus (auszugsweise):

Code:

Optiset E Standard
Optiset E Standard
Optiset E Standard
Optiset E Standard
Optiset E Standard
Optiset E Standard Gehäuse
Optiset E Standard Bodenwanne
Optiset E Standard Tastengitter Wahl Made in Germany
Optiset E Standard Tasten 8er Made in Germany
Optiset E Standard Plusminus Tasten Made in Germany
Optiset E Standard/Advance Tasten
Optiset E Standard/Advance Display Unterschale
Optiset E Standard/Advance Display Unterschale
Optiset E Standard/Advance Display Oberschale
Optiset E Standard/Advance Funktionstasten 8er-Block
Optiset E Standard/Advance Funktionstasten 4er-Block
Optiset E Standard/Advance/Memory Tasten Lautstärke (Plus und Minus)
Optiset E Standard/Advance Navigationstasten
Optiset E Standard/Advance Display Oberschale
Optiset E Standard/Advance Display Unterschale

Soweit sieht das Suchergebnis auch gut aus, eigentlich wie ich es brauche. Der Suchbegriff war hier "optiset standard", voll ausgeschrieben. Da die Suchvorschläge aber interaktiv sind, baut sich der Suchbegriff auch erst sukzessive während der User-Eingabe auf. Wenn man einen unvollständigen Suchbegriff (z.B. "optiset stand") in die selbe Query wirft, kommt folgendes bei raus:

Code:

Optiset E Standard
Optiset E Entry
Optiset E Advance plus
Optiset E Memory
Optiset E Memory
Optiset E Entry
Optiset E Basic
Optiset E Basic
Optiset E Basic
Optiset E Basic
Optiset E Standard
Optiset E Standard
Optiset E Standard
Optiset E Standard
Optiset E Advance
Optiset E Advance
Optiset E Advance plus
Optiset E Advance plus
Optiset E Advance Conference
Optiset E Advance Conference
Optiset E Memory
Optiset E Memory
Optiset E Memory
Optiset E Key Module
Optiset E Key Module
Optiset E Key Module

Wie man sieht, ist dann die Relevanzsortierung beim Teufel. Nur wie kommt das und vorallem, wie stellt man das ab?

[Ghostwalker]

Probiers doch mal so:

Code:

SELECT name
FROM products_description
WHERE language_id=2
  AND (MATCH(name) AGAINST ('optiset' IN NATURAL LANGUAGE MODE)) AND (MATCH(name) AGAINST ('standard' IN NATURAL MODE))

ORDER BY (MATCH (name) AGAINST ('optiset' IN NATURAL LANGUAGE MODE)) DESC ,(MATCH(name) AGAINST ('standard' IN NATURAL LANGUAGE MODE)) DESC;

Ungetestet und von einem SQL-Laien. Aber vielleicht eine Idee für einen Ansatz :)

[Codehunter]

Ne du, so einfach ist der Drops nicht gelutscht :-D Genau genommen macht der "Natural Language Mode" schon genau das selbe: Slicen an den Leerzeichen, Bindestrichen etc. und dann AND-verknüpft matchen.

EDIT: Und bitte auf die genaue Problemstellung achten. Bei ganzen Wörtern scheint MATCH AGAINST gut klar zu kommen, bei nicht fertig geschriebenen Wortstücken jedoch fällt es komplett aus der Rolle. Um genau zu sein liefert MATCH in dem Fall für alle Treffer exakt den selben Relevanzwert, wie folgende Query zeigt:

Code:

SELECT name,
       MATCH(name) AGAINST ('optiset stand' IN NATURAL LANGUAGE MODE)
FROM products_description
WHERE language_id=2
  AND MATCH(name) AGAINST ('optiset stand' IN NATURAL LANGUAGE MODE)
ORDER BY MATCH (name) AGAINST ('optiset stand' IN NATURAL LANGUAGE MODE) DESC

Code:

Optiset E Standard   1.4053090810775757
Optiset E Entry   1.4053090810775757
Optiset E Advance plus   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Entry   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Advance   1.4053090810775757
Optiset E Advance   1.4053090810775757
Optiset E Advance plus   1.4053090810775757
Optiset E Advance plus   1.4053090810775757
Optiset E Advance Conference   1.4053090810775757
Optiset E Advance Conference   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Key Module   1.4053090810775757
Optiset E Key Module   1.4053090810775757

[nahpets]

Helfen die Dir weiter? Which SQL query is better, MATCH AGAINST or LIKE?

Bei unvollständiger Eingabe seitens des Nutzers eventuell sowas?

SQL-Code:

SELECT name
FROM products_description
WHERE language_id=2
  AND MATCH(name) AGAINST ('optiset stand*' IN NATURAL LANGUAGE MODE)
ORDER BY MATCH (name) AGAINST ('optiset stand*' IN NATURAL LANGUAGE MODE) DESC

[Codehunter]

Zitat:

Zitat von nahpets (Beitrag 1365058)

Bei unvollständiger Eingabe seitens des Nutzers eventuell sowas?

SQL-Code:

SELECT name
FROM products_description
WHERE language_id=2
  AND MATCH(name) AGAINST ('optiset stand*' IN NATURAL LANGUAGE MODE)
ORDER BY MATCH (name) AGAINST ('optiset stand*' IN NATURAL LANGUAGE MODE) DESC

Leider nein, das Ergebnis bleibt exakt identisch zum vorherigen:

Code:

Optiset E Standard   1.4053090810775757
Optiset E Entry   1.4053090810775757
Optiset E Advance plus   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Entry   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Basic   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Standard   1.4053090810775757
Optiset E Advance   1.4053090810775757
Optiset E Advance   1.4053090810775757
Optiset E Advance plus   1.4053090810775757
Optiset E Advance plus   1.4053090810775757
Optiset E Advance Conference   1.4053090810775757
Optiset E Advance Conference   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Memory   1.4053090810775757
Optiset E Key Module   1.4053090810775757
Optiset E Key Module   1.4053090810775757

EDIT: Du hast mich aber auf eine Idee gebracht:

Code:

SELECT name,
       MATCH(name) AGAINST ('+optiset +stand*' IN BOOLEAN MODE)
FROM products_description
WHERE language_id=2
  AND MATCH(name) AGAINST ('+optiset +stand*' IN BOOLEAN MODE)
ORDER BY MATCH (name) AGAINST ('+optiset +stand*' IN BOOLEAN MODE) DESC

ergibt:

Code:

Optiset E Standard   4.073927879333496
Optiset E Standard   4.073927879333496
Optiset E Standard   4.073927879333496
Optiset E Standard   4.073927879333496
Optiset E Standard   4.073927879333496
Optiset E Standard Gehäuse   4.073927879333496
Optiset E Standard Bodenwanne   4.073927879333496
Optiset E Standard Tastengitter Wahl Made in Germany   4.073927879333496
Optiset E Standard Tasten 8er Made in Germany   4.073927879333496
Optiset E Standard Plusminus Tasten Made in Germany   4.073927879333496
Optiset E Standard/Advance Tasten   4.073927879333496
Optiset E Standard/Advance Display Unterschale   4.073927879333496
Optiset E Standard/Advance Display Unterschale   4.073927879333496
Optiset E Standard/Advance Display Oberschale   4.073927879333496
Optiset E Standard/Advance Funktionstasten 8er-Block   4.073927879333496
Optiset E Standard/Advance Funktionstasten 4er-Block   4.073927879333496
Optiset E Standard/Advance/Memory Tasten Lautstärke (Plus und Minus)   4.073927879333496
Optiset E Standard/Advance Navigationstasten   4.073927879333496
Optiset E Standard/Advance Display Oberschale   4.073927879333496
Optiset E Standard/Advance Display Unterschale   4.073927879333496
Optiset E Standard/Advance Satz Tasten und Lichtleiter   4.073927879333496
Optiset E Standard   4.073927879333496

Sieht schon mal viel besser aus! Warum jetzt aber der Relevanzwert trotzdem bei allen identisch ist, obwohl das ORDER BY ganz offensichtlich anderes vermuten lässt, das erschließt sich mir jetzt auch nicht.

BTW: Wie hast du hier eigentlich das SQL-Syntax-Highlight gemacht? Das findet sich in meiner Editor-Toolbar gar nicht...

[nahpets]

code="sql" in eckigen Klammern.

[Codehunter]

Zitat:

Zitat von nahpets (Beitrag 1365066)

code="sql" in eckigen Klammern.

Ah, ein Osterei! Das trifft sich ja gut, ist bald wieder Ostern ;-) Spaß beiseite, ist das irgendwo dokumentiert, welche Highlighter ansprechbar sind?

[nahpets]

Ostern ist hier genauer definiert: BBCode ;-)

Allerdings steht dort nicht genauer erläutert, was man bei Code noch so alles hinter das = schreiben kann. #Code

[jobo]

Ich find das ja etwas drollig. Hab mich noch nie mit diesen SQL Funktionen rumgeschlagen. Es erklärt im Grunde aber die besch.. Ausgabe in gefühlt jedem 1. Webshop mit sortierung nach "Relevanz"

Der erste wichtige Schritt ist naheliegend und bereits geschehen:
Bei unerklärlichen Sortierungen in der Ausgabe, das Sortierfeld mit ausgeben. Verblüffendes Ergebnis, naja nicht wirklich.

So wie es aussieht, kommt man recht bald zu der Erkenntnis, das Relevanz offenbar recht unterschiedlich bewertet wird.
Also Sortierkriterium selbst festlegen. Ich nehm bei sowas gern Levenshtein oder so, keine Ahnung ob es hier hilft, aber wäre mein Ansatz.

Im Übrigen wäre meine Frage auch bei dem Punkt "vollständige Eingabe" mal bitte zu erläutern, was das denn bitte sein soll?
Wann weiß ein Entwickler oder ein Stück Code, wann mein Suchbegriff vollständig ist?

[p80286]

:gruebel:
Da ich diese Funktion noch nie genutzt habe mal spekuliert
"Optiset" ist klar, muß man nicht diskutieren.
dann kommt in der DB ein "E" nach dem aber nicht gefragt wird, und schon passt die ganze Chose nicht mehr, der Rest ist nur noch geraten?

Interessant wären die nicht selektierten Daten.
Gibt es darunter "Optiset"?

Gruß
K-H

[nahpets]

Zitat:

Zitat von jobo (Beitrag 1365081)

Im Übrigen wäre meine Frage auch bei dem Punkt "vollständige Eingabe" mal bitte zu erläutern, was das denn bitte sein soll?
Wann weiß ein Entwickler oder ein Stück Code, wann mein Suchbegriff vollständig ist?

Nie, aber er soll entscheiden, wie bei vollständiger bzw. unvollständiger Eingabe zu verfahren ist.
Dabei muss er noch anwenderabhängig entscheiden, was vollständig bzw. unvollständig ist.

Und Relevanz ist immer das, was der Anwender gerade als besonders wichtig erachtet.

Naja, Sortierung immer nach dem, was ich in Order By eingebe, nie nach irgendwas, was irgendwie in der Datenbank implementiert ist. Das ist immer ein bisserl wie Lotto.

Relevanz ist subjektiv. Eine objektive Sortierung nach subjektiven Kriterien erscheint mir nicht wirklich möglich.

Das ist wie bei der Suche mit Google und Co.

Die suchen immer nach dem, was sie meinen, was der Anwender gemeint haben könnte. So gut wie nie einfach nur nach dem, was man eingegeben hat. Und wenn man da mehrere Suchbegriffe mit und verknüpft haben möchte, dann machen die halt doch ein oder. Und auch nicht zwingend mit allen Suchbegriffen, sondern nur mit denen, von denen sie meinen, das sie relevant sein könnten.
Entsprechend schwierig ist es, effektiv nach bestimmten Begriffen / Begriffskombinationen zu suchen und nur die für einen persönlich relevanten Ergebnisse zu bekommen.

Zum obigen Beispiel:

Der Relevanzwert 4.073927879333496 bezieht sich wohl bei allen Zeilen der Ergebnismenge auf den Anteil dessen, der dem Suchbegriff entspricht. Bei allen ist "Optiset E Stand" identisch und resultiert wohl aus "+optiset +stand*". Diese beiden Werte kommen überall vor und damit sind sie gleich relevant. Von daher kann sich der Wert nicht unterscheiden. Woher sollte die Datenbank denn wissen, welche der auf "Optiset E Stand" folgenden Zeichenfolgen in der Ergebnismenge für den Anwender wichtiger sein könnten. Dazu müsste sie mehr Information über die Bedeutung des Datenbankinhaltes haben, also über Wissen verfügen.

Hier wäre, wenn man da eine weitere Sortierung haben will, eine Ergänzung des Order By zwingend erforderlich.

Also z. B.

SQL-Code:

SELECT name,
       MATCH(name) AGAINST ('+optiset +stand*' IN BOOLEAN MODE)
FROM products_description
WHERE language_id=2
  AND MATCH(name) AGAINST ('+optiset +stand*' IN BOOLEAN MODE)
ORDER BY MATCH (name) AGAINST ('+optiset +stand*' IN BOOLEAN MODE) DESC, Name, levenshtein(name, 'optiset stand');

Wobei mir bei einer unvollständigen Eingabe, wie in diesem Beispiel, die Levenshtein-Distanz nicht wirklich sinnvoll erscheint.

(Die Levenshtein-Distanz in MySQL)

Oder die Tabelle müsste eine Relevanzspalte enthalten, in der vom Nutzer ein Wert für die Relevanz hinterlegt wird. Gleicher Wert = gleiche Relevanz. Kleinerer Wert = kleinere Relevanz. Diese Spalte muss dann mit ins Order By ... Relevanzspalte desc.

[Codehunter]

Über das Thema Relevanz sind ja schon ganze Dissertationen verfasst worden, ohne dem Problem wirklich näher zu kommen. Da spielt so viel mit rein. Von Kulturkreis bis was der Suchende gefrühstückt hat. Google verwendet Unsummen auf seinen Algorithmus, KI und ähnliches, ist auch schon ziemlich gut (im technischen Sinne) geworden.

Wobei man da ja Äpfel und Birnen vergleicht, denn Google muss die Inhalte unterschiedlicher Webseiten vergleichen und ranken, was zum Konfliktfeld SEO führt. Ich bewege mich aber innerhalb einer Datenbank auf einer Webseite und habe zudem noch halbwegs semantisch ordentliche Daten.

Im vorliegenden Fall wäre Relevanz recht einfach zu definieren: Ein möglichst großer Anteil dessen was der Suchende eingegeben hat im Feld "name" und ein möglichst kleiner Differenzanteil, also was in name vorhanden aber nicht im Suchbegriff angegeben ist. Entsprechend sollte das Ranking sein.

Im übrigen funktioniert die Boolesche MATCH-Methode genau so lange gut, bis der User Zahlen eingibt. Genauer gesagt, alphanumerische Zeichenfolgen und reine Zahlenfolgen, durch Leerzeichen getrennt. Dann kommt der Algorithmus wieder ins Schleudern und liefert nur Nonsens.

Zitat:

Zitat von p80286 (Beitrag 1365104)

Interessant wären die nicht selektierten Daten.
Gibt es darunter "Optiset"?

Ich habe das nur der Übersichtlichkeit halber gekürzt. Alle Suchergebnisse BEGINNEN mit "Optiset", es werden jedoch keine Datensätze gefunden, wo "Optiset" an einer anderen Stelle im Text (also nicht am Beginn des Strings) vorkommt.

Zitat:

Zitat von nahpets (Beitrag 1365106)

Der Relevanzwert 4.073927879333496 bezieht sich wohl bei allen Zeilen der Ergebnismenge auf den Anteil dessen, der dem Suchbegriff entspricht. Bei allen ist "Optiset E Stand" identisch und resultiert wohl aus "+optiset +stand*". Diese beiden Werte kommen überall vor und damit sind sie gleich relevant. Von daher kann sich der Wert nicht unterscheiden.

Eben genau das ist im NATURAL LANGUAGE MODE ja nicht der Fall. Da wurden auch Datensätze gefunden, in denen nur einer der beiden Suchbegriffe, nämlich "Optiset" vorkommt, nicht jedoch das zweite Wort(fragment) "stand". Obendrein wurden solche "Teiltreffer" dann sogar noch höher gerankt. Bzw. eigentlich war gar kein sinnvolles Ranking-Schema zu erkennen.

Mit der Levenshtein-Distanz hätte ich insofern ein Problem, als dass es sich um eine MariaDB und nicht MySQL handelt, weshalb das besagte Modul nicht (binär-)kompatibel ist und obendrein der ganze Brassel auch noch auf Windows läuft. Bliebe hier nur die Implementation in einer Mysql-Funktion, was performancetechnisch, sagen wir mal, zweifelhaft ist.

Zitat:

Zitat von jobo (Beitrag 1365081)

Es erklärt im Grunde aber die besch.. Ausgabe in gefühlt jedem 1. Webshop mit sortierung nach "Relevanz"

Da stimme ich 100%ig zu. Denn wenn man zu der Fragestellung recherchiert, findet man eigentlich nur zwei Varianten, das mit MySQL/MariaDB zu realisieren: Entweder durch einfache "feld LIKE '%wort_aus_suchbegriff%' AND feld LIKE '%anderes_wort_aus_suchbegriff%'" oder eben die Variante MATCH AGAINST. In meinem Fall habe ich mit der LIKE-AND-Methode bessere Ergebnisse, wobei BESSER nicht bedeutet GUT, sondern nur WENIGER SCHLECHT. Außerdem ist dann zwar die Gesamt-Ergebnismenge passend, ein sinnvolles Ranking habe ich dann aber immer noch nicht - was der eigentliche Grund für meine Experimente mit MATCH-AGAINST war.

[Ghostwalker]

So...noch mal der SQL-Laie :)

Ich weiß nicht in wie weit dir das weiterhilft, aber vielleicht ists ja ein Denkanstoß :)

In meiner letzten Firma standen wir auch häufiger vor diesem Problem, weshalb unser CTO und einige Kollegen mit Elasticsearch und MongoDB experimentiert haben. Es ging hier aber um eine strategische Entscheidung, auf welches System man bei zukünfigen Projekten setzten sollte.

Man hat sich, auf Grund der Tests, letztlich für genau diese Kombi entschieden, da die Datenmengen
ja auch nicht kleiner werden :)


Für die bestehende Kombi würd ich so vorgehen:

- DB-Abfrage, die ALLE Datensätze, die relevant sein könnten, zurückliefert
- Die dann via PHP bewerten und sortieren.

Bei einem Ähnlichen Problem, hab ich es geschaft, das nicht mal der Serveradmin meckerte, wg. der Last auf den Servern :mrgreen:

[p80286]

Zitat:

Zitat von Codehunter (Beitrag 1365211)

Entweder durch einfache "feld LIKE '%wort_aus_suchbegriff%' AND feld LIKE '%anderes_wort_aus_suchbegriff%'" oder eben die Variante MATCH AGAINST.

Ich habe den Eindruck, daß das MATCH AGAINST nach dem Schema

SQL-Code:

"feld LIKE 'wort_aus_suchbegriff%'

arbeitet, da ja wie Du schreibst keine Datensätze selektiert werden in denen "Optiset" irgendwo im Feld steht.

Gruß
K-H

[jobo]

Zitat:

Zitat von nahpets (Beitrag 1365106)

..
Woher sollte die Datenbank denn wissen, welche der auf "Optiset E Stand" folgenden Zeichenfolgen in der Ergebnismenge für den Anwender wichtiger sein könnten
..

Genau, das so glorreich als Relevanz zu bezeichnen halte ich für "mutig".
Türlich kann die DB das nicht wissen, die blättert nur nach Anweisung in ihren Daten. Wenn der "Relevanz"-Wert einfach über die Existenz eines Teilwortes bestimmt wird, muss man halt selbst nachjustieren. Levenshtein habe ich mal so in den Raum geworfen, weil es recht einfach eine schöne Fuzzynes erlaubt. Ich würde es allerdings nicht ohne Weiteres auf so "riesige" Texte anwenden, sondern auf (einzelne) Worte.
Ich hab jetzt nicht viel Hirnschmalz in meine vorige Antwort gesteckt, vor Levenshtein könnte man bspw. noch eher die identische Relevanz gewichten, indem man sie mit der Length des Feldwertes multipliziert (oder dem Kehrwert, je nach Order by Richtung).
Damit würde man zum Ausdruck bringen, dass bei gleicher Relevanz die Werte besser sind, wo der Suchbegriff einem größeren Teil des Feldwertes entspricht. (Oder, damit es nicht zu "Überblendung" kommt, wäre die Wortlänge ein separates, nachgelagertes Sortierkriterium, dass dadurch wirklich nur im Fall "identische Relevanz" greift.

Wenn das nicht reicht, dann halt wortweise Levenshtein Distanz.
Usw. usf.