ROX: run-time optimization of XQueries

ABSTRACT

Optimization of complex XQueries combining many XPath steps and joins is currently hindered by the absence of good cardinality estimation and cost models for XQuery. Additionally, the state-of-the-art of even relational query optimization still struggles to cope with cost model estimation errors that increase with plan size, as well as with the effect of correlated joins and selections.

In this research, we propose to radically depart from the traditional path of separating the query compilation and query execution phases, by having the optimizer execute, materialize partial results, and use sampling based estimation techniques to observe the characteristics of intermediates. The proposed technique takes as input a Join Graph where the edges are either equi-joins or XPath steps, and the execution environment provides value- and structural-join algorithms, as well as structural and value-based indices.

While run-time optimization with sampling removes many of the vulnerabilities of classical optimizers, it brings its own challenges with respect to keeping resource usage under control, both with respect to the materialization of intermediates, as well as the cost of plan exploration using sampling. Our approach deals with these issues by limiting the run-time search space to so-called "zero-investment algorithms for which sampling can be guaranteed to be strictly linear in sample size. All operators and XML value indices used by ROX for sampling have the zero-investment property.

We perform extensive experimental evaluation on large XML datasets that shows that our run-time query optimizer finds good query plans in a robust fashion and has limited run-time overhead.

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: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 3: Brian Babcock , Surajit Chaudhuri, Towards a robust query optimizer: a principled and practical approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066172]
• 4: 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]
• 5: Nicolas Bruno , Surajit Chaudhuri, Exploiting statistics on query expressions for optimization, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564722]
• 6: 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]
• 7: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: Zhiyuan Chen , H. V. Jagadish , Flip Korn , Nick Koudas , S. Muthukrishnan , Raymond T. Ng , Divesh Srivastava, Counting Twig Matches in a Tree, Proceedings of the 17th International Conference on Data Engineering, p.595-604, April 02-06, 2001
• 9: Francis Chu , Joseph Halpern , Johannes Gehrke, Least expected cost query optimization: what can we expect?, 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.543651]
• 10: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 11: Amol Deshpande , Carlos Guestrin , Wei Hong , Samuel Madden, Exploiting Correlated Attributes in Acquisitional Query Processing, Proceedings of the 21st International Conference on Data Engineering, p.143-154, April 05-08, 2005 [doi>10.1109/ICDE.2005.63]
• 12: Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007 [doi>10.1561/1900000001]
• 13: D. Fisher and S. Maneth. Structural Selectivity Estimation for XML Documents. In ICDE, 2007.
• 14: Juliana Freire , Jayant R. Haritsa , Maya Ramanath , Prasan Roy , Jérôme Siméon, StatiX: making XML count, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564713]
• 15: 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
• 16: G. Graefe , K. Ward, Dynamic query evaluation plans, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.358-366, June 1989, Portland, Oregon, United States
• 17: T. Grust. Purely Relational FLWORs. In XIME-P, 2005
• 18: T. Grust, M. Mayr, and J. Rittinger. XQuery Join Graph Isolation. In ICDE, 2009. arXiv:0810.4809.
• 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: Peter J. Haas , Fabian Hueske , Volker Markl, Detecting attribute dependencies from query feedback, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 21: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996 [doi>10.1006/jcss.1996.0041]
• 22: J. Hidders, P. Michiels, J. Siméon, and R. Vercammen. How To Recognize Different Kinds of Tree Patterns from Quite a Long Way Away. In PLAN-X, 2007.
• 23: Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
• 24: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 25: Volker Markl , Vijayshankar Raman , David Simmen , Guy Lohman , Hamid Pirahesh , Miso Cilimdzic, Robust query processing through progressive optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007642]
• 26: F. Olken and D. Rotem. Random Sampling from Databases -A Survey. Statistics and Computing, 5:25--42, 1995.
• 27: 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]
• 28: Neoklis Polyzotis , Minos Garofalakis , Yannis Ioannidis, Approximate XML query answers, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007599]
• 29: S. Seshadri, Probabilistic methods in query processing, University of Wisconsin at Madison, Madison, WI, 1992
• 30: Wei Wang , Haifeng Jiang , Hongjun Lu , Jeffrey Xu Yu, Bloom histogram: path selectivity estimation for XML data with updates, Proceedings of the Thirtieth international conference on Very large data bases, p.240-251, August 31-September 03, 2004, Toronto, Canada
• 31: Yuqing Wu , Jignesh M. Patel , H. V. Jagadish, Estimating Answer Sizes for XML Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.590-608, March 25-27, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
optimization, xml, xquery