Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Modern enterprise data warehouses have complex workloads that are notoriously difficult to manage. An important problem in workload management is to run these complex workloads 'optimally'. Traditionally this problem has been studied in the OLTP (Online Transaction Processing) context where MPL (Multi Programming Level) is used as a knob to achieve optimality. However, MPL is a tricky knob in a BI (Business Intelligence) scenario, since a low MPL can easily result in underload and a high MPL can easily result in overload and 'thrashing'.

In this work we present BI Batch Manager, a workload management system to run batches of queries 'optimally' on an Enterprise Data Warehouse (EDW). It is comprised of three components: an admission control component, a scheduler and an execution control component. In order to automatically avoid underload and overload, we introduce a novel execution control mechanism, PGM (Priority Gradient Multiprogramming). In PGM, a priority gradient is created for the workload, with each query running at a distinctly different priority level. We demonstrate that this stabilizes the execution of a workload across a wide operating range. We use memory as the controlling factor for our admission control policy -- admitting batches of queries such that their memory requirement equals the available memory on the system. Our scheduling policy of largest memory query as the highest priority query further stabilizes the execution.

We validate our BI Batch Manager using varying workloads on a commercial, enterprise class DBMS. We show that it effectively avoids underload and overload (thrashing) and can automatically run BI workloads with 'optimal' performance.

REFERENCES

• 1: Russ Blake, Optimal control of thrashing, Proceedings of the 1982 ACM SIGMETRICS conference on Measurement and modeling of computer systems, August 30-September 01, 1982, Seattle, Washington
• 2: Daniel Pierre Bovet , Marco Cassetti , Andy Oram, Understanding the Linux Kernel, O'Reilly & Associates, Inc., Sebastopol, CA, 2000
• 3: Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
• 4: Kurt P. Brown , Manish Mehta , Michael J. Carey , Miron Livny, Towards Automated Performance Tuning for Complex Workloads, Proceedings of the 20th International Conference on Very Large Data Bases, p.72-84, September 12-15, 1994
• 5: 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
• 6: Michael J. Carey , Sanjay Krishnamurthi , Miron Livny, Load control for locking: the “half-and-half” approach, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.72-84, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298543]
• 7: Richard W. Carr , John L. Hennessy, WSCLOCK—a simple and effective algorithm for virtual memory management, Proceedings of the eighth ACM symposium on Operating systems principles, p.87-95, December 14-16, 1981, Pacific Grove, California, United States
• 8: Xiangping Chen , Prasant Mohapatra , Huamin Chen, An admission control scheme for predictable server response time for web accesses, Proceedings of the 10th international conference on World Wide Web, p.545-554, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372156]
• 9: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 10: {DENN68-TH} Denning, PJ, "Thrashing: Its Causes and Prevention", Proc AFIPS 1968 FJCC 33, p. 915--922
• 11: {DENN76} Peter J. Denning et al, "Optimal Multiprogramming", Acta Informatica, Springer-Verlag, 1976
• 12: P. J. Denning, Working Sets Past and Present, IEEE Transactions on Software Engineering, v.6 n.1, p.64-84, January 1980 [doi>10.1109/TSE.1980.230464]
• 13: Peter J. Denning, A Short Theory of Multiprogramming, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.2-7, January 10-18, 1995
• 14: {ELNI04} Sameh Elnikety et al, "A method for transparent admission control and request scheduling in e-commerce web sites", WWW2004, May 2004.
• 15: 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
• 16: Song Jiang , Xiaodong Zhang, TPF: a dynamic system thrashing protection facility, Software—Practice & Experience, v.32 n.3, p.295-318, March 2002 [doi>10.1002/spe437]
• 17: {JOHN74} Johnson, D., Demers, A., Ullman, J., Garey, M., Graham, R.; Worst-case performance bounds for simple one-dimensional packaging algorithms. SIAM Journal on Computing 3 (December 1974) 299--325
• 18: {KAMR04} Kamra, A.; Misra, V.; Nahum, E. M., "Yaksha: a selftuning controller for managing the performance of 3-tiered Web sites," Quality of Service, 2004. IWQOS 2004. Twelfth IEEE International Workshop on, vol., no., pp. 47--56, 7--9 June 2004
• 19: {LIU03} Xue Liu, et al, "Online Response Rime optimization of Apache Web Server >>, IWQoS 2003, LNCS 2707, pp 461--478, 2003
• 20: 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
• 21: Hwee Hwa Pang , Michael J. Carey , Miron Livny, Managing memory for real-time queries, ACM SIGMOD Record, v.23 n.2, p.221-232, June 1994
• 22: 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]
• 23: Juan Rodriguez-Rosell , Jean-Pierre Dupuy, The design, implementation, and evaluation of a working set dispatcher, Communications of the ACM, v.16 n.4, p.247-253, April 1973 [doi>10.1145/362003.362032]
• 24: 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]
• 25: 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]
• 26: Abraham Silberschatz, (WCS)Operating System Concepts 7th Edition Flex Format, John Wiley & Sons, 2005
• 27: {SMIT80} Alan Jay Smith, "Multiprogramming and Memory Contention", Software-Practice and Experience, Vol 10, 531--552, 1980
• 28: Gerhard Weikum , Axel Moenkeberg , Christof Hasse , Peter Zabback, Self-tuning database technology and information services: from wishful thinking to viable engineering, Proceedings of the 28th international conference on Very Large Data Bases, p.20-31, August 20-23, 2002, Hong Kong, China

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration