Virtual List View Searches

Virtual List View (VLV) searches were introduced with Windows 2003 as an efficient way to return subsets of otherwise very large result sets. The secret to the speed and efficiency of a VLV search is that unlike traditional searches, VLVs do not need to retrieve all entries before returning a portion of the result set.

A common task for many enterprise application developers is to create a form (web or desktop) to allow users to search Active Directory. This application might have a few text boxes into which the user can enter search termsperhaps a last name by which to search (a custom phone-book of sorts). The results will then be displayed in a paged DataGrid or ListBox.

Inevitably, the first thing a user will do is type S* and search for every single user in the directory that has a last name starting with the letter S. For a small domain with only a few thousand users, this probably won't make much of a difference. For a very large Active Directory installation, however, we might time out before this thing returns (especially if this is a web request).

From a performance perspective, this was always a critical test: If we waited to load all the results before displaying the ListBox, there would be a noticeable lag that the user would dislike (likely causing her to pound on the Search button again). We could try to solve these problems either by loading asynchronously, or by smart paging (i.e., loading only what the user might see in her current ListBox view). Built-in asynchronous support for LDAP searching was available only for C/C++ developers prior to .NET 2.0, and properly working asynchronously can be challenging, especially when we are working with a web page and not a local desktop application. While asynchronous searching with partial results might solve the sluggishness the user perceives, it does nothing to alleviate the horror the directory administrator feels as she watches helplessly while her domain controller CPU is pegged at 100% for 5 minutes as someone tries to return 30,000 results (nonindexed, of course).

A better solution that both conserves resources and behaves responsively is to return only the portion of the larger result set that the user is presently looking at. With databases, we would offload the paging to the database server and have it selectively return a portion of the results using standard SQL statements. Until Windows Server 2003 and ADAM, this was not possible with LDAP searchesit was an all-or-nothing proposition. Using VLV searches, however, we can easily mimic the smart-paging behavior that was previously possible only with database servers. In this section, we will outline where a VLV search is most appropriate and the different methods by which to use this powerful feature.

Warning: VLV Might Not Behave Well in Active Directory

As of this writing, there are some known issues in the VLV implementation in Active Directory that cause it not to work as expected. The implementation in ADAM seems to work fine, however. We believe Microsoft is working to address these issues, but a fix may not be available as you are reading this. Use caution if you are targeting VLV for Active Directory.

 

Offset versus Target Searches

There are two different mechanisms for performing a VLV search. The first uses the Offset property, and the second uses the Target property. It might be confusing, but we only ever use one or the other of these properties at a time. The basic difference between the two methods is that the Offset type of search is specified by a numeric location within our result set, and the Target search is specified by some value within the result set. From a conceptual level, let's assume that our data can be represented by an array of letters sorted alphabetically, like this:

{"A", "A", "A", "F", "G", "L", "N," "O", "O", "S", "T", "W", "Z"}

As an example of an Offset search, we could specify that we wished to retrieve one result from either side, centered on the middle of the result set. We would do this by specifying an Offset of 7 and a BeforeCount and AfterCount of 1 each. The seventh result in this case is N, and we would choose the L and O surrounding it. In reality, this is an approximation, so the result might differ slightly, but this is a conceptual exercise at this point.

For this type of search, we can also use a handy shortcut in the TargetPercentage property that represents Offset/ApproximateTotal. This use of the VLV search is appropriate when we want information by position in the result set and not necessarily by value.

Separately, we could also define our VLV search to use the Target property. The way this works with respect to the previous example is that we specify a value representing the attribute that was used for sorting. In our case, we might not know or care what values are near the center of our result set. Instead, perhaps we want to return results that surround results starting with S (this might actually lie anywhere in the sorted results). We can do this by specifying the Target as S, and a BeforeCount and AfterCount of 1 each. This type of search is appropriate when we don't know where in our approximate total our values might be positioned, but we do know what the data might look like.

Using the DirectoryVirtualListView Class

Before we dig too deep into examples, we should cover what properties are available on the requisite helper class, DirectoryVirtualListView, and what they are used for.

AfterCount

This represents the number of results to select after the target offset. Adding the AfterCount and BeforeCount together should yield the approximate total number of results to select.

ApproximateTotal

Much as it sounds, this represents the approximate total number of results that will be retrieved. When set by the client, this helps the server quickly determine where in the offset to search. By default, this value is 0, which indicates that the server should determine and use its own estimate. This value will be updated with the server's estimate after the first search is performed. It can then be used to calculate things like pagination.

BeforeCount

This represents the number of results to select before the target offset. We would use this only when we're not selecting the first subset of results (i.e., the target indices that are greater than zero). Added to the AfterCount, this should equal the approximate number of results in the returned VLV subset.

DirectoryVirtualListViewContext

This utility class represents the underlying context that is created when performing a VLV search. For efficiency, subsequent VLV searches should use the same context when performing subsequent searches. This is taken care of automatically using the DirectoryVirtualListView class, so developers need not concern themselves too much with this utility class.

Offset

When set by the client, this represents the index in the underlying result to approximate the search. After the server performs the search, this value is updated to represent the server's best estimate of where the target result set truly resides. As an example, if we had approximately 1,000 results and wished to retrieve the last one-third of the result set, we could specify an Offset of 667 and an AfterCount of 333.

