Parallel database processing on a 100 Node PC cluster: cases for decision support query processing and data mining

ABSTRACT

We developed a PC cluster system consists of 100 PCs. Each PC employs the 200MHz Pentium Pro CPU and is connected with others through an ATM switch. We picked up two kinds of data intensive applications. One is decision support query processing. And the other is data mining, specifically, association rule mining.As a high speed network, ATM technology has recently come to be a de facto standard. While other high performance network standards are also available, ATM networks are widely used from local area to widely distributed environments. One of the problems of the ATM networks is its high latencies, in contrast to their higher bandwidths. This is usually considered a serious flaw of ATM in composing high performance massively parallel processors. However, applications such as large scale database analyses are insensitive to the communication latency, requiring only the bandwidth.On the other hand, the performance of personal computers is increasing rapidly these days while the prices of PCs continue to fall at a much faster rate than workstations'. The 200MHz Pentium Pro CPU is competitive in integer performance to the processor chips found in workstations. Although it is still weak at floating point operations, they are not frequently used in database applications.Thus, by combining PCs and ATM switches we can construct a large scale parallel platform very easily and very inexpensively. In this paper, we examine how such a system can help the data warehouse processing, which currently runs on expensive high-end mainframes and/or workstation servers.In our first experiment, we used the most complex query of the standard benchmark, TPC-D, on a 100 GB database to evaluate the system compared with commercial parallel systems. Our PC cluster exhibited much higher performance compared with those in current TPC benchmark reports. Second, we parallelized association rule mining and ran large scale data mining on the PC cluster. Sufficiently high linearity was obtained. Thus we believe that such commodity based PC clusters will play a very important role in large scale database processing.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , David E. Culler , Joseph M. Hellerstein , David A. Patterson, High-performance sorting on networks of workstations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.243-254, May 11-15, 1997, Tucson, Arizona, United States
• 4: D. S. Batory, On searching transposed files, ACM Transactions on Database Systems (TODS), v.4 n.4, p.531-544, Dec. 1979 [doi>10.1145/320107.320125]
• 5: Peter A. Boncz , Wilko Quak , Martin L. Kersten, Monet And Its Geographic Extensions: A Novel Approach to High Performance GIS Processing, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.147-166, March 25-29, 1996
• 6: Russell Carter , John Laroco, Commodity Clusters: Performance Comparison Between PC's and Workstations, Proceedings of the High Performance Distributed Computing (HPDC '96), p.292, August 06-09, 1996
• 7: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 8: Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 9: J. Heinanen. Multiprotocol encapsulation over ATM adaptation layer 5. Technical Report RFC1483, 1993.
• 10: Masaru Kitsuregawa , Miyuki Nakano , Mikio Takagi, Query Execution for Large Relations on Functional Disk Systems, Proceedings of the Fifth International Conference on Data Engineering, p.159-167, February 06-10, 1989
• 11: Masaru Kitsuregawa , Yasushi Ogawa, Bucket spreading parallel hash: a new, robust, parallel hash join method for data skew in the super database computer (SDC), Proceedings of the sixteenth international conference on Very large databases, p.210-221, September 1990, Brisbane, Australia
• 12: M. Laubach. Classical IP and ARP over ATM. Technical Report RFC1577, 1994.
• 13: Donovan A. Schneider , David J. DeWitt, Tradeoffs in processing complex join queries via hashing in multiprocessor database machines, Proceedings of the sixteenth international conference on Very large databases, p.469-480, September 1990, Brisbane, Australia
• 14: Takahiko Shintani , Masaru Kitsuregawa, Hash based parallel algorithms for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.19-30, December 18-20, 1996, Miami Beach, Florida, United States
• 15: T. Sterling , D. Savarese , D. J. Becker , B. Fryxell , K. Olson, Communication overhead for space science applications on the Beowulf parallel workstation, Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing - HPDC '95, p.23, August 02-04, 1995
• 16: T. Tamura, M. Nakamura, M. Kitsuregawa, and Y. Ogawa. Implementation and performance evaluation of the parallel relational database server SDC-II. In Proceedings of International Conference on Parallel Processing, 25th, pages I-212-I-221, 1996.
• 17: TPC. TPC Benchmark™ D (Decision Support). Standard Specification Revision 1.1, Transaction Processing Performance Council, 1995.