language: en

Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies

Amit Shukla Prasad M. Deshpande Jeffrey F. Naughton Karthikeyan Ramasamy
{amit,pmd,naughton,karthik}@cs.wisc.edu
Computer Sciences Department University of Wisconsin -
Madison

Abstract To speed up multidimensional data analysis, database systems frequently precompute aggregates on some subsets of dimensions and their corresponding hierarchies. This improves query response time. However, the decision of what and how much to precompute is a difficult one. It is further complicated by the fact that precomputation in the presence of hierarchies can result in an unintuitively large increase in the amount of storage required by the database. Hence, it is interesting and useful to estimate the storage blowup that will result from a proposed set of precomputations without actually computing them. We propose three strategies for this problem: one based on sampling, one based on mathematical approximation, and one based on probabilistic counting. We investigate the accuracy of these algorithms in estimating the blowup for different data distributions and database schemas. The algorithm based upon probabilistic counting is particularly attractive, since it estimates the storage blowup to within provable error bounds while performing only a single scan of the data.

[Work supported by an IBM CAS Fellowship, NSF grant IRI-9157357, and a grant from IBM under the University Partnership Program. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.]

[Proceedings of the 22nd VLDB Conference Mumbai (Bombay), India, 1996]

1 Introduction