Enhanced performance for the ASP.NET AJAX autocomplete control

The Problem

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.

Microsoft has provided a very powerful and easy to use control in the ASP .NET AJAX Control Toolkit – the AutoCompleteExtender.

There are two approaches to creating AutoComplete controls. The first one is to transmit all possible data to the client, and implement the algorithm that suggests possible completions, in the browser using JavaScript. The other approach is to send an AJAX request to the server that will retrieve a list of suggested completion words. Such a request is being made every time a new prefix is entered in the AutoComplete text box.

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:

[WebMethod]
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)
{
   items.SetValue(dr["name"].ToString(), i);
   i++;
}
return items;
} 

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.

The Solution

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:

    [WebMethod]
public string[] GetCustomers(string prefixText, int count)
{
   Trie customersTrie = (Trie)Context.Cache["CustomersTrie"];
   if (customersTrie == null)
   {
       customersTrie = new Trie();
       customersTrie.Load("Donald Duck");
       customersTrie.Load("Duffy Duck");
       customersTrie.Load("Mini Mouse");
       customersTrie.Load("Mickey Mouse");
       customersTrie.Load("Pluto Dog");
       customersTrie.Load("Guffy Dog");
       Context.Cache["CustomersTrie"] = customersTrie;
   }
   List<string> list = customersTrie.FindCompletions(prefixText);
   return list.ToArray();
}

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:
http://sujitpal.blogspot.com/2007/02/three-autocomplete-implementations.html
http://rmandvikar.blogspot.com/2008/07/tries.html
http://rmandvikar.blogspot.com/2008/10/trie-examples.html

Share & Enjoy.