hide
Free keywords:
-
Abstract:
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.
