wobei es nicht immer gut für die suchperformance ist, eine tabelle zu
normalisieren. aber erstmal indizes anlegen ist die beste idee.
die kardinalität eines index sollte hoch sein. die bekommst du
angezeigt, wenn du show indexes from table aufrufst.
beispielsweise hat ein index auf eine spalte mit nur 3 möglichen werten
eine sehr geringe kardinalität.
auch ist zu beachten, dass MySQL nur auf einem index arbeiten kann.
explain select ... zeigt dir, welchen index MySQL benutzen würde und
wieviel zeilen dann noch manuell durchsucht werden müssen.
kombinierte indizes können sich lohnen. du musst halt wissen,
wonach am meisten gesucht wird.
und wenn das alles nichts hilft, steig auf eine suchmaschine um.
datenbanken sind nur begrenzt als hochleistungs-suchmaschinen
tauglich.

bzgl. like "%foo%": du kannst in mySQL einen volltextindex anlegen.