Transaction reordering with application to synchronized scans

ABSTRACT

Traditional workload management methods mainly focus on the current system status while information about the interaction between queued and running transactions is largely ignored. An exception to this is the transaction reordering method, which reorders the transaction sequence submitted to the RDBMS and improves the transaction throughput by considering both the current system status and information about the interaction between queued and running transactions. The existing transaction reordering method only considers the reordering opportunities provided by analyzing the lock conflict information among multiple transactions. This significantly limits the applicability of the transaction reordering method. In this paper, we extend the existing transaction reordering method into a general transaction reordering framework that can incorporate various factors as the reordering criteria. We show that by analyzing the resource utilization information of transactions, the transaction reordering method can also improve the system throughput by increasing the resource sharing opportunities among multiple transactions. We provide a concrete example on synchronized scans and demonstrate the advantages of our method through experiments with a commercial parallel RDBMS.

REFERENCES

• 1: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Information and control in gray-box systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: Nathan C. Burnett , John Bent , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Exploiting Gray-Box Knowledge of Buffer-Cache Management, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.29-44, June 10-15, 2002
• 3: Philip A. Bernstein , David W. Shipman , James B. Rothnie, Jr., Concurrency control in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.18-51, March 1980 [doi>10.1145/320128.320131]
• 4: Hong-Tai Chou , David J. DeWitt, An evaluation of buffer management strategies for relational database systems, Proceedings of the 11th international conference on Very Large Data Bases, p.127-141, August 21-23, 1985, Stockholm, Sweden
• 5: 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]
• 6: Phillip M. Fernandez, Red brick warehouse: a read-mostly RDBMS for open SMP platforms, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.492, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: Christos Faloutsos , Raymond T. Ng , Timos K. Sellis, Predictive Load Control for Flexible Buffer Allocation, Proceedings of the 17th International Conference on Very Large Data Bases, p.265-274, September 03-06, 1991
• 8: Peter A. Franaszek , John T. Robinson , Alexander Thomasian, Concurrency control for high contention environments, ACM Transactions on Database Systems (TODS), v.17 n.2, p.304-345, June 1992 [doi>10.1145/128903.128906]
• 9: Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
• 10: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 11: G. Klaus. Real-time Data Warehousing and Data Mining for E-Commerce. http://ids.csom.umn.edu/faculty/wanninger/lectures/DataMining-6204Sp00.html.
• 12: C.A. Lang, B. Bhattacharjee, and T. Malkemus et al. Increasing Buffer-Locality for Multiple Relational Table Scans through Grouping and Throttling. ICDE 2007: 1136--1145.
• 13: Christian A. Lang , Bishwaranjan Bhattacharjee , Tim Malkemus , Kwai Wong, Increasing buffer-locality for multiple index based scans through intelligent placement and index scan speed control, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 14: G. Luo, J.F. Naughton, and C.J. Ellmann et al. Transaction Reordering and Grouping for Continuous Data Loading. BIRTE 2006: 34--49. Springer Lecture Notes in Computer Science 4365. Full version available as IBM research report RC24087.
• 15: Meikel Poess , Chris Floyd, New TPC benchmarks for decision support and web commerce, ACM SIGMOD Record, v.29 n.4, p.64-71, Dec. 2000 [doi>10.1145/369275.369291]
• 16: Ravishankar Ramamurthy , David J. DeWitt , Qi Su, A case for fractured mirrors, Proceedings of the 28th international conference on Very Large Data Bases, p.430-441, August 20-23, 2002, Hong Kong, China
• 17: 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
• 18: 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]
• 19: R.D. Sloan. A Practical Implementation of the Data Base Machine-Teradata DBC/1012. Hawaii Int. Conf. on System Sciences 1992: 320--327.
• 20: Giovanni Maria Sacco , Mario Schkolnick, A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model, Proceedings of the 8th International Conference on Very Large Data Bases, p.257-262, September 08-10, 1982
• 21: SQL Server 2005 Books Online. http://www.microsoft.com/technet/prodtechnol/sql/2005/downloads/books.mspx, 2007.
• 22: Teradata Parallel Data Pump Reference. http://www.info.ncr.com/temp/3021-122A94552.pdf.
• 23: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.271-282, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
data warehouse, synchronized scans, transaction reordering, workload management