search autocomplete performance with many records

Hi All,

We have a search_index table with over 5 Million records. As the result the search autocomplete module becomes very slow to respond. The AJAX request for a two character search (eg "be%") for example would take 23 seconds to respond (for a Sort by keyword's score).

As a solution we looked at creating a new table "search_words" which is simply a list of words used in the search. This reduced the search time to 500ms which is acceptable but still not ideal given that we will probably expect to get to 10 million records at some stage.

We've also considered creating a series of tables (probably 26, corresponding with each letter of the alphabet) to reduce the search time.

Has anyone else a) encountered this and/or b) have any approaches for a solution to reduce the search time?

Thanks