Signs on the Sand

Here I go again with another experimental creature from my XML Bestiary: IndexingXPathNavigator. This one was inspired by Mark Fussell's "Indexing XML, XML ids and a better GetElementByID method on the XmlDocument class". I've been experimenting with Mark's extended XmlDocument, played a bit with XPathDocument and "idkey()" extension function Mark was talking about. Finally I came to a conclusion that 1)XPath is the way to go (that' not the first time I say it, right? :) and thus what should be extended is XPathNavigator; 2)no need to reinvent the wheel as XSLT's keys is proved excellent stuff.
That is what IndexingXPathNavigator is - XPathNavigator, augmented with XSLT keys functionality: it supports declaring keys, lazy or eager indexing and retriving indexed nodes via key() function all as per familiar and proved XSLT semantics.

Intro

IndexingXPathNavigator is a wrapper around any XPathNavigator, augmenting it with indexing functionality. Such architecture allows seamless indexing of any IXPathNavigable XML store, such as XPathDocument, XmlDocument or XmlDataDocument. The overall semantics behind should be very familiar to any developer acquainted with XSLT as IndexingXPathNavigator behavior literally follows XSLT 1.0 specification.

The main scenario when IndexingXPathNavigator is meant to be used is uniform repetitive XPath selections from loaded in-memory XML document, such as selecting orders by orderID from an XmlDocument. Using IndexingXPathNavigator with preindexed selections allows drastically decrease selection time and to achieve O(n) perf.

How it works

First one have to declare keys, according to which the indexing occurs. This is done using
IndexingXPathNavigator.AddKey(string keyname, string match, string use) method, where
keyname is the name of the key,
match is an XPath pattern, defining the nodes to which this key is applicable and
use is an XPath expression used to determine the value of the key for each matching node.
E.g. to index XML document by "id" attribute value, one can declare a key, named "idKey" as follows: AddKey("idKey", "*", "@id"). This method works identically to XSLT's <xsl:key> instruction. Essentially a key can be thought as a collection of node-value pairs. During indexing IndexingXPathNavigator builds a Hashtable for each named key, which contains nodes and associated values and allows to retrieve nodes by key value. You may define as many keys as you need including keys with the same name.

After all keys are declared, IndexingXPathNavigator is ready for indexing. Indexing process is performed as follows - each node in XML document is matched against all key definitions. For each matching node, key value is calculated and this node-value pair is added into appropriate Hashtable. As can be seen indexing is not a cheap operation, it involves walking through the whole XML tree, multiple node matching and XPath expression evaluating. That's the usual indexing price. Indexing can be done in either lazy (first access time) or eager (before any selections) manner.

After indexing IndexingXPathNavigator is ready for node retrieving. IndexingXPathNavigator augments XPath with standard XSLT's key(string keyname, object keyValue) function, which allows to retrieve nodes directly from built indexes (Hashtables) by key value. The function is implemented as per XSLT spec.

Usage sample

Here is common usage pattern, which I used also to test the performance of the IndexingXPathNavigator. There is an XML document, northwind.xml, which is XML version of the Northwind database. It contains lots of orders, each one consisting of order ID, order date and shipping address:

<Item>
  <OrderID> 10952</OrderID>
  <OrderDate> 4/15/96</OrderDate>
  <ShipAddress> Obere Str. 57</ShipAddress>
</Item>

The aim is to select shipping address for an order by order ID. Here is how it can be implemented with IndexingXPathNavigator:

XPathDocument doc = new XPathDocument("test/northwind.xml");
IndexingXPathNavigator inav = new IndexingXPathNavigator(
  doc.CreateNavigator());
//Declare a key named "orderKey", which matches Item elements and 
//whose key value is value of child OrderID element
inav.AddKey("orderKey", "OrderIDs/Item", "OrderID"); 
//Indexing
inav.BuildIndexes();
//Selection
XPathNodeIterator ni =  nav.Select("key('orderKey', ' 10330')/ShipAddress");
while (ni.MoveNext())
  Console.WriteLine(ni.Current.Value);

Performance test

Here are results of my testing. northwind.xml is 240Kb and contains 830 orders. I'm searching shipping address for an order, whose OrderID is 10330 (it's almost in the middle of the XML document) using regular XPathNavigator and IndexingXPathNavigator (code above, full code in the download). My PC is 533MHz/256M RAM Win2K box, here are the results:

Loading XML document: 167.12 ms
Regular selection, warming...
Regular selection: 1000 times, total time 5371.79 ms, 1000 nodes selected
Regular selection, testing...
Regular selection: 1000 times, total time 5181.80 ms, 1000 nodes selected
Building IndexingXPathNavigator:   1.03 ms
Adding keys:   5.16 ms
Indexing:  58.21 ms
Indexed selection, warming...
Indexed selection: 1000 times, total time 515.90 ms, 1000 nodes selected
Indexed selection, testing...
Indexed selection: 1000 times, total time 476.06 ms, 1000 nodes selected

As can be seen, average selection time for regular XPath selection is 5.181 ms, while for indexed selection it's 0.476 ms. One order of magnitude faster! Note additionally that XML document is very simple and regular and I used /ROOT/CustomerIDs/OrderIDs/Item[OrderID=' 10330']/ShipAddress XPath for regular selection, which is almost linear search and is probably the most effective from XPath point of view. With more complex XML structure and XPath expressions such as //Item[OrderID=' 10330']/ShipAddress the difference would be even more striking.

Download

I wanted to make IndexingXPathNavigator a subproject of MVP XML library, but failed. I forgot I can't work with CVS over SSH from my work due to closed SSH port. Grrrmm. Ok, after all it's experimental implementation. Let's see if there will be any substantial feedback first.

Full source code along with perf testing. As usual two download locations available: local one and from GotDotNet (will update later). IndexingXPathNavigator homepage is http://www.tkachenko.com/dotnet/IndexingXPathNavigator.html.

---

I really like this one. Probably that's what my next article is going to be about. What do you think? I'm cap in hand waiting for comments.