Skip to main content

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.

Comments

Popular posts from this blog

SSL must not be enabled for pickup-directory delivery methods

Maybe I'm just getting soft and lazy.
It seems I've gotten used to just finding the answer to everything I need by googling it and relying on the community to solve it for me.I mean, at least when I’m not dealing with the bleeding edge of technology, I should expect to find a post from somebody who’s already ran into a similar problem – right?Well, I was a bit surprised when I tried to implement a simple email client using the totally mundane System.Net.Mail (really not bleeding edge, is it?), and received the following exception:“SSL must not be enabled for pickup-directory delivery methods“Happily I searched the web for this error message only to find two (2!) whole articles about it, none of which was any help at all.So, I figured it’s a good enough reason for my first blog post. After all, the blog itself has been ready and waiting for several months now for me to find the time and motivation to write something.But, I was doing something really trivial - there must be thous…

Containing Child Controls inside a UserControl

User Controls are a very quick and effective method to develop reusable controls for your application. They are usually much easier to develop than writing your own custom server controls.I ran into a situation the other day that a user control we’ve made and had been working on for some time, just got a new requirement to be able to contain child server controls. I was a bit surprised to discover this is not a trivial matter.It seems there is a weird limitation on User controls. If you try to put child controls in them or nest a user control inside another, the designer will complain. Furthermore if you thought you could use the PersistChildrenAttribute in order to convince the designer that your control is really intended to support this behavior, then think again – it seems that the designer simply ignores this possibility when it comes to user controls.While searching for a solution, I discovered this post by Bobby DeRosa that suggested a reasonable solution. The problem with this…