Simultaneous Optimization and Evaluation of Multiple Dimensional Queries
Yihong Zhao( University of Wisconsin - Madison )
Prasad M. Deshpande ( University of Wisconsin - Madison )
Jeffrey F. Naughton ( University of Wisconsin - Madison )
Amit Shukla ( University of Wisconsin - Madison )
Database researchers have made significant progress on several
research issues related to multidimensional data analysis, including
the development of fast cubing algorithms, efficient schemes for
creating and maintaining pre-computed group-bys, and the design of
efficient storage structures for multidimensional data. However, to
date there has been little or no work multidimensional query
optimization. Recently, Microsoft has proposed ``OLE DB for OLAP'' as
a standard multidimensional interface for databases. OLE DB for OLAP
defines Multi-dimensional Expressions (MDX), which has the interesting
and challenging feature of allowing clients to ask several related
dimensional queries in a single MDX expression. In this paper we
present three algorithms to optimize multiple related dimensional
queries. Two of algorithms focus on how to generate a global plan
from several related local plans. The third algorithm focuses on
generating a good global plan without first generating local plans. We
also present three new query evaluation primitives that allow related
query plans to share portions of their evaluation. In our performance
study, we compare the three algorithms.
Here is the postscript version of the paper
URI