Optimierung: alle Wörter aus Buchstaben suchen

[Thomaier]

Hallo,
ich betreibe eine Seite, auf der Nutzer Buchstaben eingeben können, aus denen dann Wörter gebildet werden. Die Wörter stehen in einer Datenbank. Es müssen nicht alle eingegebenen Buchstaben verwendet werden und sie dürfen nur in der Häufigkeit vorkommen, in der sie auch eingegeben wurden. Hinzu kommt ein möglicher Joker, der für jedes Zeichen stehen kann.
Bisher habe ich die Suche in MySQL 5.0.5lb über reguläre Ausdrücke gemacht, hatte jedoch mit dem Joker und Umlauten Probleme. Außerdem habe ich nun mehrfach gelesen, dass reguläre Ausdrücke sehr performencelastig sind.

Die Datenbank sieht nun wie folgt aus:

Tabelle: word (enthält die Wörter)
ID | word | length
---+-----
1  | MENSCH | 6
2  | RETTEND | 7
3  | RETTEN | 6

Tabelle: word_letter
enthält die Buchstaben [letter] und deren Häufigkeiten [n] zu den Wörtern

ID_word | letter | n
--------+--------+---
1       | M      | 1
1       | E     | 1
1       | N      | 1
1       | S      | 1
1       | C      | 1
1       | H      | 1 => MENSCH
2       | R      | 1
2       | E      | 2
2       | N      | 1
2       | D      | 1
2       | T      | 2 => RETTEND
3       | R      | 1
3       | E      | 2
3       | T      | 2
3       | N      | 1 => RETTEN

Es sind über 100.000 Einträge in der ersten Tabelle bei über 600.000 Einträgen in der zweiten vorhanden.

Derzeit habe ich folgende Abfrage, die von PHP je Eingabe neu generiert wird. Dies ist ein Beispiel für die Nutzereingabe "EEGHN" (z.B. mit dem Ergebnis "gehen", "HEGE", etc.):

SELECT w.ID AS ID_word, w.word  
FROM word AS w  
LEFT JOIN word_letter wl_e ON w.ID = wl_e.ID_word AND wl_e.letter = 'E' AND wl_e.n <= 2  
LEFT JOIN word_letter wl_g ON w.ID = wl_g.ID_word AND wl_g.letter = 'G' AND wl_g.n <= 1  
LEFT JOIN word_letter wl_h ON w.ID = wl_h.ID_word AND wl_h.letter = 'H' AND wl_h.n <= 1  
LEFT JOIN word_letter wl_n ON w.ID = wl_n.ID_word AND wl_n.letter = 'N' AND wl_n.n <= 1  
WHERE w.length <= 5 AND (IF(wl_g.n IS NULL, 0, wl_g.n) + IF(wl_e.n IS NULL, 0, wl_e.n) + IF(wl_h.n IS NULL, 0, wl_h.n) + IF(wl_n.n IS NULL, 0, wl_n.n) = w.length)  

Jeder eingegebene Buchstabe fügt einen LEFT JOIN ein. Am Ende wird mittels der Wortlänge grob gekürzt und dabei geprüft, dass die Anzahl der vorkommenden Buchstaben gleich der Wortlänge ist. Dabei kann die Anzahl der Buchstaben um eins erhöht werden, falls ein Joker eingegeben wurde.
Alle hier genannten Felder sind indiziert.

Mein Problem ist nun, dass die oben genannte Abfragestruktur bei der Suche nach Wörtern mit mehr als 5 Buchstaben schon bei 8 Sekunden liegt, noch nicht erwähnt, dass bis zu 10 verschiedene Buchstaben ja bis zu 10 LEFT JOINs erzeugen, was dann schon einem Serverabsturz nahe kommt.

