# Suchoptimierung

Die Daten mit denen gearbeitet werden soll werden in zwei Datenbanken gespeichert, wovon später
hauptsächlich nur noch eine genutzt wird. Diesen Fakt können wir aber gekonnt ignorieren. Zu
Testzwecken wird eine um eine deutlich vielfach größere Datenbank erzeugt, auf dem die Algorithmen
getestet werden. Alle Test erfolgen auf dem gleichen Endgerät unter ähnlichen Bedingungen. Bei der
Optimierung geht es weniger darum das komplette Ergebnis ein paar Millisekunden eher zu erhalten,
sondern um signifikante Proportionen (z.B. 20% schneller).

Die erzeugte Datenbank sieht ungefähr so aus:

| Kategorie | Erzeugte Datenbank | Erwartete Realwerte | Kommentar |
|-|-|-|-|
| Anzahl von Interviews | 1000 | ca. 10-15 ||
| Anzahl von Personen | 5000 | ca. 50 ||
| Anzahl an genutzten Rollen | 2 | ca. 5-10 | dies hat keine Auswirkung auf die Suchperformance |
| Anzahl an Attributen pro Rolle | 7 und 182 | ca. 10-15 | jeweils zu ca. 50% genutzt |
| Anzahl an Attributen | ca. 472.000 | ca. 625 ||
| Länge der Texte | ca. 2,5 KB | ca. 50 KB | Für die Suche wurden kürzere Texte mit mehr Attributen gewählt |
| Anzahl der Einträge in der Historie | ca. 5 | ca. 50 | Historie wird für die Suche ignoriert |
| Speicher | ca. 2,3 GB | ca. 650 MB ||

Es wurde sich dafür entschieden die Texte kürzer zu halten und dafür deutlich mehr Attribute in die
Datenbank aufzunehmen. Dadurch lässt sich besser testen wie gut der Suchalgorithmus Ergebnisse
zusammenfassen kann. Einfache Suchen über Texte skalieren linear mit der Länge dieser, von daher
lässt sich hier weniger erreichen.

Ziel ist es, dass sämtliche Anfragen auf der Testdatenbank akzeptabel schnell vonstatten gehen (max.
3-5 Sekunden für komplexere Suchanfragen, einfache max. 1 Sekunde).

## Stand 0

Die Datenbank ist implementiert und ist nur über die Id der Einträge indeziert. Eine Suche erfolgt,
indem jeder Eintrag aus der Datenbank ausgelesen und mit dem Suchquery abgeglichen wird. Ist der
Abgleich erfolgreich, wird der Query zurückgegeben. Ein Eintrag ist entweder eine Datei
(Metainformationen ohne Inhalt der eigentlichen Datei), Interview oder Person. Bei der Person kommen
noch alle verknüpften Attribute inklusive Historie dazu. Bei Dateien die Historie der Änderungen.

Außerdem zeigt derzeit jede Person auf ihr Interview und jede Datei auf ihre Person und nicht
zusätzlich anders herum.

Das Abrufen einzelner Einträge dauert mitunter 5-10 Sekunden. Insbesondere das Herausfinden der
Grundinformationen von Personen aus Interviews (Id und Rolle) dauern 10-20 Sekunden. Die Abarbeitung
von einem einzelnen Wort innerhalb der Suchanfragen können gerne 30 Sekunden dauern.

## Stand 1 - Einfachen Index dranklatschen

**Änderung:** Die Ids für die verknüpften Interviews bzw. Person von Personen bzw. Dateien sind als
Index hinterlegt.

**Auswirkung:** Die Abfrage der Personen zu Interviews scheint gefühlt ein wenig schneller
vonstatten zu gehen, dauern aber immer noch zu lange.

## Stand 2 - Einträge als eigene Collections und doppelte Verknüpfung

### Änderung:
Die Attribute, Attributeshistorie und Einträge von Dateien werden von ihren Elternelementen
ausgegliedert und erhalten eigene Collections und Ids. Außerdem zeigen wird bei den Verknüpfungen
der doppelte Ansatz gewählt: Jedes Kindselement zeigt auf seinen Elternelement durch die Id, und das
Elternelement beinhaltet eine Liste von Ids. Das bedeutet ein klein wenig Mehraufwand bei der
Aktualisierung (da beide Seiten aktualisiert werden müssen) und ein wenig mehr totalen
Speicheraufwand, dafür sind die Einträge in der Datenbank selbst kleiner. Dadurch wird eine
schnelleres Einlesen und Speichern erwartet. Ein weiterer Vorteil ist, dass man nun weniger Daten
abruft, welche einen eigentlich nicht interessieren.

