Я конечно не профи, но можно попробовать:

1. Выгрузить нужные столбцы в программу после ввода первого символа, а затем делать поиск в оставшемся только средствами приложения.
2. Или сделать поиск по минимум трем символам, если такой подход возможен.

Хотя при большем объеме базы это один хрен тормоза.