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