Вы можете рассмотреть возможность поворота стола и его нарезки. Возьмите все свои столбцы varchar и сохраните данные в одной таблице "Search_Strings"; сделать то же самое для столбцов int:
оригинальный стол
id
always_field1
always_field2
varstring1
...
varstringx
int1
...
inty
new main_table (то же количество строк, что и в исходной таблице, но очень мало столбцов)
id
always_field1
always_field2
Search_Strings (
id (FK to main_table)
old_column_name
string_value
Search_Ints
id (FK to main_table)
old_column_name
int_value
При такой настройке вам нужен полнотекстовый индекс только для string_value. Извините, я ничего не могу предложить Сфинксу или Люсене, так как я не знаком с ними.