Machbarkeitsstudie: Forensuche

Anything regarding research, researchers, newest research results and personal tinkering.

German Machbarkeitsstudie: Forensuche

  •  
Avatar: Seiji
VIP
Thread Creator#1

Nach einigen Tagen und Nächten in denen ich eine meiner virtuellen Maschinen mit Tests gequält habe bin ich froh nun endlich die Zeit gefunden zu haben das Folgende zu verfassen:

Alle halbe Jahr wieder - die Prüfungen stehen an und ich brauche eine Alternativbeschäftigung.
Da traf sich dieser Feature-Request ganz gut.

Da ich ab und zu dann aber doch mal in die Prüfungsunterlagen sehen musste hab ich mich hauptsächlich mit Suchen unter möglichst geringem Aufwand beschäftigt. Das erschien mir am sinnvollsten, da auch Vendel vermutlich weniger Zeit für die Implementierung aufwenden möchte. Meine Vorgehensweise ist natürlich alles außer perfekt, doch wir (zumindest ich) sind ja hier um zu lernen. Sollte mir irgendwo ein Fehler unterlaufen sein, oder irgendjemand Vorschläge für Verbesserungen haben - ab in die Kommentare.

Vorweg ein paar Bemerkungen:
Der Titel Machbarkeitsstudie ist vermutlich etwas ungünstig gewählt. Die Frage der Machbarkeit ist mit einem klaren "ja" beantwortbar. Womit ich mich hauptsächlich beschäftigt habe ist: zu welchem Preis.
Da ich mit der aniSearch-Datenbank nicht betraut bin behandle ich im Folgenden nur die Suche im Titel von Threads.
(Einträge werden als HTML erstellt, ich weiß an dieser Stelle aber nicht wie genau diese gespeichert werden - Zumindest eine Art Validator muss es geben, da mein mühevoll von Hand gesetzter border-radius in manchen Posts immer von Zauberhand verschwindet )

Alle Verfahren, die ich behandeln möchte basieren auf dem MySQL FULLTEXT Index. Da wir den armen Server nicht überlasten wollen und Vendel vorbildlich auf sein Schätzchen Acht gibt habe ich mich zunächst mit dem Verhalten dieses Index beschäftigt um abwägen zu können, ob dessen Verwendung überhaupt sinnvoll ist:

Achtung! Der Support für FULLTEXT-Suchen ist auf die Verwendung der Storage-Engine MyISAM (bis MySQL 5.5) beschränkt. Ab MySQL 5.6.4 wird die Suche auch auf InnoDB-Tabellen unterstützt.
Beim Support in MariaDB bin ich mir nicht ganz sicher (in meiner Version funktionert es aber)
(Ich gehe mal davon aus, dass aniSearch InnoDB verwendet - da MyISAM bekanntlicherweiße keine Fremdschlüssel kennt)

Technische Daten meiner Testumgebung:

Ich bin mir natürlich im Klaren darüber, dass eine VM für Performancetests eher ungeeignet ist - aufgrund von schwankenden Faktoren (a.k.a. andere VMs auf dem Host), da ich allerdings weniger Performance als Speicherplatz und Effizienz-Tests (Query-Effizienz) durchgeführt habe, ist das akzeptabel.
Hardware:

Hypervisor: VMWare (Version leider unbekannt - da kein von mir zugängliches System)
CPU: (2 Kerne eines) AMD Opteron 6386 SE @ 2.80 GHz
RAM: 2,00 GB


Software:

Betriebssystem: Windows 7 Professional SP1 (32 bit)
(hätte ich die Möglichkeit dazu gehabt - hätte ich diese Tests natürlich auf einem richtigen Betriebssystem durchgeführt)

Datenbank: MariaDB - 10.0.14 [gezwungenermaßen im TCP Betrieb]
(Storage-Engine = InnoDB; Collation = utf8_general_ci)

Post was last edited on 16.10.2015 13:53.
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
Avatar: Seiji
VIP
Thread Creator#2
Benötigter Speicherplatz

Was dieses Thema anbelangt habe ich mich für die Holzhackermethode entschieden:

Eine kurze Suche nach "Word Database" brachte mich zu der umfangreichen WordNet Datenbank aus Amerika (ausschließlich englische Wörter). Obwohl die Datenbank die Typen der einzelnen Wörter enhält habe ich mich dazu entschieden diese außen vor zu lassen (auf Grund der begrenzten Zeit). Die Wortdatenbank habe ich auf das geringste reduziert, sodass ich im Folgenden mit dieser Aufstellung arbeite:

Die Tabelle words enthält die aufs Minimum reduzierte WortNet Datenbank (lediglich das Wort selbst und einen Surrogate Key).

