Improving query time for auto complete box with millions of record

Question

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.

Answer 1

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...

Answer 2

A leading % kills use of an index
Most users want autocomplete based on first characters anyway
Most users don't care about more than 1000
Have an index on city

select top (1000) city 
from citylist 
where cityname like citynamevar + '%' 
order by city;

If you can have them select a state from pull down

select top (1000) city 
from citylist 
where cityname like citynamevar + '%'  
and state = statenamevar
order by city;

If you are in desktop app then download the city to a collection and search the collection. You end up with a lot of round trips to the database and returning the same data multiple times

A trick I also use is wait 1/10 seconds before sending off the request so they can slam in multiple 4+ characters.

If they want more than 1000 then give them a button or use a key (like tab) to mean get more

Answer 3

Full text search fits more into your scenario. A full text search uses inverted index - think of it as an index structure that stores words or number mapping to its location in database.

There are good amount of changes in sql server 2012 for full text search.

Check Full-Text Search (SQL Server)

A LIKE query against millions of rows of text data can take minutes to return; whereas a full-text query can take only seconds or less against the same data, depending on the number of rows that are returned.