Improving query time for auto complete box with millions of record I have a very basic requirement. I have a table that store city id (primary key) and city name (nvarchar value). The remaining information is stored in a separate table. In my UI, I have an auto complete box, that lists all cities when user start typing. After selection, application gets the data for that particular city to fill up. 

The main table with just two columns for city id and name, is indexed on name. I am currently running following query to get the list of names. 

Select cityname from citylist where cityname like '%' + citynamevar + '%'


This query is supposed to give me the list of all names that contain the value typed by user. It currently takes about 2 minutes to run on approx. 600k records. 

I have also added a way to display 10 records in the beginning, while the query executes. But even then, it is not helping the case as remaining data loads way too slow. 

I am trying to find ways I can improve this query time. Till now I have found about full text search, which I believe should help. I was just wondering if there is any other method I can try or any trick to get the query to respond fast enough. 

I am currently using SQL server 2012. I tried running the query directly outside the application, using ssms too. And even then it took the same amount of time. Indexing sped up the query by about 20% but not enough to be meaningful. 

Edit: 

No idea why I am not able to comment anymore on this post. Anyway, it is a test build to see how much impact auto complete boxes will have. It is running on my personal laptop (core i5, basic mobile GPU). I am using SQL server 2012, .net 4.5 with wpf. 

I can ask user to reduce the search space by entering country name. But this is supposed to be a generic solution. In some cases, we don't have any way to reduce the search space. And it has to be a "contains" search, instead of "starts with". Which might be the reason why indexing hardly had any impact. 

The table is just 600k records, out of which we need to display 1000-10k. The query is executed only once when user type the third character, after which remaining characters are sorted within the application from that 1000-10k records. I can reduce the impact by increasing the character count to 5, but then user will be unable to see any suggestions for most city names.
Have you thought about restricting the search in the UI?  Don't start the autocomplete query until after they've typed 3 or 4 characters. Then instead of looking for 6000 A*, the first jump would be a fraction of that number still. 

Also, @Jonathan Fite 's comment about removing the leading % is also a good way to reduce time.  Unless, your users start looking for ew Yor, or shington...