MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Single phase construction of optimal DAG-structured QEPs

Neumann, Thomas and Moerkotte, Guido

July 2008, 73 pages.

Status: available - back from printing

Traditionally, database management systems use tree-structured query evaluation plans. They are easy to implement but not expressive enough for some optimizations like eliminating common algebraic subexpressions or magic sets. These require directed acyclic graphs (DAGs), i.e. shared subplans. Existing approaches consider DAGs merely for special cases and not in full generality. We introduce a novel framework to reason about sharing of subplans and, thus, DAG-structured query evaluation plans. Then, we present the first plan generator capable of generating optimal DAG-structured query evaluation plans. The experimental results show that with no or only a modest increase of plan generation time, a major reduction of query execution time can be achieved for common queries.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Neumann, Thomas and Moerkotte, Guido},
  TITLE = {Single phase construction of optimal DAG-structured QEPs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2008-5-002},
  MONTH = {July},
  YEAR = {2008},
  ISSN = {0946-011X},