Intensional Query Optimization
Abstract
We have introduced a new query optimization framework called intensional
query optimization (IQO), which enables existing
optimization techniques to be applied to queries that use views. In
particular, we consider that view definitions may employ
unions. Advanced database technologies and applications--such as federation
and mediation over heterogeneous database
sources--lead to such complex view definitions, and to the need to handle
complex, expensive queries.
Query rewriting techniques have been proposed which exploit semantic query
caches, materialized views, and semantic
knowledge about the database domain to optimize query evaluation. These can
augment syntactic optimization to reduce
evaluation costs further. Such techniques include semantic query caching,
query folding, and semantic query optimization.
However, most proposed rewrite techniques ignore views in queries; that is,
the views are considered as other tables. The IQO
framework enables rewrites to be applied to various expansions of the
query, even when no such rewrite is applicable directly to
the query itself. With IQO, we optimize the query tree, not just the query.
The IQO framework introduces the notion of a discounted query, which is a
query with some of its expansions "separated out", so
the query can be recast into pieces that can be optimized. For this
approach to be effective, the sum of the costs of evaluating
each piece must be less than the cost of evaluating the query itself. This
includes the discounted query. We develop an evaluation
plan for discounted queries that is generally more efficient than the
evaluation of the queries themselves.
(Also cross-referenced as UMIACS-TR-96-72)