Jakbyś to robił na Postgresie, to mam aplikację do automatycznego zakładania indeksów na bazie i "clustrowania" tabel. Wystarczy podłączyć do bazy i wpisać zapytania, albo zassać je z logu (ale wtedy trzeba wcześniej włączyć logowanie zapytań), kliknąć jeden guzik i po kilku sekundach podaje jakie indeksy trzeba założyć, a które są niepotrzebne.
Można też zoptymalizować bazę pod konkretne, docelowe wielkości tabel - tj. teraz masz mało użytkowników, ale zakładasz, że będzie dużo, więc dajesz mu że np. w tabeli z userami będzie tyle a tyle rekordów i to uwzględnia. Na razie wersja beta, ale już da się używać w praktyce. Kiedyś pisałem o tym na forum.
Do MySQLa wersję będę miał później, bo nie jest to w tej chwili dla mnie priorytetowe. Zresztą w MySQLu prawie nie ma co optymalizować, bo on i tak mało umie. Z drugiej strony do MySQLa brakuje tylko wtyczki do importu logów zapytań i schematu bazy wraz ze statystykami optymalizatora*, więc jeśli byłbyś bardzo zainteresowany, mógłbyś dopisać ;)
*) Nie wiem, czy z MySQLa da się wyciągnąc - z Postgresa dało się bez problemu, bo on wyniki ANALYZE trzyma w tabelach systemowych. W razie czego trzeba policzyć pewne rzeczy z danych, ale to jest wolne.