Target

We don't always have to use the Offset when searching using a VLV. Instead, we can have a sorted result set and use a string as the index. For example, if we had 1,000 results sorted by last name (the sn attribute), we could search for all the entries starting with the word "Dunn" by specifying this string as the Target value. The number of entries determined by the AfterCount and BeforeCount would be returned surrounding the Dunn index. The Target value should always represent the attribute that was used to sort the result set.

TargetPercentage

The TargetPercentage is nothing more than a convenience to represent the Offset/ApproximateTotal. We could use this to specify things like returning the surrounding 50 entries at the 60% mark of the result set (TargetPercentage=60, AfterCount=25, BeforeCount=25). As such, this is used with Offset searches and not Target searches (though the name might be confusing).

Searching by Offset

Using code similar to that shown in Listing 5.2, we can search using the Offset tHRough a portion of the result set.

Listing 5.2. Searching by Offset

string adsPath = "LDAP://DC=domain,DC=com";

//Explicitly create our SearchRoot
DirectoryEntry searchRoot = new DirectoryEntry(
 adsPath,
 null,
 null,
 AuthenticationTypes.Secure
 );

using (searchRoot)
{
 DirectorySearcher ds = new DirectorySearcher(
 searchRoot,
 "(objectCategory=person)"
 );

 //sorting must be turned on
 ds.Sort = new SortOption(
 "cn",
 SortDirection.Descending
 );

 //grab first 50 users starting at 1st index
 ds.VirtualListView =
 new DirectoryVirtualListView(0, 50, 1);
 using (SearchResultCollection src=ds.FindAll())
 {
 Console.WriteLine("Found {0}", src.Count);

 foreach (SearchResult sr in src)
 {
 Console.WriteLine(sr.Path);
 }
 }

 Console.WriteLine(
 "Approx: {0} Found",
 ds.VirtualListView.ApproximateTotal
 );

 int offset = 50;

 //this is how we would search again using the same VLV
 while (offset < ds.VirtualListView.ApproximateTotal)
 {
 //update our offset and continue to search
 ds.VirtualListView.Offset = offset;


 using (SearchResultCollection src=ds.FindAll())
 {
 Console.WriteLine("Found {0}", src.Count);

 foreach (SearchResult sr in src)
 {
 Console.WriteLine(sr.Path);
 }
 }

 //increment our offset
 offset += 50;
 }
}

Listing 5.2 also demonstrates how we reuse the same DirectoryVirtualListView to perform additional searches while changing the Offset.

Searching by String

Another powerful option for VLV searches comes in the form of the Target property. Since we must use a server-side sort for a VLV search to work, we can specify by string value where in the sort index we would like to retrieve.

For instance, if we created an application that searched for all users in the directory by last name, this would provide an ideal use of the VLV and the Target example. Listing 5.3 shows such an example.

Listing 5.3. Searching by String

string adsPath = "LDAP://DC=domain,DC=com";

//Explicitly create our SearchRoot
DirectoryEntry searchRoot = new DirectoryEntry(
 adsPath,
 null,
 null,
 AuthenticationTypes.Secure
 );

using (searchRoot)
{
 DirectorySearcher ds = new DirectorySearcher(
 searchRoot,
 "(objectCategory=person)"
 );

 //sorting must be turned on,
 //sort by last name
 ds.Sort = new SortOption(
 "sn",
 SortDirection.Descending
 );

 //grab 50 users starting with sn="D*"
 ds.VirtualListView =
 new DirectoryVirtualListView(0, 50, "D");

 using (SearchResultCollection src=ds.FindAll())
 {
 Console.WriteLine(
 "Returning {0}",
 src.Count
 );

 foreach (SearchResult sr in src)
 {
 Console.WriteLine(sr.Path);
 }
 }
 Console.WriteLine(
 "Approx: {0} Found",
 ds.VirtualListView.ApproximateTotal
 );
}

As Listing 5.3 demonstrates, this powerful solution allows us to return a subset of a much larger result set quickly, without needing to retrieve all of the entries first. In the case of a user trying to search for other users by last name, this provides an easy mechanism to pull only enough results surrounding the Target, and it is much more efficient.

It is important to note that in both listings, we applied server-side sorting to the result set. This is a necessary step when using VLV searches, and an error will occur when sorting is not applied. Both the Target and the Offset refer to a location within a sorted result set, but with different purposes. We can use only one or the other as a basis for a starting location in our search. Finally, we should also be cognizant that the VLV is returning an estimate and not an exact match around the Offset or Target. There might be an overlap or gaps in those results if we were to try to iterate sequentially through the result set, as shown in Listing 5.2.

VLV searches provide a powerful option for SDS developers when dealing with otherwise large result sets and ad hoc queries. Thoughtful implementation of a VLV search can provide huge performance wins for both the end user and the directory servers themselves.

Note: VLV Requires Windows XP or Higher

Even though the target server may support it, as of this writing the ADSI client itself added support for VLV only as of the Windows XP version. Developing a solution on Windows XP and attempting to deploy it to a Windows 2000 application server will result in a disappointing surprise. Note that Microsoft may choose to add this feature to Windows 2000 at some point, so check the documentation for the latest information.

Searching for Deleted Objects