### Seiteneffekte:
- Vorher musste man nur wenige Objekte verwalten (Datei, Person und Interviews). Durch das
  Aufspalten ist die Verwaltung der Attribute, etc. nicht mehr einfach inklusive, sondern müssen
  separat gespeichert und aktualisiert werden. Das bedeutet ein wenig Mehraufwand in der
  Programmierung, kann dafür aber an anderen Stellen Vorteile bringen (z.B. bei Aktualisierung der
  Einträge). Die Verwaltung der Schnittstelle der Datenbank wird auf jedem Fall nocheinmal
  umstrukturiert.

### Auswirkung:
- Obwohl jetzt die Daten doppelt verlinkt gespeichert werden, hat sich an der Gesamtgröße von ca.
  2,3 GB nicht viel geändert.
- Die Reaktionszeiten für folgende Abfragen sind wieder auf einem normalen Niveau
    - Liste aller Interviews oder Personen (< 200ms, bei Personen mit vielen Attributen < 2s)
    - Öffnen eines einzelnen Interviews (< 80ms)
    - Abfragen der Liste aller Personen zu einem Interview (< 20ms)
- Eine normale Suche nach einen Begriff aus einem beliebigen Attribut dauert weiterhin sehr lange
  (ca. 45 Sekunden)

## Stand 3 - Suchsystem umbauen

### Änderung
Aktuell wird die Suche vom eingehenden Event verwaltet. Stattdessen soll eine eigene Klasse mit
Verwaltung und Status eingeführt werden. Diese wäre dann auch in der Lage die Suche jederzeit
abzubrechen. 

Es wird nicht erwartet, dass die Suche selbst schneller geschieht, stattdessen soll diese jetzt
abbrechbar und transparenter dem Nutzer gegenüber sein.

### Probleme 1
Die Implementierung der Datenbankschnittstelle nutzt für sich einen `ReadWriteLockSlim`, welcher
aber Thread-gebunden ist. Das heißt der Thread, der sich den Lock holt **muss** diesen auch wieder
zurückgeben. Wenn man einzelne Sachen abruft, dann macht das normalerweise kein Problem.

Für die Suchen gehen ich aber normalerweise jedes Element durch und gebe die nach und nach über
einen Iterator zurück. Derjenige, welcher den Iterator weiterführen möchte, bestimmt auch in der
Regel auf welchen Thread die Ausführung fortgesetzt wird. Und da ich mit mehreren Locks und
Wartephasen arbeite, werden hier verschiedene Tasks verwendet. Tasks haben aber die Eigenschaft,
dass die nicht Thread-gebunden sind. Sie können zwar ihre Ausführung auf dem ursprünglichen Kontext
(was nicht immer gleichen Thread bedeutet) fortsetzen, aber die Aufrufe geschehen in der Regel über
den aufrufenden Thread. So kann es sehr leicht passieren, dass der Iterator über einen anderen
Thread weitergeführt und auch beendet wird. Am Ende versucht die Datenbankschnittstelle den Lock
wieder zurückzugeben und wird verwundert feststellen, dass diese für den aktuellen Thread gar keinen
Lock hat.

Dieser Fehler geschieht nicht in 100% der Fälle. Aber je mehr Einträge man zurückgibt, desto
wahrscheinlicher wird der Fall, dass dies passiert.

Da ich weiterhin die Einträge über einen Iterator zurückgeben möchte (dadurch muss ich weniger Daten
im RAM halten und kann schneller Daten weiterverarbeiten), habe ich mich für folgendes Modell
entschieden: Es gibt ein Thread, welcher sich den Lock holt und die Einträge nach und nach abruft.
Die Einträge werden an einer bestimmten Stelle bereitgestellt und der Thread blockiert aktiv bis der
Eintrag abgerufen wurde. Danach kann ein beliebiger Thread ankommen und den Eintrag von der Stelle
abrufen und somit den den aktiv blockierten Thread wieder freigeben. Dieses Modell erfordert zwar
viele Locks, was die erwartete Laufzeitlich natürlich verlängert, dafür aber zu keinen unerwarteten
Fehlern mehr führt.

Man könnte auch die Bibliothek der Datenbank forken und eine andere Lock-Art verwenden, welche nicht
diese Schwachstelle hat, aber das wurde vorerst zurückgeschoben.

### Probleme 2
Bei der Umstellung wurde Syntax verwendet, welcher eigentlich ohne Probleme funktionieren sollte .
Dieser sieht in etwa so aus:

