regex - Speedup mysql queries with regexp and order by length -

i trying implement search auto-completion feature on website. came far table search terms (cities)

city_id int(10) auto increment, primary city_name varchar(200) index 

and query

select * city_names lower(city_name) lower('my_search_term%) order length(city_name) limit 10; 

this query returns 10 cities shortest names containing search string, need, it's slow. guess db first searches matches regexp, sorts results length, , picks 10 rows. think better somehow pre-sort data length(city_name), query stops after reaches 10 rows match regexp.

so questions are:

1. is there way sort (collate?) city_names column content length? i'm not planning alter table data, data need sorted 1 single time.
2. what db engine , index structure suitable table (city_names data not unique)?
3. is there way change query in order increase performance?

any ideas welcome.

update: based on zerkms's suggestions, did following:

1. changed collation latin_general_ci. allowed me rid of lower(city_name) conversion.
2. created column (sort_index) , populated incremental values ordering length(city_name) , city_name. i.e., short names go first, , "a**" goes before "b**" cities same length. search quicker.
3. changed default order sort_index ascending. don't need order commands in query.

the table , query like:

sort_index int(10) primary city_name varchar(200) city_id int(10) auto increment  select * city_names city_name lower('my_search_term%) limit 10; 

1. if use *_ci collation string comparisons should case insensitive. city_name lower('term%') should used.
2. create column , store each city_name column length there
3. create composite (city_name, city_name_length) index (but there chance city_name_length won't used though)