Cost based plan selection for xpath

ABSTRACT

We present a complete XPath cost-based optimization and execution framework and demonstrate its effectiveness and efficiency for a variety of queries and datasets. The framework is based on a logical XPath algebra with novel features and operators and a comprehensive set of rewriting rules that together enable us to algebraically capture many existing and novel processing strategies for XPath queries. An important part of the framework is PSA, a very efficient cost-based plan selection algorithm for XPath queries. In the presented experimental evaluation, PSA picked the cheapest estimated query plan in 100% of the cases. Our cost-based query optimizer independent of the underlying physical data model and storage system and of the available logical operator implementations, depending on a set of well-defined APIs. We also present an implementation of those APIs, including primitive access methods, a large pool of physical operators, statistics estimators and cost models, and experimentally demonstrate the effectiveness of our end-to-end query optimization system.

REFERENCES

• 1: Matthias Brantner , Sven Helmer , Carl-Christian Kanne , Guido Moerkotte, Full-Fledged Algebraic XPath Processing in Natix, Proceedings of the 21st International Conference on Data Engineering, p.705-716, April 05-08, 2005 [doi>10.1109/ICDE.2005.69]
• 2: Matthias Brantner , Carl-Christian Kanne , Guido Moerkotte , Sven Helmer, Algebraic Optimization of Nested XPath Expressions, Proceedings of the 22nd International Conference on Data Engineering, p.128, April 03-07, 2006 [doi>10.1109/ICDE.2006.15]
• 3: GALAX System. Available: http://db.bell-labs.com/galax/
• 4: Stelios Paparizos , Shurug Al-Khalifa , Adriane Chapman , H. V. Jagadish , Laks V. S. Lakshmanan , Andrew Nierman , Jignesh M. Patel , Divesh Srivastava , Nuwee Wiwatwattana , Yuqing Wu , Cong Yu, TIMBER: a native system for querying XML, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872862]
• 5: Venkatesh Raghavan , Kurt Deschler , Elke A. Rundensteiner, VAMANA - A Scalable Cost-Driven XPath Engine, Proceedings of the 21st International Conference on Data Engineering Workshops, p.1278, April 05-08, 2005 [doi>10.1109/ICDE.2005.303]
• 6: 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
• 7: 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]
• 8: Neoklis Polyzotis , Minos Garofalakis , Yannis Ioannidis, Selectivity Estimation for XML Twigs, Proceedings of the 20th International Conference on Data Engineering, p.264, March 30-April 02, 2004
• 9: J. Filho, T. Härder: Statistics for Cost-Based XML Query Optimization. Grundlagen von Datenbanken (2006)
• 10: Christian Mathis , Andreas M. Weiner , Theo Härder , Caesar Ralf Franz Hoppen, XTCcmp: XQuery compilation on XTC, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454183]
• 11: Haris Georgiadis , Vasilis Vassalos, Xpath on steroids: exploiting relational engines for xpath performance, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247517]
• 12: Torsten Grust , Maurice van Keulen , Jens Teubner, Staircase join: teach a relational DBMS to watch its (axis) steps, Proceedings of the 29th international conference on Very large data bases, p.524-535, September 09-12, 2003, Berlin, Germany
• 13: 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]
• 14: Torsten Grust, Accelerating XPath location steps, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564705]
• 15: 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]
• 16: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 17: Neoklis Polyzotis , Minos Garofalakis , Yannis Ioannidis, Selectivity Estimation for XML Twigs, Proceedings of the 20th International Conference on Data Engineering, p.264, March 30-April 02, 2004
• 18: C. Mathis: Integrating Structural Joins into a Tuple-Based XPath Algebra. BTW 2007:pp 242--261
• 19: Christopher Re , Jerome Simeon , Mary Fernandez, A Complete and Efficient Algebraic Compiler for XQuery, Proceedings of the 22nd International Conference on Data Engineering, p.14, April 03-07, 2006 [doi>10.1109/ICDE.2006.6]
• 20: 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
• 21: XML Data Repository, at www.cs.washington.edu/research/
• 22: Torsten Grust , Jan Rittinger , Jens Teubner, Why off-the-shelf RDBMSs are better at XPath than you might expect, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247591]
• 23: 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]
• 24: N. Tang, J. Xu Yu, et al: Fast Structural Join with a Location Function. Proc. DASFAA: pp777--786 (2006).
• 25: H. Jiang, H. Lu, et al: XR-Tree: Indexing XML Data for Efficient Structural Joins. Proc. ICDE: pp 253--263 (2003)
• 26: Shankar Pal , Istvan Cseri , Oliver Seeliger , Gideon Schaller , Leo Giakoumakis , Vasili Zolotov, Indexing XML data stored in a relational database, Proceedings of the Thirtieth international conference on Very large data bases, p.1146-1157, August 31-September 03, 2004, Toronto, Canada
• 27: Jiaheng Lu , Tok Wang Ling , Chee-Yong Chan , Ting Chen, From region encoding to extended dewey: on efficient processing of XML twig pattern matching, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 28: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]
• 29: Wei Wang , Haifeng Jiang , Hongzhi Wang , Xuemin Lin , Hongjun Lu , Jianzhong Li, Efficient processing of XML path queries using the disk-based F&B Index, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 30: Shu-Yao Chien , Zografoula Vagena , Donghui Zhang , Vassilis J. Tsotras , Carlo Zaniolo, Efficient structural joins on indexed XML documents, Proceedings of the 28th international conference on Very Large Data Bases, p.263-274, August 20-23, 2002, Hong Kong, China
• 31: Daniela Florescu , Chris Hillery , Donald Kossmann , Paul Lucas , Fabio Riccardi , Till Westmann , J. Carey , Arvind Sundararajan, The BEA streaming XQuery processor, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.294-315, September 2004 [doi>10.1007/s00778-004-0137-1]
• 32: H. Georgiadis, M. Charalambides, V. Vassalos: Novel Operators for Efficient XPath Execution, Submitted for publication. Available at http://wim.aueb.gr/novOp.pdf
• 33: Haris Georgiadis , Minas Charalambides , Vasilis Vassalos, Cost based plan selection for xpath, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559909]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.9 Management

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Languages, Measurement, Performance

Keywords:
algebraic rewritings, cardinality estimation, cost models, cost-based optimization, xml, xpath