MPI-I-2008-5-002

Single phase construction of optimal DAG-structured QEPs

Neumann, Thomas and Moerkotte, Guido

MPI-I-2008-5-002. July 2008, 73 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
MPI-I-2008-5-002.pdf	480 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2008-5-002

BibTeX
@TECHREPORT{NeumannMoerkotte2008, 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},}