AutoComplete controls have become a main feature in many interactive website and web applications.
In fact it is very common to explain the advantages of AJAX using the “Google Suggest” example, as this was one of the first powerful well known implementations implementations.
The AutoCompleteExtender is implemented using the second approach – this approach works best when the vocabulary that needs to be considered for suggestions is potentially very large – this would make it impractical to download the full list of possibility to the client.
When you implement an AutoCompleteExtender you need to provide a web service that will be used to supply the word/sentence completions. But, the guide and sample stop there and do not instruct you how to build an effective web service.
You need to consider that such a web service is used in a highly interactive way, and may need to respond quickly to the waiting user by suggesting completions from a potentially large database. Furthermore each user is likely to make several such completion requests within a short period of time. If you intend to support many concurrent users, you have a potential load problem on your hands.
The trivial implementation for such a web service would select from the DB your data and convert it to a string array, there are quite a few such examples on the web, here’s a raw snippet for the service method:
public string GetStudentNames(string prefix)
string sql = "SELECT * from students WHERE name like @prefix";
string items = new string[dt.Rows.Count];
int i = 0;
foreach (DataRow dr in dt.Rows)
The problem with the above code is that it will access the DB to retrieve and filter the required data every time the user will change the prefix in the the AutoComplete control. This puts unnecessary strain on both your DB server and the web server and will severely degrade the performance if the amount of data involved is large.The common solution for unnecessary DB trips is caching, but here we encounter another problem – what is it that we need to cache and how?
In the above example we could potentially select all student names in the DB and cache that as a list in memory – but when the method is called we will need to filter only those names that start with the required prefix. A naive implementation will go over the whole list and check each string against the prefix (with a complexity of O(n) where n is the number of student names in the DB), but there are more appropriate data structures to handle this problem.
One of the best data structures to handle this problem is the Trie.
A .NET Trie implementation that is specifically tailored to serve the AutoCompleteExtender can be downloaded from CodePlex here.
The time complexity of building a Trie is considered to be O(n) where n is the total amount of strings to be contained in the Trie. To search for the existence of a prefix we need O(l) where l is the length of the prefix.
Retrieving a list of strings beginning with the prefix – is done at O(m) where m is the number of strings that will be retrieved.
You should consider that querying the DB, and building a large Trie can be costly in time and memory. But once the Trie is built you can cache it and use it repeatedly for fast search and string completions. Specifically, you can use a cached Trie to repeatedly return string suggestions from the AutoComplete web service.
How To Use
First download the code from CodePlex.
Follow the regular instructions on how to use the AutoCompleteExtender.
Make sure your web service builds the AutoCompletion Trie and stores it in cache, if it does not already exist. If and when it does exist use it to return the completion list:
public string GetCustomers(string prefixText, int count)
Trie customersTrie = (Trie)Context.Cache["CustomersTrie"];
if (customersTrie == null)
customersTrie = new Trie();
Context.Cache["CustomersTrie"] = customersTrie;
List<string> list = customersTrie.FindCompletions(prefixText);
Note that the Trie is thread safe for multiple readers only. You should protect the Trie from concurrent read/write operations.
Check out the code and unit tests for some further details, to run the unit tests you will need NUnit. If you want to run the performance test you will need an external dictionary you can use the AGID wordlist from: http://wordlist.sourceforge.net/ or modify the code to use a different large word list.
Here are some posts I have found helpful while building this Trie:
Share & Enjoy.