ROX: The Robustness of a Run-time XQuery Optimizer Against Correlated Data

R. Abdel Kader, Peter Boncz, Stefan Manegold, Maurice van Keulen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
86 Downloads (Pure)

Abstract

We demonstrate ROX, a run-time optimizer of XQueries, that focuses on finding the best execution order of XPath steps and relational joins in an XQuery. The problem of join ordering has been extensively researched, but the proposed techniques are still unsatisfying. These either rely on a cost model which might result in inaccurate estimations, or explore only a restrictive number of plans from the search space. ROX is developed to tackle these problems. ROX does not need any cost model, and defers query optimization to run-time intertwining optimization and execution steps. In every optimization step, sampling techniques are used to estimate the cardinality of unexecuted steps and joins to make a decision which sequence of operators to process next. Consequently, each execution step will provide updated and accurate knowledge about intermediate results, which will be used during the next optimization round. This demonstration will focus on: (i) illustrating the steps that ROX follows and the decisions it makes to choose a good join order, (ii) showing ROX’s robustness in the face of data with different degree of correlation, (iii) comparing the performance of the plan chosen by ROX to different plans picked from the search space, (iv) proving that the run-time overhead needed by ROX is restricted to a small fraction of the execution time.
Original languageUndefined
Title of host publicationProceedings of the 26th International Conference on Data Engineering (ICDE2010)
Place of PublicationLos Alamitos
PublisherIEEE
Pages1185-1188
Number of pages4
ISBN (Print)978-1-4244-5444-0
DOIs
Publication statusPublished - Mar 2010
Event26th International Conference on Data Engineering, ICDE 2010 - Long Beach, United States
Duration: 1 Mar 20106 Mar 2010
Conference number: 26

Publication series

Name
PublisherIEEE Computer Society Press

Conference

Conference26th International Conference on Data Engineering, ICDE 2010
Abbreviated titleICDE
Country/TerritoryUnited States
CityLong Beach
Period1/03/106/03/10

Keywords

  • METIS-270690
  • DB-XMLDB: XML DATABASES
  • EWI-16035
  • IR-67868

Cite this