Efficient computation of multiple group by queries

ABSTRACT

Data analysts need to understand the quality of data in the warehouse. This is often done by issuing many Group By queries on the sets of columns of interest. Since the volume of data in these warehouses can be large, and tables in a data warehouse often contain many columns, this analysis typically requires executing a large number of Group By queries, which can be expensive. We show that the performance of today's database systems for such data analysis is inadequate. We also show that the problem is computationally hard, and develop efficient techniques for solving it. We demonstrate significant speedup over existing approaches on today's commercial database systems.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• 3: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 4: Nicolas Bruno , Surajit Chaudhuri, Exploiting statistics on query expressions for optimization, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564722]
• 5: Surajit Chaudhuri , Vivek Narasayya, AutoAdmin “what-if” index analysis utility, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.367-378, June 01-04, 1998, Seattle, Washington, United States
• 6: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 7: Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
• 8: Nilesh N. Dalvi , Sumit K. Sanghai , Prasan Roy , S. Sudarshan, Pipelining in multi-query optimization, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.59-70, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375561]
• 9: Wolfgang Lehner , Roberta Cochrane , Hamid Pirahesh , Markos Zaharioudakis, fAST Refresh using Mass Query Optimization, Proceedings of the 17th International Conference on Data Engineering, p.391-398, April 02-06, 2001
• 10: Himanshu Gupta, Selection of Views to Materialize in a Data Warehouse, Proceedings of the 6th International Conference on Database Theory, p.98-112, January 08-10, 1997
• 11: Himanshu Gupta , Inderpal Singh Mumick, Selection of Views to Materialize Under a Maintenance Cost Constraint, Proceeding of the 7th International Conference on Database Theory, p.453-470, January 10-12, 1999
• 12: Graefe G. The Cascades Framework for Query Optimization. In Data Engineering Bulletin (Sept 1995), 19--29.
• 13: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 14: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 15: Hinneburg A., Habich D., and Lehner W. COMBI-Operator -- Database Support for Data Mining Applications. In Proc. of VLDBA 2003, 429--439.
• 16: Kenneth A. Ross , Divesh Srivastava, Fast Computation of Sparse Datacubes, Proceedings of the 23rd International Conference on Very Large Data Bases, p.116-125, August 25-29, 1997
• 17: Kenneth A. Ross , Divesh Srivastava , S. Sudarshan, Materialized view maintenance and integrity constraint checking: trading space for time, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.447-458, June 04-06, 1996, Montreal, Quebec, Canada
• 18: Jack Olson, Data Quality: The Accuracy Dimension, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 19: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 20: Protein Information Resource (PIR) web site. <u>http://pir.georgetown.edu/</u>
• 21: Sarawagi S., Agrawal R., and Gupta A. On Compressing the Data Cube. IBM Technical Report.
• 22: Wolfgang Scheufele , Guido Moerkotte, On the complexity of generating optimal plans with cross products (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.238-248, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263687]
• 23: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 24: TPC Benchmark H. Decision Support. http://www.tpc.org
• 25: Daniel C. Zilio , Calisto Zuzarte , Guy M. Lohman , Hamid Pirahesh , Jarek Gryz , Eric Alton , Dongming Liang , Gary Valentin, Recommending Materialized Views and Indexes with IBM DB2 Design Advisor, Proceedings of the First International Conference on Autonomic Computing (ICAC'04), p.180-188, May 17-18, 2004