Optimizing cursor movement in Holistic twig joins

Holistic twig join algorithms represent the state of the art for evaluating path expressions in XML queries. Using inverted indexes on XML elements, holistic twig joins move a set of index cursors in a coordinated way to quickly find structural matches. Because each cursor move can trigger I/O, the performance of a holistic twig join is largely determined by how many cursor moves it makes, yet, surprisingly, existing join algorithms have not been optimized along these lines. In this paper, we describe TwigOptimal, a new holistic twig join algorithm with optimal cursor movement. We sketch the proof of TwigOptimal's optimality, and describe how Twig Optimal can use information in the return clause of XQuery to boost its performance. Finally, experimental results are presented, showing Twig Optimal's superiority over existing holistic twig join algorithms. Copyright 2005 ACM.