Towards self-tuning data placement in parallel database systems

ABSTRACT

Parallel database systems are increasingly being deployed to support the performance demands of end-users. While declustering data across multiple nodes facilitates parallelism, initial data placement may not be optimal due to skewed workloads and changing access patterns. To prevent performance degradation, the placement of data must be reorganized, and this must be done on-line to minimize disruption to the system.

In this paper, we consider a dynamic self-tuning approach to reorganization in a shared nothing system. We introduce a new index-based method that faciliates fast and efficient migration of data. Our solution incorporates a globally height-balanced structure and load tracking at different levels of granularity. We conducted an extensive performance study, and implemented the methods on the Fujitsu AP3000 machine. Both the simulation and empirical results demonstratic that our proposed method is indeed scalable and effective in correcting any deterioration in system throughput.

REFERENCES

• 1: Kiran J. Achyutuni , Edward Omiecinski , Shamkant B. Navathe, Two techniques for on-line index modification in shared nothing parallel databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.125-136, June 04-06, 1996, Montreal, Quebec, Canada
• 2: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 3: Elisa Bertino , C , Kian-Lee Tan , Beng Chin Ooi , Ron Sacks-Davis , Justin Zobel , Boris Shidlovsky, Indexing Techniques for Advanced Database Systems, Kluwer Academic Publishers, Norwell, MA, 1997
• 4: Theodore Johnson , Padmashree Krishna, Lazy updates for distributed search structure, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.337-346, May 25-28, 1993, Washington, D.C., United States
• 5: P. Krishna and T. Johnson. Implementing distributed search structures. Technical report available at cis. ulf. edu: cis/tech-reports/tr92/tr92-O32.ps.Z, 1992.
• 6: Brigitte Kröll , Peter Widmayer, Distributing a search tree among a growing number of processors, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.265-276, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: David Lomet, Replicated indexes for distributed data, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.108-119, December 18-20, 1996, Miami Beach, Florida, United States
• 8: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, ACM SIGMOD Record, v.21 n.2, p.361-370, June 1, 1992
• 9: Edward Omiecinski, Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File, Proceedings of the Fourth International Conference on Data Engineering, p.589-596, February 01-05, 1988
• 10: Edward Omiecinski , Liehuey Lee , Peter Scheuermann, Concurrent File Reorganization for Record Clustering: A Performance Study, Proceedings of the Eighth International Conference on Data Engineering, p.265-272, February 03-07, 1992
• 11: Beng Chin Ooi , Kian-Lee Tan , Cui Yu , Stephane Bressan, Indexing the edges—a simple and yet efficient approach to high-dimensional indexing, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.166-174, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335219]
• 12: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 13: D. Ridge, D. Becker, P. Merkey, and T. Sterling. Beowulf: Harnessing the power of parallelism in a pile of pcs. In Proc. of IEEE Aerospace, 1997.
• 14: P. Scheuermann, G. Weikum, and P. Zabback. Disk cooling in parallel disk systems. IEEE Bulletin of the Technical Committee on Data Engineering, 17(3):29- 40, 1994.
• 15: Peter Scheuermann , Gerhard Weikum , Peter Zabback, Data partitioning and load balancing in parallel disk systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.1, p.48-66, February 1998 [doi>10.1007/s007780050053]
• 16: G.H. Sockut and B.R. Iyer. A survey of online reorganization in ibm products and research. IEEE Bulletin of the Technical Committee on Data Engineering, 19(2):4- 11, 1996.
• 17: Takayuki Tamura , Masato Oguchi , Masaru Kitsuregawa, Parallel database processing on a 100 Node PC cluster: cases for decision support query processing and data mining, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-16, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509642]
• 18: Radek Vingralek , Yuri Breitbart , Gerhard Weikum, Snowball: Scalable Storage on Networks of Workstations with Balanced Load, Distributed and Parallel Databases, v.6 n.2, p.117-156, April 1998 [doi>10.1023/A:1008609030195]
• 19: Kevin Watkins, Discrete Event Simulation in C, McGraw-Hill, Inc., New York, NY, 1993
• 20: Chendong Zou , Betty Salzberg, On-line reorganization of sparsely-populated B+-trees, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.115-124, June 04-06, 1996, Montreal, Quebec, Canada
• 21: Chendong Zou , Betty Salzberg, Safely and Efficiently Updating References During On-line Reorganization, Proceedings of the 24rd International Conference on Very Large Data Bases, p.512-522, August 24-27, 1998

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Performance