Multi-level operator combination in XML query processing Shurug Al-Khalifa and H. V. Jagadish   View Paper (PDF)   Return to XML query processing Abstract A core set of efficient access methods is central to the development of any database system. In the context of an XML database, there has been considerable effort devoted to defining a good set of primitive operators and inventing efficient access methods for each individual operator. These primitive operators have been defined either at the macro-level (using a "pattern tree" to specify a selection, for example) or at the micro-level (using multiple explicit containment joins to instantiate a single XPath expression).In this paper we argue that it is valuable to consider operations at each level. We do this through a study of operator merging: the development of a new access method to implement a combination of two or more primitive operators. It is frequently the case that access methods for merged operators are superior to a pipelined execution of separate access methods for each operator. We show operator merging to be valuable at both the micro-level and the macro-level. Furthermore, we show that the corresponding merged operators are hard to reason with at the other level.Specifically, we consider the influence of projections and set operations on pattern-based selections and containment joins. We show, through both analysis and extensive experimentation, the benefits of considering these operations all together. Even though our experimental verification is only with a native XML database, we have reason to believe that our results apply equally to RDBMS-based XML query engines. DiSC'03 © 2003 Association for Computing Machinery