Parallel Algorithms for the Execution of Relational Database Operations Revisited On Grids

Abstract

This paper presents an analytical discussion of algorithms for relational database operations in a grid environment, compares the findings with the classical generalized multiprocessor framework, and describes an optimization algorithm to maximize performance for a heterogeneous environment.

We develop a concise but comprehensive analytical model of parallel algorithms for sorting, joining, and aggregation. In our approach we focus on a limited number of characteristic parameters to keep the analytical model clear. It is shown that an expressive model can be built upon just three characteristic parameter sets, namely the node processing performance and the network and the disk bandwidths. These parameters are the input for the optimization process for the orchestration of the execution workflow on the grid. Based on these results the paper proves that using smart enhancement to exploit the heterogeneity of the grid, the performance of the algorithms for database operations can be increased remarkably.

Keywords

Heterogeneous environment grids database systems parallel relational operators performance analysis

Get full access to this article

View all access options for this article.

References

Antonioletti, M. , Atkinson, M. , Baxter, R. , Borley, A. , Hong, N.C. , Collins, B. , Hardman, N. , et al. (2005). The design and implementation of grid database services in OGSA-DAI, Concurrency and Computation: Practice and Experience, 17(2-4): 357-376.

Batcher, K.E. (1968). Sorting networks and their applications. In Proc. of the 1968 Spring Joint Computer Conference (Atlantic City, NJ, Apr. 30 May 2), Vol. 32. pp. 307-314, New York, ACM.

Beran, P.P. , Habel, G. , and Schikuta, E. (2008). Soda - a distributed data management framework for the internet of services. GCC '08: Proceedings of the 2008 Seventh International Conference on Grid and Cooperative Computing , Washington, DC, USA: IEEE Computer Society, 2008, pp. 292-300.

Bitton, D. , Boral, H. , DeWitt, D.J. , and Wilkinson, W.K. (1983). Parallel algorithms for the execution of relational database operations, ACM Trans. Database Syst., 8(3): 324-353.

DeWitt, D. and Gray, J. (1992). Parallel database systems: the future of high performance database systems, Commun. ACM, 35(6): 85-98.

Gounaris, A. , Sakellariou, R. , Paton, N.W. , and Fernandes, A.A.A. (2004). Resource scheduling for parallel query processing on computational grids. In 5th International Workshop on Grid Computing (GRID 2004), pp. 396- 401.

Hoschek, W. , Jaen-Martinez, J. , Samar, A. , Stockinger, H. , and Stockinger, K. (2000). Data management in an international data grid project. In IEEE/ACM International Workshop on Grid Computing Grid, pp. 77-90, London, Springer-Verlag.

Moreno, E. (2002). Hash join algorithms on SMPs clusters: Effects of netcaches on its scalability and performance, Journal of Information Science and Engineering, 18(1- 10).

Pirahesh, H. , Mohan, C. , Cheng, J. , Liu, T. , and Selinger, P. (1990). Parallelism in relational database systems: Architectural issues and design approaches. In Proc. of the IEEE Conf. on Distributed and Parallel Database Systems, pp. 4-29, Los Alamitos, CA : IEEE Computer Society Press.

10.

Soe, K.M. , Aung, T.N. , Nwe, A.A. , Naing, T.T. , and Thein, N. (2005). A framework for parallel query processing on grid-based architecture. In ICEIS 2005, Proceedings of the 7th International Conference on Enterprise Information Systems, pp. 203-208.

11.

Stone, H. (1971). Parallel processing with the perfect shuffle, IEEE Trans. Computing, C- 20(2), 153-161.

12.

Stonebraker, M. , Aoki, P. , Devine, R. , Litwin, W. , and Olson, M. (1994). Mariposa: A new architecture for distributed data . In Proc. of the Int. Conf. on Data Engineering, pp. 54-65, Los Alamitos, CA: IEEE Computer Society Press.

13.

Valduriez, P. and Gardarin, G. (1984). Join and semijoin algorithms for a multiprocessor database machine, ACM Trans. Database Syst., 9(1): 133-161.