A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory Database Systems.
Nick Bassiliades, Ioannis P. Vlahavas:
A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory Database Systems.
VLDB 1995: 370-381@inproceedings{DBLP:conf/vldb/BassiliadesV95,
author = {Nick Bassiliades and
Ioannis P. Vlahavas},
editor = {Umeshwar Dayal and
Peter M. D. Gray and
Shojiro Nishio},
title = {A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory
Database Systems},
booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
publisher = {Morgan Kaufmann},
year = {1995},
isbn = {1-55860-379-4},
pages = {370-381},
ee = {db/conf/vldb/BassiliadesV95.html},
crossref = {DBLP:conf/vldb/95},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
In multi-processor database systems there are processor initialization andinter-communication overheads that diverge real systems from the ideal linear behaviour as the number of processors increases.
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, leading 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 results in concurrent termination of query processing among all the processors.
The proposed fragmentation strategy is analytically modeled, simulated andcompared to the uniform strategy.
It is proven that the non-uniform fragmentation strategy offers inherentlybetter performance for a parallel database system than the uniform strategy.
Furthermore, the non-uniform strategy scales-up perfectly till an upper limit, after which a system reconfiguration is needed.
Copyright © 1995 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.):
VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland.
Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents
References
- [1]
- Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, Annita N. Wilschut:
PRISMA/DB: A Parallel Main Memory Relational DBMS.
IEEE Trans. Knowl. Data Eng. 4(6): 541-554(1992)
- [2]
- ...
- [3]
- ...
- [4]
- Björn Bergsten, Michel Couprie, Patrick Valduriez:
Overview of Parallel Architectures for Databases.
Comput. J. 36(8): 734-740(1993)
- [5]
- Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez:
Prototyping Bubba, A Highly Parallel Database System.
IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990)
- [6]
- László Böszörményi, Johann Eder, Carsten Weich:
PPOST: A Parallel Database in Main Memory.
DEXA 1994: 754-758
- [7]
- George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller:
Data Placement In Bubba.
SIGMOD Conference 1988: 99-108
- [8]
- Zarka Cvetanovic:
The Effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems.
IEEE Trans. Computers 36(4): 421-432(1987)
- [9]
- David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen:
The Gamma Database Machine Project.
IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990)
- [10]
- David J. DeWitt, Jim Gray:
Parallel Database Systems: The Future of High Performance Database Systems.
Commun. ACM 35(6): 85-98(1992)
- [11]
- David Hung-Chang Du, J. S. Sobolewski:
Disk Allocation for Cartesian Product Files on Multiple-Disk Systems.
ACM Trans. Database Syst. 7(1): 82-101(1982)
- [12]
- ...
- [13]
- Hector Garcia-Molina, Kenneth Salem:
Main Memory Database Systems: An Overview.
IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992)
- [14]
- Shahram Ghandeharizadeh, David J. DeWitt:
A Multiuser Performance Analysis of Alternative Declustering Strategies.
ICDE 1990: 466-475
- [15]
- Shahram Ghandeharizadeh, David J. DeWitt, Waheed Qureshi:
A Performance Analysis of Alternative Multi-Attribute Declustering Strategies.
SIGMOD Conference 1992: 29-38
- [16]
- Goetz Graefe:
Volcano - An Extensible and Parallel Query Evaluation System.
IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994)
- [17]
- ...
- [18]
- ...
- [19]
- Kyung-Chang Kim:
Parallelism in Object-Oriented Query Processing.
ICDE 1990: 209-217
- [20]
- Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
ACM Trans. Database Syst. 9(1): 38-71(1984)
- [21]
- Jaideep Srivastava, Thomas M. Niccum, Bhaskar Himatsingka:
Data Declustering in PADMA: A PArallel Database MAnager.
IEEE Data Eng. Bull. 17(3): 3-13(1994)
- [22]
- Michael Stonebraker:
Introduction to the Special Issue on Database Prototype Systems.
IEEE Trans. Knowl. Data Eng. 2(1): 1-3(1990)
- [23]
- Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout:
The Design of XPRS.
VLDB 1988: 318-330
- [24]
- The Tandem Performance Group:
A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper).
SIGMOD Conference 1988: 337-341
- [25]
- ...
- [26]
- Arun K. Thakore, Stanley Y. W. Su:
Performance Analysis of Parallel Object-Oriented Query Processing Algorithms.
Distributed and Parallel Databases 2(1): 59-100(1994)
- [27]
- Patrick Valduriez:
Parallel Database Systems: Open Problems and New Issues.
Distributed and Parallel Databases 1(2): 137-165(1993)
- [28]
- Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers:
Parallelism in a Main-Memory DBMS: The Performance of PRISMA/DB.
VLDB 1992: 521-532
Copyright © Tue Mar 16 02:22:05 2010
by Michael Ley (ley@uni-trier.de)