A Non-Uniform Data Fragmentation Strategy for Parallel Main-Memory Database Systems

N. Bassiliades, I. Vlahavas, “A Non-Uniform Data Fragmentation Strategy for Parallel Main-Memory Database Systems”, 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.

Multi-Processor Database System, Parallel Query Execution, Main-Memory Database, Data Fragmentation, Analytic Model, Speed-up, Scale-up, Hashing Function.

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.