MonetDB/XQuery: a fast XQuery processor powered by a relational engine

ABSTRACT

Relational XQuery systems try to re-use mature relational data management infrastructures to create fast and scalable XML database technology. This paper describes the main features, key contributions, and lessons learned while implementing such a system. Its architecture consists of (i) a range-based encoding of XML documents into relational tables, (ii) a compilation technique that translates XQuery into a basic relational algebra, (iii) a restricted (order) property-aware peephole relational query optimization strategy, and (iv) a mapping from XML update statements into relational updates. Thus, this system implements all essential XML database functionalities (rather than a single feature) such that we can learn from the full consequences of our architectural decisions. While implementing this system, we had to extend the state-of-the-art with a number of new technical contributions, such as loop-lifted staircase join and efficient relational query evaluation strategies for XQuery theta-joins with existential semantics. These contributions as well as the architectural lessons learned are also deemed valuable for other relational back-end engines. The performance and scalability of the resulting system is evaluated on the XMark benchmark up to data sizes of 11GB. The performance section also provides an extensive benchmark comparison of all major XMark results published previously, which confirm that the goal of purely relational XQuery processing, namely speed and scalability, was met.

REFERENCES

• 1: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 2: Berkeley DB XML. http://www.sleepycat.com/products/bdbxml.html.
• 3: Kevin Beyer , Roberta J. Cochrane , Vanja Josifovski , Jim Kleewein , George Lapis , Guy Lohman , Bob Lyle , Fatma Özcan , Hamid Pirahesh , Normen Seemann , Tuong Truong , Bert Van der Linden , Brian Vickery , Chun Zhang, System RX: one part relational, one part XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066197]
• 4: P. Boncz. Monet: A Next-Generation DBMS Kernel For Query-Intensive Applications. PhD thesis, UVA, 2002.
• 5: P. Boncz et al. Pathfinder: Relational XQuery Over Multi-Gigabyte XML Inputs In Interactive Time. Technical Report INS-E0503, CWI, 2005.
• 6: P. Boncz, S. Manegold, and J. Rittinger. Updating the Pre/Post Plane in MonetDB/XQuery. In XIME-P, 2005.
• 7: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 8: Peter Buneman , Byron Choi , Wenfei Fan , Robert Hutchison , Robert Mann , Stratis D. Viglas, Vectorizing and Querying Large XML Repositories, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.261-272, April 05-08, 2005 [doi>10.1109/ICDE.2005.150]
• 9: M. Carey, D. Florescu, Z. Ives, Y. Lu, S. J., E. Shekita, and S. S. XPERANTO: Publishing Object-Relational Data as XML. In WebDB, 2000.
• 10: D. Chamberlin, D. Florescu, and J. Robie. XQuery Update Facility. W3C, 2006. http://www.w3.org/TR/xqupdate/.
• 11: Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543648]
• 12: David DeHaan , David Toman , Mariano P. Consens , M. Tamer Özsu, A comprehensive XQuery to SQL translation using dynamic interval encoding, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872832]
• 13: A. Deutsch and V. Tannen. MARS: A System for Publishing XML from Mixed and Redundant Storage. In VLDB Conf., 2003.
• 14: M. Fernández, J. Siméon, B. Choi, A. Marian, and G. Sur. Implementing XQuery 1.0: The Galax Experience. In VLDB Conf., 2003.
• 15: D. Florescu et al. The BEA/XQRL Streaming XQuery Processor. In VLDB Conf., 2003.
• 16: T. Grust. Purely Relational FLWORs. In Proc. XIME-P, 2005.
• 17: T. Grust, S. Sakr, and J. Teubner. XQuery on SQL Hosts. In VLDB Conf., 2004.
• 18: T. Grust, M. van Keulen, and J. Teubner. Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. In VLDB Conf., 2003.
• 19: Torsten Grust , Maurice Van Keulen , Jens Teubner, Accelerating XPath evaluation in any RDBMS, ACM Transactions on Database Systems (TODS), v.29 n.1, p.91-131, March 2004 [doi>10.1145/974750.974754]
• 20: IPSI-XQ. http://ipsi.fhg.de/oasys/projects/ipsi-xq/.
• 21: Vanja Josifovski , Marcus Fontoura , Attila Barta, Querying XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.197-210, April 2005 [doi>10.1007/s00778-004-0123-7]
• 22: C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier. Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams. In VLDB Conf., 2004.
• 23: R. Krishnamurthy, R. Kaushik, and J. Naughton. XML-to-SQL Query Translation Literature: The State of the Art and Open Problems. In Proc. XSym, 2003.
• 24: Kweelt. http://kweelt.sourceforge.net/.
• 25: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 26: Xiaogang Li , Gagan Agrawal, Efficient evaluation of XQuery over streaming data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 27: Zhen Hua Liu , Muralidhar Krishnaprasad , Vikas Arora, Native Xquery processing in oracle XMLDB, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066259]
• 28: Wolfgang Meier, eXist: An Open Source Native XML Database, Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Systems, p.169-183, October 07-10, 2002
• 29: G. Moerkotte and T. Neumann. A Combined Framework for Grouping and Order Optimization. In VLDB Conf., 2004.
• 30: Patrick O'Neil , Elizabeth O'Neil , Shankar Pal , Istvan Cseri , Gideon Schaller , Nigel Westbury, ORDPATHs: insert-friendly XML node labels, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007686]
• 31: Shankar Pal , Istvan Cseri , Oliver Seeliger , Michael Rys , Gideon Schaller , Wei Yu , Dragan Tomic , Adrian Baras , Brandon Berg , Denis Churin , Eugene Kogan, XQuery implementation in a relational database system, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 32: Stelios Paparizos , H. V. Jagadish, Pattern tree algebras: sets or sequences?, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 33: Qizx/open. http://www.xfra.net/qizxopen/.
• 34: QuiP. http://developer.softwareag.com/tamino/quip/.
• 35: Saxon. http://saxon.sourceforge.net/.
• 36: A. Schmidt, F. Waas, M. Kersten, M. Carey, I. Manolescu, and R. Busse. XMark: A Benchmark for XML Data Management. In VLDB Conf., 2002.
• 37: David Simmen , Eugene Shekita , Timothy Malkemus, Fundamental techniques for order optimization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.57-67, June 04-06, 1996, Montreal, Quebec, Canada
• 38: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 39: X. Wang and M. Cherniack. Avoiding Sorting and Grouping in Processing Queries. In VLDB Conf., 2003.
• 40: X-Hive/DB. http://www.x-hive.com/.
• 41: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
RDBMS, XML, XQuery, performance, relational XQuery systems, scalability