```csharp
public async IAsyncEnumerator<T> Filter(IAsyncEnumerator<T> iterator)
{
    await foreach (var item in iterator)
    {
        yield return item;
    }
}
```

An sich funktionierte dieser wie erwartet und es gab auch schon vorher ähnlich aussehende Ausdrücke
im Code. Doch jetzt stellte sich heraus, wenn dieser Ausdruck sehr lange ausgeführt wird und unter
Umständen sogar mehrere solcher Schleifen vorhanden sind, dass es eine `NullReferenceException` in
der Runtime gibt, welche sich nicht genau lokalisieren lässt. Nach vielen probieren und überfliegen
des Quellcodes der Dotnet Runtime auf GitHub stellt sich heraus, dass der Task, nachdem er
abgeschlossen war, versucht wird ein zweites Mal auszuführen. Dies ist eigentlich so nicht möglich.
Meine Lösung ist es jetzt, dass ich all diese Ausdrücke in eine Klassenstruktur (das was eigentlich
der Compiler macht, nur kompakter) überführt habe und schon taucht der Fehler nicht mehr auf.

### Auswirkung
- Keine deutlichen Unterschiede in der Suchperformance
- Code ist besser strukturiert

## Stand 4 - Suchindex erstellen

### Änderung
Alle aktiven Texte (historische werden ignoriert) werden in Wörter gespalten. Jedes Wort ist eine
Zeichenfolge bestehend aus Kleinbuchstaben und Zahlen. Großbuchstaben werden in Kleinbuchstaben
umgewandelt. Akzente in deren Entsprechungen umgewandelt und Sonderzeichen entfernt. Im Index wird
dann jedem Wort eine Liste an Fundorten angegeben. Ein Fundort besteht aus:
- Typ: Datei, Interview, Person, Attribut (hier nur der neuste Eintrag)
- Id

Im Suchstring wird dann das Gleiche gemacht und es wird eine Phase der Vorsuche eingeführt. Bei
einer Vorsuche wird ermittelt welche Einträge noch genauer analysiert werden müssen. Danach wird
eine normale Suche wie bisher darauf ausgeführt mit dem Unterschied, dass nur die Elemente aus der
Vorsuche genommen werden.

Die Indexe können vertrauenswürdige Daten enthalten, von daher wird dieser auch aufgespalten.

Eine Besonderheit am Index ist, dass eine Aktualisierung der Daten auch eine Aktualisierung des
Indexes bedeutet. Das bedeutet gleichzeitig auch Mehraufwand in diesem Bereich.

### Probleme 1
Wenn eine minimale Wortlänge von 1 genommen wird, dann wächst die Datenbank schnell auf das 10-fache
an, und das noch bevor ein zehntel der Daten gelesen wurden. Es wird daher eine minimale Tokenlänge
von 4 genommen. Kürzere Wörter sind eher weniger relevant für die Suche.

**Edit 1:**
Dies hat auch zu einer großen Logdatei mit schlechter Performance geführt. Also wurde es so
eingerichtet, dass die Änderungen am Index erst einmal nur gecacht werden und erst nach Abschluss
der Arbeit auf die Platte geschrieben.

Dadurch werden die Daten deutlich schneller verarbeitet und die Logdatei bleibt relativ klein.
Gleichzeitig stieg der RAM Verbrauch bis auf 600 MB an. Das Wegschreiben der ca. 18.000 Änderungen
geht danach relativ fix. Die endgültige Datenbankgröße ist dann ca. 3,2 GB (das bedeutet ca. 900 MB
Suchindex).

**Edit 2:**
Die Menge der Daten bei einer minimalen Wortlänge von 4 hielt sich in Grenzen. Von daher wurde eine
minimale Wortlänge von 3 ausprobiert.

Das hatte zur Auswirkung, dass das Programm nun bis zu 900 MB RAM verbrauchte. Der Speicher für die
Datenbank veränderte sich dagegen gar nicht und der Index beinhaltet nun ca. 18700 Einträge (kaum
ein Unterschied).

**Edit 3:**
Es werden nun Teilstücke mindestens der Länge 3 von alle Wörtern ermittelt und dazu mit in den Index
eingetragen. Dies hat nun zur Folge, dass ca. 144.000 Einträge im Index existieren. Die Daten
brauchen nun 3,3 GB auf der Festplatte (kein großer Unterschied) und am RAM Verbauch hat sich nicht
wirklich etwas geändert.

