Using shared virtual memory for parallel join processing

ABSTRACT

In this paper, we show that shared virtual memory, in a shared-nothing multiprocessor, facilitates the design and implementation of parallel join processing algorithms that perform significantly better in the presence of skew than previously proposed parallel join processing algorithms. We propose two variants of an algorithm for parallel join processing using shared virtual memory, and perform a detailed simulation to investigate their performance. The algorithm is unique in that it employs both the shared virtual memory paradigm and the message-passing paradigm used by current shared-nothing parallel database systems. The implementation of the algorithm requires few modifications to existing shared-nothing parallel database systems.

REFERENCES

• BBDW83: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• CBZ91: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• DG85: D. J. DeWitt and R. Gerber. Multiprocessor hash-based join algorithms. In Proe. of the 1$th VLDB Conf., 1985.
• DGS+90: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• DNSS92: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
• ELZ86: Derek L. Eager , Edward D. Lazowska , John Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986
• ESW78: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• GD90: Shahram Ghandeharizadeh , David J. DeWitt, Hybrid-range partitioning strategy: a new declustering strategy for multiprocessor databases machines, Proceedings of the sixteenth international conference on Very large databases, p.481-492, September 1990, Brisbane, Australia
• HD91: Hui-I Hsiao , David J. DeWitt, A performance study of three high availability data replication strategies, Proceedings of the first international conference on Parallel and distributed information systems, p.18-29, December 1991, Miami, Florida, United States
• HL91: Kien A. Hua , Chiang Lee, Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning, Proceedings of the 17th International Conference on Very Large Data Bases, p.525-535, September 03-06, 1991
• HT88: M. Hsu and V.-O. Tam. Managing databases in distributed virtual memory. Technical Report TR-07-88, Aiken Computation Lab., Harvard Univ., March 1988.
• HT89: M. Hsu and V.-O. Tam. Transaction synchronization in distributed shared virtual memory systems. Technical Report TR-05-89, Center for Research in Computing Technology, Harvard Univ., 1989.
• KO90: 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
• LH89: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• LKB87: Miron Livny , Setrag Khoshafian , Haran Boral, Multi-disk management algorithms, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.69-77, May 11-14, 1987, Banff, Alberta, Canada
• LT91: H. Lu and K.-L.Tan. A dynamic and load-bManced taskoriented approach to parallel query processing. DISC Technical Report TPtC7/91, National University of Singapore, July 1991.
• LTS90: Hongjun Lu , Kian-Lee Tan , Ming-Chien Sahn, Hash-based join algorithms for multiprocessor computers with shared memory, Proceedings of the sixteenth international conference on Very large databases, p.198-209, September 1990, Brisbane, Australia
• LY90: M. S. Lakshmi , P. S. Yu, Effectiveness of Parallel Joins, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.410-424, December 1990 [doi>10.1109/69.63253]
• Omi91: Edward Omiecinski, Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor, Proceedings of the 17th International Conference on Very Large Data Bases, p.375-385, September 03-06, 1991
• RE78: D. Ries and R. Epstein. Evaluation of distribution criteria for distributed database systems. UCB/ERL Technical Report M78/22, University of California, Berkeley, May 1978.
• Sch90: H. Schwetman. CSIM users' guide. MCC Tech Report ACT-126-90, Microelectronics and Computer Technology Corp., March 1990.
• SD89: Donovan A. Schneider , David J. DeWitt, A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.110-121, June 1989, Portland, Oregon, United States
• SD90: 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
• WDJ91: Christopher B. Walton , Alfred G. Dale , Roy M. Jenevein, A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins, Proceedings of the 17th International Conference on Very Large Data Bases, p.537-548, September 03-06, 1991
• WDYT90: J. L. Wolf, D. M. Dias, et al. An effective algorithm for parallelizing hash joins in the presence of data skew. IBM T. J. Watson Research Center Tech Report RC 15510, 1990.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.2 Simulation Languages

General Terms:
Design, Experimentation, Languages, Performance