Dependable cardinality forecasts for XQuery

ABSTRACT

Though inevitable for effective cost-based query rewriting, the derivation of meaningful cardinality estimates has remained a notoriously hard problem in the context of XQuery. By basing the estimation on a relational representation of the XQuery syntax, we show how existing cardinality estimation techniques for XPath and proven relational estimation machinery can play together to yield dependable forecasts for arbitrary XQuery (sub)expressions. Our approach benefits from a light-weight form of data flow analysis. Abstract domain identifiers guide our query analyzer through the estimation process and allow for informed decisions even in case of deeply nested XQuery expressions. A variant of projection paths [15] provides a versatile interface into which existing techniques for XPath cardinality estimation can be plugged in seamlessly. We demonstrate an implementation of this interface based on data guides. Experiments show how our approach can equally cope with both, structure-and value-based queries. It is robust with respect to intermediate estimation errors, from which we typically found our implementation to recover gracefully.

REFERENCES

• 1: Ashraf Aboulnaga , Alaa R. Alameldeen , Jeffrey F. Naughton, Estimating the Selectivity of XML Path Expressions for Internet Scale Applications, Proceedings of the 27th International Conference on Very Large Data Bases, p.591-600, September 11-14, 2001
• 2: A. Balmin , T. Eliaz , J. Hornibrook , L. Lim , G. M. Lohman , D. Simmen , M. Wang , C. Zhang, Cost-based optimization in DB2 XML, IBM Systems Journal, v.45 n.2, p.299-319, January 2006
• 3: D. Berleant. Automatically Verified Reasoning with Both Intervals and Probability Density Functions. Interval Computations, No. 2, 1993.
• 4: S. Boag, D. Chamberlin, M. F. Fernández, D. Florescu, J. Robie, and J. Siméon. XQuery 1.0: An XML Query Language. W3C Recommendation, 2007.
• 5: Peter Boncz , Torsten Grust , Maurice van Keulen , Stefan Manegold , Jan Rittinger , Jens Teubner, MonetDB/XQuery: a fast XQuery processor powered by a relational engine, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142527]
• 6: Don Chamberlin, Peter Fankhauser, Daniela Florescu, Massimo Marchiori, and Jonathan Robie. XML Query Use Cases. W3C Working Group Note, 2007.
• 7: D. Draper, P. Fankhauser, M. F. Fernández, A. Malhotra, K. Rose, M. Rys, J. Siméon, and P. Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Recommendation, 2007.
• 8: D. K. Fisher and S. Maneth. Structural Selectivity Estimation for XML Documents. In Proc. ICDE, 2007.
• 9: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 10: T. Grust. Purely Relational FLWORs. In Proc. XIME-P, 2005.
• 11: Torsten Grust , Sherif Sakr , Jens Teubner, XQuery on SQL hosts, Proceedings of the Thirtieth international conference on Very large data bases, p.252-263, August 31-September 03, 2004, Toronto, Canada
• 12: T. Grust and J. Teubner. Relational Algebra: Mother Tongue---XQuery: Fluent. In Proc. of the 1st Twente Data Management Workshop (TDM), 2004.
• 13: International Business Machines Corp. (IBM). DB2 Version 9 XML Guide, 2006.
• 14: Hanyu Li , Mong Li Lee , Wynne Hsu , Gao Cong, An Estimation System for XPath Expressions, Proceedings of the 22nd International Conference on Data Engineering, p.54, April 03-07, 2006 [doi>10.1109/ICDE.2006.19]
• 15: Amélie Marian , Jérôme Siméon, Projecting XML documents, Proceedings of the 29th international conference on Very large data bases, p.213-224, September 09-12, 2003, Berlin, Germany
• 16: Neoklis Polyzotis , Minos Garofalakis, XSKETCH synopses for XML data graphs, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1014-1063, September 2006 [doi>10.1145/1166074.1166082]
• 17: Naveen Reddy , Jayant R. Haritsa, Analyzing plan diagrams of database query optimizers, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 18: C. Sartiani. A General Framework for Estimating XML Query Cardinality. In Proc. DBPL, 2003.
• 19: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 20: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance