DiSC - SIGMOD Paper Index

Caching Multidimensional Queries Using Chunks

Prasad Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton

Full Paper (PDF)
Slides (HTML)

Abstract

Caching has been proposed (and implemented) by OLAP systems in order to reduce response times for multidimensional queries. Previous work on such caching has considered table level caching and query level caching. Table level caching is more suitable for static schemes. On the other hand, query level caching can be used in dynamic schemes, but is too coarse for "large" query results. Query level caching has the further drawback for small query results in that it is only effective when a new query is subsumed by a previously cached query. In this paper, we propose caching small regions of the multidimensional space called "chunks". Chunk-based caching allows fine granularity caching, and allows queries to partially reuse the results of previous queries with which they overlap. To facilitate the computation of chunks required by a query but missing from the cache, we propose a new organization for relational tables, which we call a "chunked file." Our experiments show that for workloads that exhibit query locality, chunked caching combined with the chunked file organization performs better than query level caching. An unexpected benefit of the chunked file organization is that, due to its multidimensional clustering properties, it can significantly improve the performance of queries that "miss" the cache entirely as compared to traditional file organizations.

References

References, where available, link to the DBLP on the World Wide Web.

[AAD+96]

Sameet Agarwal, Rakesh Agrawal, Prasad Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, Sunita Sarawagi: On the Computation of Multidimensional Aggregates. VLDB 1996: 506-521

[BPT97]

Elena Baralis, Stefano Paraboschi, Ernest Teniente: Materialized Views Selection in a Multidimensional Database. VLDB 1997: 156-165

[DFJST]

Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, Michael Tan: Semantic Data Caching and Replacement. VLDB 1996: 330-341

[DKLP+94]

David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu: Client-Server Paradise. VLDB 1994: 558-569

[Fell57]

...

[GBLP96]

Jim Gray, Adam Bosworth, Andrew Layman, Hamid Pirahesh: Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total. ICDE 1996: 152-159

[GHRU97]

Himanshu Gupta, Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman: Index Selection for OLAP. ICDE 1997: 208-219

[Gupt97]

Himanshu Gupta: Selection of Views to Materialize in a Data Warehouse. ICDT 1997: 98-112

[HRU96]

Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman: Implementing Data Cubes Efficiently. SIGMOD Conf. 1996: 205-216

[OG95]

Patrick E. O'Neil, Goetz Graefe: Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3): 8-11(1995)

[OQ97]

Patrick E. O'Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference 1997: 38-49

[RJZN97]

...

[RK96]

...

[SDJL96]

Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. VLDB 1996: 318-329

[SDN]

...

[SDNR96]

Amit Shukla, Prasad Deshpande, Jeffrey F. Naughton, Karthikeyan Ramasamy: Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies. VLDB 1996: 522-531

[SS94]

Sunita Sarawagi, Michael Stonebraker: Efficient Organization of Large Multidimensional Arrays. ICDE 1994: 328-336

[SSV96]

Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. VLDB 1996: 51-62

[Ull96]

Jeffrey D. Ullman: Efficient Implementation of Data Cubes Via Materialized Views. KDD 1996: 386-388

[ZDN97]

Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton: An Array-Based Algorithm for Simultaneous Multidimensional Aggregates. SIGMOD Conference 1997: 159-170 Referenced By:

Amit Shukla, Prasad Deshpande, Jeffrey F. Naughton: Materialized View Selection for Multidimensional Datasets. VLDB 1998: 488-499

BIBTEX

@inproceedings{DBLP:conf/sigmod/DeshpandeRSN98,
author = {Prasad Deshpande and
Karthikeyan Ramasamy and
Amit Shukla and
Jeffrey F. Naughton},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Caching Multidimensional Queries Using Chunks},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {259-270},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}