Ich habe es, zur Info, erfolglos mit einem anderen Abfrageansatz versucht. Dabei habe ich die word_letter-Tabelle per FROM (SUBSELECT) immer weiter eingeschränkt. Die genaue Abfrage hat sich dabei immer wieder geändert und ich werde euch nicht mit allen Fehlversuchen zutexten. Mich interessiert hier nur die Meinung von euch, über welchen konkreten Ansatz sich das vielleicht doch sinnvoll und performant machen lässt:
1. Alle Buchstaben von Wörtern mit maximal 5 Buchstaben raussuchen
2. Alle Buchstaben von Wörtern mit maximal 2 "E"
3. Zeilen mit den Buchstaben "E" entfernen => daher sinkt eine mit HAVING SUM(n) ausgegebene Buchstabensumme von Wörtern
4. Buchstaben ausgeben für die gilt: GROUP BY ID_word HAVING SUM(n) <= 3
(die 3 ergibt sich aus der Gesamtlänge der Eingabe des nutzers "eeghn" minus die 2 bereits gelöschten "e")
Schritt 2 bis 4 werden dann für alle restlichen Buchstaben wiederholt:

Muster:
SELECT
FROM (
 SELECT
 FROM (
  SELECT
  FROM word_letter
  LEFT JOIN word ...
  WHERE word.length <= 5
  )
 )
)

Vielen Dank für jegliche Hinweise. Ich arbeite schon Tage an einer Lösung, finde aber einfach kein Ende, bzw. kein einfaches Ende.

Thomaier

[Alexander (HH)]

Moin Moin!

Vielen Dank für jegliche Hinweise. Ich arbeite schon Tage an einer Lösung, finde aber einfach kein Ende, bzw. kein einfaches Ende.

Das sieht ganz nach einer Fortsetzung zum archivierten Thread MySQL : mit regulären Ausdrücken Wörter für Buchstaben suchen aus.

Alexander

[Thomaier]

Hallo Alexander,

Das sieht ganz nach einer Fortsetzung zum archivierten Thread MySQL : mit regulären Ausdrücken Wörter für Buchstaben suchen aus.

Der alte Thread hat eine Struktur-Lösung geschaffen, jedoch nicht die Abfrage vollendet. Vinzenz meinte, ich solle mit einem neuen Posting warten, bis der alte Thread im Archiv ist. So ist es nun. Weiterhin habe ich in der Charta einige Gründe gefunden, die dieses Posting rechtfertigen.

Ich nehme aber natürlich Antworten auch im alten Thread entgegen.

Gruß,
Thomaier

[Patrick Andrieu]

Hallo Thomaier!

Vinzenz meinte, ich solle mit einem neuen Posting warten, bis der alte Thread im Archiv ist. So ist es nun. Weiterhin habe ich in der Charta einige Gründe gefunden, die dieses Posting rechtfertigen.

So ist es auch richtig. In dem Fall aber, wenn ein Problem eine »Vorgeschichte« hat, ist es sinnvoll, den entsprechenden Archivthread gleich zu verlinken, so dass Thematik-Quereinsteiger sofort erkennen können, dass das Thema bereits diskutiert worden ist. Aus den Antworten, die Du im ersten Thread erhalten hast, und aus der neuen bzw. erweiterten Problematik kann ein Antwortender evtl. die zielführende Lösung anbieten.

Viele Grüße aus Frankfurt/Main,
Patrick

[Tom]

Hello,

sehe ich das richtig, dass die zweite Datei lediglich Auskunft darüber geben soll, wieviele Buchstaben  jeder Spieler besitzt?

Dann wäre das keine Aufgabe für eine Datenbank, sondern für eine dirrektgestreute Datei. Die Anzahl möglicher Buchstaben liegt fest und ihre Reihenfolge lässt sich auch bestimmen. Unter PHP würde ich dann ein serialisiertes Array dafür nehmen.

Die Wortliste kann dageben durchaus als Datenbankdatei geführt werden, da sie offen ist.

Liebe Grüße aus Syburg

Tom vom Berg

[Thomaier]

Hallo,

sehe ich das richtig, dass die zweite Datei lediglich Auskunft darüber geben soll, wieviele Buchstaben  jeder Spieler besitzt?

Die zweite Tabelle enthält die Anzahl der Buchstaben für jedes Wort der ersten Tabelle. Spieler gibt es bei mir nicht, nur eine Suche nach Begriffen, welche von Scrabble-Spielern abgefragt werden kann.
Die Tabelle ist sinnvoll, wenn ich auf regüläre Ausdrücke verzichten will, die sich hier besonders aufgrund der deutschen Umlaute nicht eigneten.

Gruß,
Thomaier