### Probleme 2
Es wird ein Index für Dateien, Interviews, Personen und Attribute erstellt. Die ersten drei
funktionieren super und sind relativ schnell. Beim Dritten kommt es dagegen zu einer Verzögerung im
folgenden Ablauf:
1. Man sucht die Ids der passenden Attribute für den Token (relativ schnell, gleiche Laufzeit wie
   für Dateien, Interviews und Personen).
2. Man geht nun diese Ids durch und sucht die Personen raus. Das funktioniert, indem man die
   Attribute selbst durchgeht und nach den zugeordneten Personen fragt. Dieser Schritt ist relativ
   langsam und braucht bei der aktuellen Datenbank um die 4 Sekunden.
3. Man hat nun eine Liste von Personen, diese wird mit der Personensuche gemerged und zusammen
   abgefragt.
4. Jede dieser Personen wird abgerufen und alle Attribute werden erneut geprüft. Auf die genaue
   Zuordnung aus dem 1. Schritt wird nicht erneut eingegangen.

Man speichert hier also im Index Daten zu genau, was dazu führt, dass man wieder die Datenbank
durchgehen muss, um die benötigten Daten zu erhalten. Leider führt dieser Ansatz außerdem zu
kuriosen versteckten Bugs.

Als Lösung werden alle Tokens der Attribute direkt den Personen zugeordnet und gemeinsam behandelt.
Dies führt dadurch zu einen erhöhten Aufwand bei der Aktualisierung, sollte aber die Abfragen
deutlich vereinfachen.

### Auswirkung
Die Suche ist jetzt deutlich schneller als zuvor. Die Ergebnisse werden in einem Bruchteil einer
Sekunde angezeigt (sofern Suchindex im Query auch genutzt wird)

## Stand 5 - Sortierung einbauen

### Änderungen
Für die Suche werden die Sortierparameter vor dem Senden an die Datenbank ausgewertet und aus dem
Query entfernt. Die Sortierungeinstellungen wird dann an auf die Suchergebnisse angewandt und
unsortiert an die Oberfläche gesendet. Die Oberfläche sortiert dann die bekannten Ergebnisse für
sich selbst. Das hat den Vorteil, dass der Nutzer schnell Ergebnisse (auch wenn es am Anfang
vermutlich eher schlechte sind) sieht.

Für die Sortierung gibt es also folgende Schritte:

1. Die Datenbank sucht wie gehabt seine Daten. Diese werden unsortiert weitergegeben.
2. Jeder Rückgabewert erhält entsprechend der Position des Sortierparameters seine Werte. Es kann
   nach folgende Wertetypen sortiert werden:
   - Ganzzahlen (long)
   - Fließkommazahlen (double)
   - Strings
   - Null (kein Wert für das Feld verfügbar - wird somit immer (unabhängig von der Sortierrichtung)
     ans Ende sortiert)
3. Die Rückgabeparameter werden mit den Sortiereinstellungen und den reinen Suchparameter an die
   Oberfläche übertragen.
4. Die Oberfläche sortiert die neuen in die alten Suchergebnisse ein. Dazu nutzt es die übergebenen
   Sortierparameter und Sortiereinstellungen. Falls die Anzahl der Ergebnisse zu groß wird, dann
   wird die aktuelle Liste abgeschnitten.

Man hätte das auch auf Ebene der Datenbank sortieren könnten. Das hat aber den Nachteil, dass alle
Ergebnisse für die Sortierung zurückgehalten werden müssen. Das kostet Zeit und der Nutzer ist nicht
in der Lage schon früh relativ gute Ergebnisse zu sehen.

### Probleme 1
Die Oberfläche ist nicht in der Lage eine große Anzahl an Ergebnissen gleichzeitig anzuzeigen (ca.
1000). Dies führt zu einer schlechten Performance. Als Zwischenlösung wurden auf Ebene der Datenbank
nur die ersten 100 Ergebnisse weitergegeben, was sehr gut funktioniert.

Um das Problem in der Oberfläche zu beheben, muss eine Paginierung in der Oberfläche eingebaut
werden, wo an sich alle Ergebnisse bereitgehalten werden können, aber nur ein Teil davon angezeigt
wird.

### Auswirkung
Die Sortierung funktioniert. Man erhält nun schon frühzeitig Ergebnisse, welche mit der Zeit auch
verbessert werden können. An der Suchgeschwindigkeit hat sich nicht viel geändert.

Man kann noch versuchen den Score etwas besser zu berechnen. Aktuell wird nicht berücksichtigt, wo
die Stelle im Wort gefunden wurde.