Die Tabelle sentences enthält die durch das unten angesprochene Tool generierten Sätze, für die ein FULLTEXT Index aufgebaut wird.

Ein kleines Tool, das ich schnell programmiert habe nimmt die gewünschte Anzahl an Sätzen, sowie die maximale Anzahl an Wörtern pro Satz entgegen - um mithilfe der Wortdatenbank n Sätze mit zufälliger Länge aus zufälligen Wörtern der words Tabelle zu generieren und in der Tabelle sentences abzulegen.
Die Sätze, welche das Tool erzeugt sehen z.B. so aus:
Natürlich machen sie nicht viel Sinn - da Worttyp und Satzaufbau nicht beachtet werden.

reinforced concrete Latino sine flexione EBV peseta Sophist haymaker orchard
machine-displayable text span deliriously persona grata
bulginess Araucaria heterophylla roach

Der gehärtete Beton Latino ist natürlich super aber mein persönlicher Favorit ist:
sexual volleyball game (und jetzt nochmal mit der Stimme von Duke Nukem )

Butter bei die Fische:
Die Statistiken der Tabelle sentences mit und ohne FULLTEXT Index:

1.000.000 zufällige Sätze @ 1-10 Wörter
Aus einem Wortschatz von 202778 Wörtern
Die Tabelle wurde zuerst ohne jeglichen Index befüllt (=> [0]), danach wurde der FULLTEXT Index erstellt (=> [1]).

### NO INDEX ### [0]
data_length: 93962240
avg_row_length: 94
index_length: 0
free: 6291456
==> 87670784 (~ 83,61 MiB)
### WITH FULLTEXT ### [1]
data_length: 102367232
avg_row_length: 102
index_length: 20512768
free: 0
==> 122880000 (~ 117,18 MiB)

Hinweis: Die avg_row_length steigt AFAIK, da der FULLTEXT-Index Daten zur bestehenden Tabelle Daten hinzufügt (invisible columns).

Erkenntnis: Die Tabelle ist um ca. 33,57 MiB in der Größe gewachsen, das entspricht einer Steigerung des Speicherverbrauchs um etwa 40,2%. Da es sich hier allerdings um eine Tabelle handelt in der ausschließlich eine Spalte mit Sätzen enthalten ist, beschreibt der prozentuale Anstieg nur den zu erwartenden Anstieg der Titel-Spalte in der aniSearch Datenbank.
In dieser Statistik fällt zudem noch der Faktor Stopwords (weiter unten) unter den Tisch - der wahrscheinlich für einen kleineren Index sorgen würde.
Der Speicherverbrauch sollte sich also im Rahmen des verträglichen bewegen.

Einen FULLTEXT-Index für die Posts ansich würde ich allerdings nicht erstellen, da diese wahrscheinlich auch im HTML-Format in der Datenbank liegen (?) gestaltet sich die Suche dort womöglich ohnehin eher schwer. Sollte ein Post im BBCode in der Datenbank liegen könnte ich mir allerdings einen kleinen Umweg über Stopwords (weiter unten) vorstellen.

Nach einem bisschen Einlesen in die grobe Funktionsweiße des FULLTEXT-Index hatte ich die Vermutung, dass eine Verkleinerung des zur Verfügung stehenden Wortschatzes eventuell eine Auswirkung auf die spätere Größe des Indexes haben könnte.
Sehr schwer nachzuweisen, da ich bei der Halbierung des Wortschatzes einfach die obere Hälfte abschneide. Das Ergebnis hängt also von der Normalverteilung der Wortlänge in der unteren Hälfte - verglichen mit der in der oberen Hälfte ab.
(Wären die Worte in der unteren Hälfte beispielsweise alle im Schnitt 5 Zeichen lang und die in der oberen Hälfte im Schnitt 8, so hätte ich schon "per Design" einen kleineren Speicherbedarf - wenn nur die untere Hälfte genutzt wird)


Trotzdem hier der nächste Test mit halbem Wortschatz:
Die Statistiken der Tabelle sentences2 mit und ohne FULLTEXT Index:

1.000.000 zufällige Sätze @ 1-10 Wörter
Aus einem Wortschatz von 10389 Wörtern


### NO INDEX ###
data_length: 95027200
avg_row_length: 94
index_length: 0
free: 5242880
==> 89784320 (~ 85,63 MiB)
### WITH FULLTEXT ###
data_length: 103415808
avg_row_length: 103
index_length: 20512768
free: 0
==> 123928576 (~ 118,19 MiB)

