Cost-sensitive reordering of navigational primitives

ABSTRACT

We present a method to evaluate path queries based on the novel concept of partial path instances. Our method (1) maximizes performance by means of sequential scans or asynchronous I/O, (2) does not require a special storage format, (3) relies on simple navigational primitives on trees, and (4) can be complemented by existing logical and physical optimizations such as duplicate elimination, duplicate prevention and path rewriting.We use a physical algebra which separates those navigation operations that require I/O from those that do not. All I/O operations necessary for the evaluation of a path are isolated in a single operator, which may employ efficient I/O scheduling strategies such as sequential scans or asynchronous I/O.Performance results for queries from the XMark benchmark show that reordering the navigation operations can increase performance up to a factor of four.

REFERENCES

• 1: C. Beeri and Y. Tzaban. SAL: An algebra for semistructured data and xml. In WebDB (Informal Proceedings), pages 37--42, 1999.
• 2: S. Boag, D. Chamberlin, M. Fernandez, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu. XQuery 1.0: An XML query language. Technical report, World Wide Web Consortium, 2002. W3C Working Draft 30 April 2002.
• 3: 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 (ICDE'05), p.705-716, April 05-08, 2005 [doi>10.1109/ICDE.2005.69]
• 4: 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]
• 5: 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]
• 6: J. Clark. XSL transformations (XSLT) version 1.0. Technical report, World Wide Web Consortium (W3C), November 1999.
• 7: J. Clark and S. DeRose. XML path language (XPath) version 1.0. Technical report, World Wide Web Consortium (W3C) Recommendation, 1999.
• 8: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 9: T. Fiebig , S. Helmer , C.-C. Kanne , G. Moerkotte , J. Neumann , R. Schiele , T. Westmann, Anatomy of a native XML base management system, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.292-314, December 2002 [doi>10.1007/s00778-002-0080-y]
• 10: G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In VLDB Conf., pages 95--106, 2002.
• 11: G. Gottlob, C. Koch, and R. Pichler. Xpath query evaluation Improving time and space efficiency. In ICDE, pages 379--390, 2003.
• 12: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 13: 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]
• 14: J. Hidders and P. Michiels. Avoiding unnecessary ordering operations in xpath. In DBLP, pages 54--74, 2003.
• 15: Tom Keller , Goetz Graefe , David Maier, Efficient assembly for complex objects, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.148-157, May 29-31, 1991, Denver, Colorado, United States
• 16: Alfons Kemper , Donald Kossmann, Dual-Buffering Strategies in Object Bases, Proceedings of the 20th International Conference on Very Large Data Bases, p.427-438, September 12-15, 1994
• 17: Alfons Kemper , Guido Moerkotte, Advanced query processing in object bases using access support relations, Proceedings of the sixteenth international conference on Very large databases, p.290-301, September 1990, Brisbane, Australia
• 18: C. Koch. Efficient processing of expressive node-selecting queries on xml data in secondary storage: A tree automata-based approach. In VLDB Conf., pages 249--260, 2003
• 19: J. Eliot B. Moss, Working with Persistent Objects: To Swizzle or Not to Swizzle, IEEE Transactions on Software Engineering, v.18 n.8, p.657-673, August 1992 [doi>10.1109/32.153378]
• 20: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 21: 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]
• 22: A. Schmidt, F. Waas, M. Kersten, M. J. Carey, I. Manolescu, and R. Busse. Xmark: A benchmark for xml data management. In VLDB Conf., pages 974--985, 2002.
• 23: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 24: S. A.-K. Shurug, H. V. Jagadish, J. M. Patel, Y. Wu, N. Koudas, and D. Srivastava. Structural joins: A primitive for efficient xml query pattern matching. In ICDE, pages 141--152, 2003.
• 25: Zhaohui Xie , Jiawei Han, Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.522-533, September 12-15, 1994