Abstract
The barriers to parallel query execution are start-up time of parallel operations, interference and poor load balancing among the processors due to skewed data distribution. In this paper, we have described how these problems are addressed in DBS3, a shared-memory database system implemented on a 72-node KSR1 multiprocessor.
Our solution combines the advantages of static and dynamic partitioning. We use static partitioning of relations to reduce interference and dynamic allocation of processors to operations to reduce start-up time and improve load balancing. A major advantage of this solution is to be able to deal efficiently with skew by allowing each thread to dynamically choose which operation's instance it will execute. A performance analysis on our prototype with databases of the Wisconsin benchmark confirm these results. More information on this work can be found in http://rodin.inria.fr/bouganim.
This work has been partially funded by the CEC under ESPRIT project IDEA.
Preview
Unable to display preview. Download preview PDF.
References
B. Bergsten, M. Couprie, P. Valduriez, “Prototyping DBS3, a shared-memory parallel database system”. Int. Conf. on Parallel and Distributed Information Systems, Florida, USA, December 1991.
P. Borla-Salamet, C. Chachaty, B. Dageville, “Compiling Control into Database Queries for Parallel Execution Management”. Int. Conf. on Parallel and Distributed Information Systems, Florida, USA, December 1991.
C. Chachaty, P. Borla-Salamet, M. Ward, “A Compositional Approach for the Design of a Parallel Query Processing Language”, Int. Conf. on Parallel Architectures and Language Europe, Paris, France, June 1992.
B. Dageville, P. Casadessus, P. Borla-Salamet, “The Impact of the KSR1 AllCache Architecture on the Behaviour of the DBS3 Parallel DBMS”, Int. Conf. on Parallel Architectures and Language Europe, Athens, Greece, July 1994.
G. Gardarin, P. Valduriez, “ESQL2, an Extended SQL2 with F-logic Semantics.”, IEEE Int. Conf. on Data Engineering, Phoenix, Arizona, February 1992.
R. Lanzelotte, P. Valduriez, M. Zait, M. Ziane, “Industrial-Strength Parallel Query Optimization: issues and lessons”, Information Systems, Vol. 19, No. 4, 1994.
P. Valduriez, “Parallel Database Systems: open problems and new issues.”, Int. Journal on Distributed and Parallel Databases, Vol. 1, No. 2, 1993.
G. K. Zipf, Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology, Reading, MA, Addison-Wesley, 1949.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bouganim, L., Dageville, B., Valduriez, P. (1996). Adaptive parallel query execution in DBS3. In: Apers, P., Bouzeghoub, M., Gardarin, G. (eds) Advances in Database Technology — EDBT '96. EDBT 1996. Lecture Notes in Computer Science, vol 1057. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014172
Download citation
DOI: https://doi.org/10.1007/BFb0014172
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61057-1
Online ISBN: 978-3-540-49943-5
eBook Packages: Springer Book Archive