Meine Vermutung hat sich leider nicht bewahrheitet: Auch bei halbem Wortschatz bleibt die Index-Länge gleich. Die avg_row_length ist zwar ebenfalls gleich der in sentences, doch die letztendliche Größe der Tabelle ist um 2 MiB größer. Die Wörter in der ersten Hälfte von words scheinen also aufs Mittel gesehen etwas größer zu sein.



Fazit:
Der Speicherverbrauch sollte im Rahmen des Verträglichen liegen, vorausgesetzt man setzt nur eine Suche in den Thread-Titeln um. Die Anzahl der Thread-Titel ist um einiges kleiner als die Anzahl der Posts, daher sollte der anfallende Speicherbedarf für den FULLTEXT-Index nahezu unspürbar bleiben. Das große WoH Board hat beispielsweiße erst 158.726 Themen, deren Titel vermutlich um einiges schmäler ausfallen als die, mit denen ich getestet habe. Der Speicherbedarf ist unabhängig vom verwendeten Vokabular in den Titeln.
Post was last edited on 30.12.2014 10:06.
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
Avatar: Seiji
VIP
Thread Creator#3
Techniken und deren Suchperformance

Im Folgenden möchte ich mich mit der Volltext-Suche ansich beschäftigen.
Grundlegend stellt SQL mehrere Möglichkeiten der Suche zur Verfügung:

Natural Language Search:
Die Natural Language Search durchsucht die Datenbank mit einem gewissen Spielraum in Form von verbalem Interpretierungsfreiraum.

Die Varianzen zwischen gleichklindenen Wörtern wird zu unterdrücken versucht. Zum Beispiel:
[Aus den Daten von den Tests zum Speicherverbrauch]

BesonderheitQuerySuchergebnis
Doppelkonsonantentippsytipsy
s und ztipzytipsy
y und itipsitipsy
Wortzusammensetzungenillill-humored / ill-equipped

Die Ergebnisse sind nicht zu 100% gleich, aber der Interpretationsfreiraum wird ziemlich gut ausgeglichen.

SQL:
SELECT * FROM sentences WHERE MATCH(text) AGAINST('yummy cake')
Dieser Query berechnet die Relevance (einen Wert, der angibt wie genau der Suchtext mit dem zu vergleichenden Text in der Datenbank überein stimmt), lässt alle Rows mit der Relevance 0 wegfallen und sortiert die übrig bleibenden nach absteigender Relevance.
(Der Query wird automatisch sortiert, da das Matching in der WHERE-Clause steht)

Um den Relevance-Wert auszulesen (z.B. zum Testen oder um ihn im Ergebnis anzuzeigen) kann man ihn mit dem folgenden SQL mit ausgeben lassen:
SELECT text, MATCH(text) AGAINST('yummy cake') AS relevance FROM sentences WHERE MATCH(text) AGAINST('yummy cake')
(Auch wenn das MATCH AGAINST zweimal im Query steht erzeugt dieser Befehl nicht viel mehr Overhead als der obere. Da es sich um 2 identische Matches handelt wird nur ein MATCH AGAINST berechnet)

Boolean Search Mode:
Der Boolean Mode ist eine Erweiterung der Natural Language Search.

Achtung! Beim Testen ist mir zufällig aufgefallen, dass der Boolean Mode mit MyISAM anders arbeitet als mit InnoDB (auf einer MariaDB). Wie sich InnoDB auf MySQL (ab V5.6.x) verhält habe ich nicht getestet.

Er erlaubt das benutzen von Modifiern im Suchstring, wie zum Beispiel (Es gibt noch einige mehr):
(Bei InnoDB gibt es ein paar Dinge zu beachten: Referenz)

ModifierEffektBeispielResult-Example
+Wort muss enthalten sein+linuxAuf Servern läuft meist: Linux
-Wort darf nicht enthalten sein-windowsAntivirus für Windows installieren
*Wort muss so anfangenpoliti*Politik / Politiker / politisch

Da es bei der Verwendung dieser Modifier zu Syntax-Fehlern beim Query kommen kann ist deren Verwendung zwar (bei validem Query) einfach super für erfahrenere Benutzer, der User spielt dann allerdings den wichtigsten Faktor. Sucht ein Nutzer beispielsweiße nach einem Text der ein "+" enthält wird es trotzdem als Modifier interpretiert. Ein Beispiel dafür:
Kaffee + Kuchen
Das Ergebnis muss Kuchen enthalten und kann Kaffee beinhalten.

Bei der Verwendung von + und - ist (Mutmaßung - ohne jeglichen Beweiß!) eventuell eine Geschwindigkeits-Steigerung zu beobachten, da Rows sofort als unpassend parkiert werden können ohne weitere Berechnungen auszuführen, sollten Wörter vor bzw. nicht vorkommen die ausdrücklich ausgeschlossen oder erwünscht wurden.

