Fair, effective, efficient and differentiated scheduling in an enterprise data warehouse

ABSTRACT

A typical online Business Intelligence (BI) workload consists of a combination of short, less intensive queries, along with long, resource intensive queries. As such, the longest queries in a typical BI workload may take several orders of magnitude more time to execute, compared with the shortest queries in the workload. This makes it challenging to design a good Mixed Workload Scheduler (MWS). In this paper we first define the design criteria that make a 'good' MWS. We then use these criteria to design rFEED, a MWS that is fair, effective, efficient, and differentiated. We simulate real workloads and compare our rFEED MWS with models of the current best of breed commercial systems. We show that the rFEED MWS works extremely well.

REFERENCES

• 1: Nikhil Bansal , Kirk Pruhs, Server scheduling in the L_p norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780580]
• 2: L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, and K. Pruhs. Online weighted flow time and deadline scheduling. J. Discrete Algorithms, 4(3):339--352, 2006.
• 3: A. Bedekar, S. Borst, K. Ramanan, P. Whiting, and E. Yeh. Downlink scheduling in CDMA data networks. GLOBECOM, 5:2653--2657, 1999.
• 4: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 5: Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
• 6: Peter Brucker, Scheduling Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
• 7: Carrie Ballinger. The Wild World of Mixed Workload: Priorities and resources learn to get along. Teradata Magazine Online. http://www.teradata.com/t/go.aspx/?id=114533.
• 8: Badrish Chandramouli , Christopher N. Bond , Shivnath Babu , Jun Yang, Query suspend and resume, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247542]
• 9: Chandra Chekuri , Sanjeev Khanna, Approximation schemes for preemptive weighted flow time, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509954]
• 10: Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece [doi>10.1145/380752.380778]
• 11: L. Cherkasova and T. Rokicki. Alpha Message Scheduling for Packet-Switched Interconnects. Technical Report HPL-94-71, HP Labs, August 1994.
• 12: Mark E. Crovella , Robert Frangioso , Mor Harchol-Balter, Connection scheduling in web servers, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.22-22, October 11-14, 1999, Boulder, Colorado
• 13: Eric J. Friedman , Shane G. Henderson, Fairness and efficiency in web server protocols, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 14: J. R. M. Hosking , J. F. Wallis, Parameter and quantile estimation for the generalized pareto distribution, Technometrics, v.29 n.3, p.339-349, August 1, 1987 [doi>10.2307/1269343]
• 15: IBM. DB2 Query Patroller. http://www-306.ibm.com/software/data/db2/querypatroller/.
• 16: Bala Kalyanasundaram , Kirk Pruhs , Mahendran Velauthapillai, Scheduling Broadcasts in Wireless Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.290-301, September 05-08, 2000
• 17: Arnaud Legrand , Alan Su , Frédéric Vivien, Minimizing the stretch when scheduling flows of biological requests, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148124]
• 18: Joseph Leung , Laurie Kelly , James H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, Inc., Boca Raton, FL, 2004
• 19: A. Mehta, C. Gupta, S. Wang, and U. Dayal. rfeed: A mixed workload scheduler for enterprise data warehouses. In ICDE '09, Accepted, 2009.
• 20: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 21: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 22: 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]
• 23: Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Efficient scheduling of heterogeneous continuous queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea