Optimizing the table to hold a million records
The possible solution is to limit the resulting set to 10-20 rows as well as sorting not only alphabetical but also by frequency. There are vocabularies exists that contains words along with the probability to be met in the text. May be you have to build your own based on the query statistics. That is called ranking and is used by the search engines. In the simpliest case you have the table like that:

+------+------+
! word ! prob !
+------+------+


and the query is :

SELECT word
  FROM table
 WHERE word LIKE a%
 ORDER BY prob DESC
        , word ASC
 LIMIT 10
;