Publication Details

Title

Dependable Cardinality Forecasts for XQuery

Authors

Jens Teubner, Torsten Grust, Sebastian Maneth, and Sherif Sakr

Published

Proceedings of the VLDB Endowment (PVLDB), vol. 1(1), Auckland, New Zealand, August 2008

Download

paper (PDF), presentation slides (PDF), code (.tar.gz)

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 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.

Publication Log

June 2008

camera-ready for VLDB 2008

• camera-ready paper (PDF)
• list of changes (TXT) (as mandated by the VLDB 2008 camera-ready guidelines)

March 2008

submission to VLDB 2008 (accepted)

• submission (PDF)
• reviews (rating: weak accept, accept, accept)