Begrenze die Ausgabe durch limit-anweisungen, z.B. ersten 30 Ergebnisse mit
LIMIT 0,30
Du kannst auch wenn der Suchstring zu klein ist gar keine Suche machen und einen Text ausgeben "Bitte mindestens 4 Zeichen" o.so ähnlich.
Zum Thema Indizierung bist Du am besten in der
MySQL Doku aufgehoben.