Stanford InfoLab Publication Server

Index Selection for OLAP

Gupta, H. and Harinarayan, V. and Rajaraman, A. and Ullman, J. (1996) Index Selection for OLAP. Technical Report. Stanford InfoLab.




On-line analytical processing (OLAP) is a recent and important application of database systems. Typically, OLAP data is presented as a multidimensional "data cube." OLAP queries are complex and can take many hours or even days to run, if executed directly on the raw data. The most common method of reducing execution time is to precompute some of the queries into summary tables (subcubes of the data cube) and then to build indexes on these summary tables. In most commercial OLAP systems today, the summary tables that are to be precomputed are picked first, followed by the selection of the appropriate indexes on them. A trial-and-error approach is used to divide the space available between the summary tables and the indexes. This two-step process can perform very poorly. Since both summary tables and indexes consume the same resource --space -- their selection should be done together for the most effcient use of space. In this paper, we give algorithms that automate the selection of summary tables and indexes. In particular, we present a family of algorithms of increasing time complexities, and prove strong performance bounds for them. The algorithms with higher complexities have better performance bounds. However, the increase in the performance bound is diminishing, and we show that an algorithm of moderate complexity can perform fairly close to the optimal. This work was supported by NSF grant IRI{92{23405, ARO grant DAAH04{95{1{0192, and Air Force Contract F33615{93{ 1{1339. y Present address of V. Harinarayan and A. Rajaraman: Junglee Corp., Palo Alto, CA.

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Data Integration and Mediation
Projects:Information Integration
Related URLs:Project Homepage
ID Code:185
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:08 Dec 2008 15:30

Download statistics

Repository Staff Only: item control page