Anda sebaiknya menggunakan indeks teks lengkap (Anda bilang tidak bisa), merancang pencarian teks lengkap sendiri atau membongkar pencarian dari MySQL dan menggunakan Sphinx/Lucene. Untuk Lucene Anda dapat menggunakan implementasi Zend_Search_Lucene dari Zend Framework atau menggunakan Solr.
Indeks normal di MySQL adalah B+Trees, dan tidak dapat digunakan jika awal string tidak diketahui (dan ini terjadi ketika Anda memiliki wildcard di awal)
Pilihan lain adalah menerapkan pencarian Anda sendiri, menggunakan tabel referensi. Pisahkan teks dalam kata-kata dan buat tabel yang berisi kata, record_id. Kemudian dalam pencarian Anda membagi kueri dalam kata-kata dan mencari setiap kata dalam tabel referensi. Dengan cara ini Anda tidak membatasi diri Anda pada awal keseluruhan teks, tetapi hanya pada awal kata yang diberikan (dan Anda tetap akan mencocokkan kata-kata lainnya)
