Modeling and exploiting query interactions in database systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Modeling and exploiting query interactions in database systems

Full text

Pdf (2.71 MB)

Source

Conference on Information and Knowledge Management archive
Proceeding of the 17th ACM conference on Information and knowledge management table of contents

Napa Valley, California, USA

SESSION: DB: efficient maintenance and query optimization table of contents

Pages 183-192

Year of Publication: 2008

ISBN:978-1-59593-991-3

Authors

Mumtaz Ahmad	University of Waterloo, Waterloo, ON, Canada
Ashraf Aboulnaga	University of Waterloo, Waterloo, ON, Canada
Shivnath Babu	Duke University, Durham, NC, USA
Kamesh Munagala	Duke University, Durham, NC, USA

Sponsors

ACM: Association for Computing Machinery
SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web
SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 151, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1458082.1458109 What is a DOI?

ABSTRACT

The typical workload in a database system consists of a mixture of multiple queries of different types, running concurrently and interacting with each other. Hence, optimizing performance requires reasoning about query mixes and their interactions, rather than considering individual queries or query types. In this paper, we show the significant impact that query interactions can have on workload performance. We present a new approach based on planning experiments and statistical modeling to capture the impact of query interactions. This approach requires no prior assumptions about the internal workings of the database system or the nature or cause of query interactions, making it portable across systems. As a concrete demonstration of the potential of capturing, modeling, and exploiting query interactions, we develop a novel interaction-aware query scheduler that targets report-generation workloads in Business Intelligence (BI) settings. Under certain assumptions, the schedule found by this scheduler is within a constant factor of optimal. An experimental evaluation with TPC-H queries on IBM DB2 demonstrates that our scheduler consistently outperforms (up to 4x) conventional schedulers that do not account for query interactions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Robert Abbott , Hector Garcia-Molina, Scheduling real-time transactions, ACM SIGMOD Record, v.17 n.1, p.71-81, March, 1988 [doi>10.1145/44203.44209]
	2	R. Abbott , H. Garcia-Molina, Scheduling real-time transactions with disk resident data, Proceedings of the 15th international conference on Very large data bases, p.385-395, July 1989, Amsterdam, The Netherlands
	3	Robert K. Abbott , Hector Garcia-Molina, Scheduling real-time transactions: a performance evaluation, ACM Transactions on Database Systems (TODS), v.17 n.3, p.513-560, Sept. 1992 [doi>10.1145/132271.132276]
	4	M. Ahmad, A. Aboulnaga, S. Babu, and K. Munagala. Qshuffler: Getting the query mix right. In ICDE, 2008.
	5	Stefan Aulbach , Torsten Grust , Dean Jacobs , Alfons Kemper , Jan Rittinger, Multi-tenant databases for software as a service: schema-mapping techniques, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376736]
	6	Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Dilys Thomas, Operator scheduling in data stream systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.333-353, December 2004 [doi>10.1007/s00778-004-0132-6]
	7	Business objects. http://www.businessobjects.com/.
	8	M. J. Carey , R. Jauhari , M. Livny, Priority in DBMS resource scheduling, Proceedings of the 15th international conference on Very large data bases, p.397-410, July 1989, Amsterdam, The Netherlands
	9	Cognos. http://www.cognos.com/.
	10	R. H. Conway, W. L. Maxwell, and M. L. W. Theory of scheduling. Addison-Wesley, 1967.
	11	CPLEX. http://www.ilog.com/products/cplex/.
	12	Sameh Elnikety , Erich Nahum , John Tracey , Willy Zwaenepoel, A method for transparent admission control and request scheduling in e-commerce web sites, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988710]
	13	Hans-Ulrich Heiss , Roger Wagner, Adaptive Load Control in Transaction Processing Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.47-54, September 03-06, 1991
	14	Toshihide Ibaraki , Tiko Kameda , Naoki Katoh, Cautious Transaction Schedulers for Database Concurrency Control, IEEE Transactions on Software Engineering, v.14 n.7, p.997-1009, July 1988 [doi>10.1109/32.42740]
	15	Naoki Katoh , Toshihide Ibaraki , Tiko Kameda, Cautious transaction schedulers with admission control, ACM Transactions on Database Systems (TODS), v.10 n.2, p.205-229, June 1985 [doi>10.1145/3857.3860]
	16	Terence Kelly, Detecting performance anomalies in global applications, Proceedings of the 2nd conference on Real, Large Distributed Systems, p.42-47, December 13, 2005, San Francisco, CA
	17	J. Kyoung-Don Kang Son, S.H. Stankovic. Service differentiation in real-time main memory databases. In ISORC, 2002.
	18	W.-Y. Loh. Regression trees with unbiased variable selection and interaction detection. Statistica Sinica, 12:361--386, 2002.
	19	David T. McWherter , Bianca Schroeder , Anastassia Ailamaki , Mor Harchol-Balter, Priority Mechanisms for OLTP and Transactional Web Applications, Proceedings of the 20th International Conference on Data Engineering, p.535, March 30-April 02, 2004
	20	David T. McWherter , Bianca Schroeder , Anastassia Ailamaki , Mor Harchol-Balter, Improving Preemptive Prioritization via Statistical Characterization of OLTP Locking, Proceedings of the 21st International Conference on Data Engineering, p.446-457, April 05-08, 2005 [doi>10.1109/ICDE.2005.78]
	21	Abhay Mehta , Chetan Gupta , Umeshwar Dayal, BI batch manager: a system for managing batch workloads on enterprise data-warehouses, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353420]
	22	Axel Mönkeberg , Gerhard Weikum, Performance Evaluation of an Adaptive and Robust Load Control Method for the Avoidance of Data-Contention Thrashing, Proceedings of the 18th International Conference on Very Large Data Bases, p.432-443, August 23-27, 1992
	23	K. O'Gorman , A. El Abbadi , D. Agrawal, Multiple query optimization in middleware using query teamwork, Software—Practice & Experience, v.35 n.4, p.361-391, 10 April 2005 [doi>10.1002/spe.640]
	24	HweeHwa Pang , Michael J. Carey , Miron Livny, Multiclass Query Scheduling in Real-Time Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.533-551, August 1995 [doi>10.1109/69.404028]
	25	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
	26	H. J. Ryser. Combinatorial Mathematics. The Mathematical Association of America, 1963.
	27	Giovanni Maria Sacco , Mario Schkolnick, Buffer management in relational database systems, ACM Transactions on Database Systems (TODS), v.11 n.4, p.473-498, Dec. 1986 [doi>10.1145/7239.7336]
	28	Alexander Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	29	Bianca Schroeder , Mor Harchol-Balter, Web servers under overload: How scheduling can help, ACM Transactions on Internet Technology (TOIT), v.6 n.1, p.20-52, February 2006 [doi>10.1145/1125274.1125276]
	30	Bianca Schroeder , Mor Harchol-Balter , Arun Iyengar , Erich Nahum , Adam Wierman, How to Determine a Good Multi-Programming Level for External Scheduling, Proceedings of the 22nd International Conference on Data Engineering, p.60, April 03-07, 2006 [doi>10.1109/ICDE.2006.78]
	31	Skewed TPC-D data generator. ftp://ftp.research.microsoft.com/users/viveknar/TPCDSkew/.
	32	Christopher Stewart , Terence Kelly , Alex Zhang, Exploiting nonstationarity for performance prediction, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
	33	M. Welsh and D. Culler. Adaptive overload control for busy internet servers. In USITS, 2003.
	34	Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
	35	Q. Zhang, L. Cherkasova, G. Mathews, W. Greene, and E. Smirni. R-capriccio: A capacity planning and anomaly detection tool for enterprise services with live workloads. In Middleware, 2007.
	36	Qi Zhang , Ludmila Cherkasova , Evgenia Smirni, A Regression-Based Analytic Model for Dynamic Resource Provisioning of Multi-Tier Applications, Proceedings of the Fourth International Conference on Autonomic Computing, p.27, June 11-15, 2007 [doi>10.1109/ICAC.2007.1]