Cost based plan selection for xpath

By Haris Georgiadis, Minas Charalambides, and Vasilis Vassalos. In SIGMOD Conference, 603–614. ACM, 2009.

Publisher Link:

http://doi.acm.org/10.1145/1559845.1559909

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.

BibTeX

@inproceedings{conf/sigmod/GeorgiadisCV09,
    author = "Georgiadis, Haris and Charalambides, Minas and
              Vassalos, Vasilis",
    editor = "Çetintemel, Ugur and Zdonik, Stanley B. and Kossmann,
              Donald and Tatbul, Nesime",
    title = "Cost based plan selection for xpath",
    booktitle = "SIGMOD Conference",
    crossref = "conf/sigmod/2009",
    ee = "http://doi.acm.org/10.1145/1559845.1559909",
    pages = "603-614",
    year = "2009",
}

@proceedings{conf/sigmod/2009,
    editor = "Çetintemel, Ugur and Zdonik, Stanley B. and Kossmann,
              Donald and Tatbul, Nesime",
    title = "Proceedings of the ACM SIGMOD International Conference on
             Management of Data, SIGMOD 2009, Providence, Rhode Island, USA,
             June 29 - July 2, 2009",
    isbn = "978-1-60558-551-2",
    publisher = "ACM",
    year = "2009",
}