Сейчас сайт работает на MySQL 4.1.x

Активно используется поиск по таблице, в которой сейчас под 3 миллиона записей (дальше будет больше ещё на несколько миллионов). Собственно поиск идёт по трём строковым полям (длиной не более 100 символов каждое). Для ускорения использую индекс FULLTEXT - на эти три поля.

Всё бы ничего, но ищет он только слова целиком. Чтобы найти что-то по части слова, приходится использовать оператор LIKE, и такой поиск растягивается порой на десятки секунд (слова целиком по индексу FULLTEXT находит практически моментально).

Требуется ускорить поиск по частям слова (по вхождению).

Апгрейд железа, думаю, ну сократит с 20 секунд до 10-5, но это не то. Должно быть какое-то чисто софтовое решение, типа того же FULLTEXT, но чтобы искал по вхождению.
В каких базах такое есть? Желательно бесплатных, и легких для прикрутки к PHP-сайту. Может, уже в 5-й версии MySQL такое есть? Может, в PostgreSQL?