Hint and run: accelerating XPath queries

XML documents are often represented as DOM structures or trees. In some instances, due to the complexity of queries, XPath queries are better evaluated by traversing these structures rather than using summarization indexes. A requirement for the optimization of document navigation, is to efficiently decrease the number of traversed nodes. The optimization task is more difficult when the query framework allows a syntax that enlarges the search space, such as wildcards and descendant queries. To reduce the overhead of query processing, many database systems supporting XML rely on indexes. Such indexes are typically not able to adapt to memory restrictions or workload changes. A secondary data structure that uses little storage space and tunes itself to address hot spots in processing, can therefore be beneficial. In this paper, we propose a first method for creating, using, and maintaining selective signatures called hints to aid in the navigation of XML documents. Hints form a flexible data structure for pruning the search space, that can be used on its own or it can complement existing indexes. The amount of hints used is variable, and it depends on the storage limitation set a priori, and on the efficiency of the hints. Our experiments show that hints can improve the efficiency of navigational XML query processing by a large margin while using only little extra memory.