आपको या तो पूर्ण-पाठ अनुक्रमणिका का उपयोग करना चाहिए (आपने कहा था कि आप नहीं कर सकते हैं), अपने आप से एक पूर्ण-पाठ खोज डिज़ाइन करें या MySQL से खोज को ऑफ़लोड करें और Sphinx/Lucene का उपयोग करें। लुसीन के लिए आप ज़ेंड फ्रेमवर्क से Zend_Search_Lucene कार्यान्वयन का उपयोग कर सकते हैं या सोलर का उपयोग कर सकते हैं।
MySQL में सामान्य अनुक्रमणिका B+Tree हैं, और यदि स्ट्रिंग की शुरुआत ज्ञात नहीं है, तो उनका उपयोग नहीं किया जा सकता है (और यह तब होता है जब आपके पास शुरुआत में वाइल्डकार्ड होता है)
एक अन्य विकल्प संदर्भ तालिका का उपयोग करके स्वयं खोज को लागू करना है। टेक्स्ट को शब्दों में विभाजित करें और तालिका बनाएं जिसमें शब्द, record_id हो। फिर खोज में आप क्वेरी को शब्दों में विभाजित करते हैं और संदर्भ तालिका में प्रत्येक शब्द की खोज करते हैं। इस तरह आप अपने आप को पूरे पाठ की शुरुआत तक सीमित नहीं कर रहे हैं, लेकिन केवल दिए गए शब्द की शुरुआत तक (और आप वैसे भी बाकी शब्दों से मेल खाएंगे)