LPIS Home Page
Google Search

Title: A Non-Uniform Data Fragmentation Strategy for Parallel Main-Memory Database Systems
Author(s): N. Bassiliades, I. Vlahavas.
Availability: Click here to download the GZ (gzipped postscript) file (11 pages).
Keywords: Multi-Processor Database System, Parallel Query Execution, Main-Memory Database, Data Fragmentation, Analytic Model, Speed-up, Scale-up, Hashing Function.
Appeared in: Proc. 21st International Conference on Very Large Data Bases (VLDB '95), U. Dayal, P.M.D. Gray, S. Nishio (Ed.), Morgan Kaufmann, pp. 370-381, September 11-15, 1995, Zurich, Switzerland, 1995.
Abstract: In multi-processor database systems there are processor initialization and inter-communication overheads that diverge real systems from the ideal linear behaviour as the number of processors in-creases. Main-memory database systems suffer more since the database processing cost is small compared to disk-based database systems and thus comparable to the processor initialization cost. The usual uniform data fragmentation strategy divides a relation into equal data partitions, lead-ing to idleness of single processors after local query execution termination and before global termination. In this paper, we propose a new, non-uniform data fragmentation strategy that re-sults in concurrent termination of query process-ing among all the processors. The proposed fragmentation strategy is analytically modeled, simulated and compared to the uniform strategy. It is proven that the non-uniform fragmentation strat-egy offers inherently better performance for a par-allel database system than the uniform strategy. Furthermore, the non-uniform strategy scales-up perfectly till an upper limit, after which a system re-configuration is needed.
See also : PRACTIC

        This paper has been cited by the following:

1 L. Brunie and H. Kosch, "Intégration dheuristiques dordonnancement dans loptimisation parallèle de requêtes relationnelles," Calculateurs parallèles, Volume été 1997.
2 H. Kosch, "Why to use randomized search strategies for complex parallel relational query optimization," Journal of Computing and Information, Vol. 3, No. 1, pp. 8-34, 1998.
3 Wang Yijie, Hu Shouren, Data Placement in Parallel Object-Oriented Database, Journal of National University Of Defense Technology, Vol. 21, No. 5, 1999, pp. 79-82.
4 Marco A.F. Duran, "Dynamic Allocation of Objects in Parallel Database", MSc Thesis, Dep. of Systems Engineering and Computer Science, Federal University of Rio de Janeiro, Brazil, March 1999.
5 D. Taniar and C.H.C. Leung, "Query Execution in Parallel Object-Oriented Databases", Information and Software Technology, Vol. 41, No. 3, pp. 163-178, 1999.
6 A. Hameurlain, F. Morvan, "Parallel query optimization methods and approaches: a survey", Computer Systems Science and Engineering, Vol. 19, No. 5, pp. 275-288, Sep 2004.
7 Andrew Pavlo, Carlo Curino, and Stanley Zdonik. 2012. Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). ACM, New York, NY, USA, 61-72. DOI=10.1145/2213836.2213844