Pathfinder: A Relational Query Optimizer Explores XQuery Terrain.
Jan Rittinger, Jens Teubner, Torsten Grust · 2007
Relational encodings of the static aspects of the XQuery data model, i.e., tabular representations for XML documents and ordered sequences of items, are widely used today. Since 2002, the Pathfinder and MonetDB/XQuery companion projects [BGvK + 06] pursue the primary goal to also embrace the complete dynamic semantics of XQuery (expression evaluation and runtime aspects) with the help of relational database systems. In earlier work [GT04], we have shown that relational algebra makes for a suitable target language in an XQuery compiler. This purely relational approach to XQuery inherits the scalability advantages of the underlying relational database back-end and makes proven optimization techniques immediately applicable to the construction of XQuery processors. MonetDB/XQuery, an open-source system that implements this approach, is found among the fastest and most scalable XQuery processors available today [BGvK + 06]. This is a demonstration of the relational optimizer of Pathfinder 1, the query compiler behind MonetDB/XQuery. To account for the significant size and unusual shape of the relational query plans (see Figure 1) derived from input XQuery expressions, Pathfinder implements various optimization techniques in a peephole-style fashion and provides support for graph-shaped plans from the ground up. 2 Relational Query Optimization in an XQuery Compiler Pathfinder’s XQuery compiler turns incoming XQuery expressions into relational query plans according to the loop-lifting compilation strategy we devised in [GT04]. In a nutshell, loop-lifting trades iteration (esp. the XQuery FLWOR construct) for efficient bulkoriented processing. The compiler emits expressions of a relational algebra whose operators have been chosen to match the actual capabilities of modern SQL query engines. A few representative operators are shown in Table 1 (note that non-standard operators like the XPath step join ¢ are synonyms for relational “micro-plans ” with an optimized implementation in Pathfinder’s back-end database system MonetDB). 1 MonetDB/XQuery and Pathfinder are available via