İlk öneri olarak mysql in full text search özelliğini kullanmalısınız.
http://dev.mysql.com/doc/refman/5.1/...t-boolean.html

Eğer başarılı olamazsanız en azından '$veri%' olarak aratmanız performansı arttıracaktır.