フルテキストインデックスを使用するか（使用できないと言った）、自分でフルテキスト検索を設計するか、MySQLから検索をオフロードしてSphinx/Luceneを使用する必要があります。 Luceneの場合、Zend FrameworkのZend_Search_Lucene実装を使用するか、Solrを使用できます。
MySQLの通常のインデックスはB+Treesであり、文字列の先頭が不明な場合は使用できません（これは、先頭にワイルドカードがある場合です）
もう1つのオプションは、参照テーブルを使用して独自に検索を実装することです。テキストを単語に分割し、単語record_idを含むテーブルを作成します。次に、検索でクエリを単語に分割し、参照テーブル内の各単語を検索します。このようにして、テキスト全体の先頭に制限するのではなく、指定された単語の先頭のみに制限します（とにかく、残りの単語と一致します）