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

1. BBDW83.D. Bitton, H. Boral, et al. Parallel algorithms for the execution of relational database operations. A CM Trans. on Database Systems, 8(3), September 1983.
2. CBZ91.J. B. Carter, j. K. Bonnet, and W. Zwaenepoel. Implementation and performance of Muffin. In Proc. of the 1991 Syrup. on Operating SyMem Principles, 1991.
3. DG85.D. J. DeWitt and R. Gerber. Multiprocessor hash-based join algorithms. In Proe. of the 1$th VLDB Conf., 1985.
4. DGS+90.D. DeWitt, S. Ghandeharizadeh, D. Schneider et al. The Gamma database machine project. IEEE Trans. on Knowledge and Data Engineering, 2(1), March 1990.
5. DNSS92.D. J. DeWitt, J. F. Naughton, D. A. Schneider, and S. Seshadri. Practical skew handling in parallel joins. In Proc. of the 19th VLDB Conf., August 1992.
6. ELZ86.D.L. Eager, E. D. Lazowska, and J. Zahorjan. Adaptive load sharing in homogeneous distributed systems. IEEE Trans. on Software Engineering, SE-12(5), May 1986.
7. ESW78.R. Epstein, M. Stonebraker, and E. Wong. Distributed query processing in a relational database system. In Proc. of the A CM-SIGMOD Conf., 1978.
8. GD90.S. Ghandeharizadeh and D. J. DeWitt. Hybrid-range partitioning strategy: A new declustering strategy for multiprocessor database machines. In Proc. of the 16th VLDB Conf., September 1990.
9. HD91.H. I. Hsiao and D. J. DeWitt. A performance study of three high-availabillty data replication strategies. In Proc. of the 1st int'l Conf. on Parallel and Distributed Systems, December 1991.
10. HL91.K. A. Hua and C. Lee. Handling data skew in multiprocessor database computers using partition tuning. In Proc. of the 17th VLDB Conf., August 1991.
11. 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.
12. 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.
13. KO90.M. Kitsuregawa and Y. Ogawa. Bucket spreading parallel hash: A new, robust, parallel hash join method for data skew in the Super Database Computer (SDC). In Proc. of the 16#h VLDB Conf., August 1990.
14. LH89.K. Li and P. Hudak. Memory coherence in shared virtual memory systems. A CM Transactions on Computer Systems, 7(4), November 1989.
15. LKB87.M. Livny, S. Khoshafian, and H. Boral. Multi-disk management algorithms. In Proc. of the 1987 A CM-SIGMETRICS Conf., May 1987.
16. 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.
17. LTS90.H. Lu, K.-L. Tan, and M.-C. Shaxl. Hash-based join algorithms for multiprocessor computers with shared memory. In Proe. of the 16th VLDB Con}., September 1990.
18. LY90.M. S. Lakshmi and P. S. Yu. Effectiveness of parallel joins. IEEE Trans. on Knowledge and Da#a Engineering, 2(4), December 1990.
19. Omi91.E. Omiecinski. Performance analysis of a ioaxt balancing hash-join algorithm for a shared memory multiprocessor. In Proc. of the 17th VLDB Conf., September 1991.
20. 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.
21. Sch90.H. Schwetman. CSIM users' guide. MCC Tech Report ACT-126-90, Microelectronics and Computer Technology Corp., March 1990.
22. SD89.D. A. Schneider and D. J. DeWitt. A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment. In Proc. of the A CM-SIGMOD Conf., June 1989.
23. SD90.D. Schneider and D. J. DeWitt. Tradeoffs in processing complex join queries via hashing in multiprocessor database machines. In Proc. of #he 16#h VLDB Conf., September 1990.
24. WDJ91.C. B. Walton, A. G. Dale, and R. M. Jenevein. A taxonomy and performance model of data skew effects in parallel joins. In Proc. of the 17th VLDB Conf., September 1991.
25. 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

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Multiple instruction, multiple data

• Computing methodologies

  • Concurrent computing methodologies

  • Modeling and simulation

    • Simulation support systems

      • Simulation languages

  • Parallel computing methodologies

    • Parallel algorithms

• Information systems

  • Data management systems

    • Database management system engines

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Virtual memory

• Theory of computation

  • Design and analysis of algorithms

    • Parallel algorithms

  • Models of computation

    • Concurrency