Query Optimization for XML

TLDR

XML is an emerging standard for web data representation, often semistructured and dynamic, which creates unique challenges for query optimization. This paper presents Lore, a DBMS for XML, focusing on its cost‑based query optimizer. Lore defines logical and physical query plans, database statistics, a cost model, and employs heuristics to enumerate plans while reducing the search space. The optimizer is fully implemented in Lore and preliminary performance results show promising improvements. This is a short version of the paper Query Optimization for Semistructured Data available at http://www-db.stanford.edu/~mchughj/publications/qo.ps.

Abstract

XML is an emerging standard for data representation and exchange on the World-Wide Web. Due to the nature of information on the Web and the inherent flexibility of XML, we expect that much of the data encoded in XML will be semistructured: the data may be irregular or incomplete, and its structure may change rapidly or unpredictable. This paper describes the query processor of Lore, a DBMS for XML-based data supporting an expressive query language. We focus primarily on Lore's cost-based query optimizer. While all of the usual problems associated with cost-based query optimization apply to XML-based query languages, a number of additional problems arise, such as new kinds of indexing, more complicated notions of database statistics, and vastly different query execution strategies for different databases. We define appropriate logical and physical query plans, database statistics, and a cost model, and we describe plan enumeration including heuristics for reducing the large search space. Our optimizer is fully implemented in Lore and preliminary performance results are reported. This is a short version of the paper Query Optimization for Semistructured Data which is available at: http://www-db.stanford.edu/~mchughj/publications/qo.ps