SQL:
Um ein Query im Boolean-Mode durchzuführen fügt man lediglich ein IN BOOLEAN MODE am Ende des Suchstrings im ASSIGN() an:
SELECT * FROM sentences WHERE MATCH(text) AGAINST('yummy cake' IN BOOLEAN MODE)

Hinweis: Das Natural Query ignoriert Modifier im Suchstring (keine Auswirkung auf das Ergebnis), da die Zeichen der Modifier (+ / - / ...) zumeist eh als Delimiter-Zeichen gesehen werden.

Search with Query Expansion:
Die Query Expansion ist ein Verfahren um Synonymen bei der Suche Herr zu werden, deswegen lässt sich dieses Verfahren nur mit sinnvollen Test-Daten untersuchen.

Da ich zufälligerweise die Gelegenheit dazu hatte das mit Produktiv-Daten zu testen kann ich sagen, dass die Ergebnisse doch erstaunlich gut sind (Vorausgesetzt ist eine gute Stopword-Liste!) und nahezu an die Suchergebnisse mit von Hand eingetragenen Synonymen heranreicht.

Da die Suche allerdings mehrere Durchläufe ausführt (laut Dokumentation 2) um ihr Ziel zu erreichen ist ihre Verwendung "durstiger" als die der Anderen. Die Ergebnisse allerdings bei korrektem Setup unschlagbar.

SQL:
SELECT * FROM sentences WHERE MATCH(text) AGAINST('yummy cake' WITH QUERY EXPANSION)

Diese unterschiedlichen Möglichkeiten der Suche lassen sich natürlich beliebig kombinieren. Verwendet man allerdings im selben Query zwei unterschiedliche Suchmethoden werden beide einzeln berechnet, sie sind nicht voneinander ableitbar.

Fazit:
Ohne die Verwendung von Modifiern dürften sich Default Mode (Natural Language) und Boolean Mode Geschwindigkeitstechnisch nicht viel geben. (Boolean könnte etwas schneller sein, da er ein paar Dinge per Design ignoriert, siehe: Referenz)
Obwohl die zusätzliche Funktionalität des Boolean Mode usability-technisch durchaus Spaß machen kann, wird sie für Normalnutzer vermutlich hauptsächlich Kopfschmerzen bereiten.
Sollten die Suchergebnisse im Natural Language Mode keine allzu guten Ergebnisse liefern, lohnt sich sicherlich mal ein Blick auf die Query Expansions. Bei den (aktuell - 02.01.2015) rund 5500 Foreneinträgen und damit 5500 zu durchsuchenden Titeln dürfte der Unterschied (noch) nicht spürbar sein.
Post was last edited on 01.01.2015 22:07.
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
Avatar: Seiji
VIP
Thread Creator#4
Suchergebnis-Optimierung

Die Ergebnisse für die Suchen lassen sich durch ein paar Maßnahmen optimieren:

Achtung! Alle dieser Änderungen müssen durchgeführt werden, bevor der FULLTEXT-Index angelegt wird, da diese den Index beeinflussen!

- Beim Suchen in viel Text ist eine gute Stopwords-Liste sehr vorteilhaft. Im Fall von aniSearch müssten in dieser Stopwords-Liste dann alle verfügbaren Sprachen vertreten sein, sonst ist die Suche für eine Sprache optimiert und bei den anderen kommt viel Mist.
Ein paar Stopwords-Listen gibt es hier:

aniSearch's Haupt-Sprachen und sehr umfangreich:
http://www.webpageanalyse.com/blog/lists-of-stop-words-in-9-languages

Viele Sprachen:
http://www.ranks.nl/stopwords/

Stopwords-HowTo:
Abhängig von der verwendete Datenbank / Version und Storage-Engine kann die Stopwords-Liste in eine Datenbank-Tabelle(InnoDB) oder in einer Text-Datei abgelegt werden.

In der Server-Einstellung:
innodb_ft_server_stopword_table  wird der qualifizierende Name der Tabelle angegeben, in der sich die zu benutzende Liste befindet.

oder:
ft_stopword_file wird der Pfad zu einer Text-Datei angegeben in der die zu verwendenden Stopwords stehen.


- Die maximale / minimale Wort-Länge kann einen großen Unterschied machen. Wird z.B. nach Kürzeln für Anime's gesucht (SAO z.B.) könnte es sein, dass diese ignoriert werden.

Max/Min-Token-Größe HowTo:
In der Server-Einstellung:

innodb_ft_min_token_size wird die minimale Länge für zu beachtende Wörter angegeben

innodb_ft_max_token_size wird die maximale Länge für zu beachtende Wörter angegeben
Post was last edited on 16.01.2015 11:51.
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
    • ×0
  •