Modeling and exploiting query interactions in database systems

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

• 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
database systems, query prcoessing, statistical techniques