Index selection for OLAP

被引:137
作者
Gupta, H
Harinarayan, V
Rajaraman, A
Ullman, JD
机构
来源
13TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING - PROCEEDINGS | 1997年
关键词
D O I
10.1109/ICDE.1997.581755
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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 efficient 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.
引用
收藏
页码:208 / 219
页数:12
相关论文
empty
未找到相关数据