re: Querying LINQ to XML Nodes in Reverse Document Order with Better Performance

Rick Jelliffe — Fri, 26 Jun 2009 07:22:11 GMT

You say "The need to process nodes in reverse document order is rare" but that is only if you remove the scenario of processing documents from what people do with XML.

Database people have seemed congenitally certain that whatever they need is all that document processing people need. But it isn't so.

In XML, you can write that an element X has a label Y with a value Z as

</container>

and so on.

So the heuristic for XML processing systems should not be that "forward axis is normal, other axes are weird" but rather something like "processing one element requires accessing other elements in inverse proportion to their degree of separation."

Indeed, you could classify documents, schemas and programs by the degrees of separation (XPath location steps needed to process each node.) I would guess an average (mode) of 2 for HTML, 4 for ODF and 5 for OOXML.

re: Querying LINQ to XML Nodes in Reverse Document Order with Better Performance

EricWhite — Fri, 26 Jun 2009 23:45:48 GMT

Hi Rick,

I believe that you are right that 'document-centric' XML tree processing is the scenario that requires the most from XML processing systems, including the ability to process nodes in reverse document order. I certainly agree that document-centric XML processing requires more interesting axes than database scenarios. I can't comment on ODF - I'm not an expert - but certainly there are places in Open XML that require quite a few (4-5) XPath location steps to process nodes.

Regarding the decision of the designers of LINQ to XML to not include a doubly linked list for nodes, I believe it is a good one. I've written a lot of LINQ to XML queries over Open XML documents, and til now, there have been only one or two scenarios that require reverse document order queries that perform well. I just counted the nodes of one of my largest Open XML documents - it contains > 2,400,000 XML nodes in the main document part. If there were a previous sibling node link in each node, then this would consume 8 meg that wouldn't be often used. In addition, maintaining previous nodes would add additional processing burden - not a lot, but it adds up.

But as seen here, it is trivial to add reverse document order axes that perform well. We only need to enable them for the few scenarios where we actually need them.

-Eric