Varför inte köra sidan på en VPS istället? Om du nu vill bygga ett vettigt FULLTEXT index som du vill söka snabbt i så är ju Sphinx att rekommendera. Alternativt så kan du ju lägga enbart Sphinx delen på en VPS och ha resten på ett webbhotell.
Om du nu endå vill göra det i MySQL så kolla manualen för deras FULLTEXT indextyp:
http://dev.mysql.com/doc/refman/5.0/...xt-search.html