article

Free access

Exploiting inter-operation parallelism in XPRS

Author:

Wei HongAuthors Info & Claims

ACM SIGMOD Record, Volume 21, Issue 2

Pages 19 - 28

https://doi.org/10.1145/141484.130292

Published: 01 June 1992 Publication History

PDF eReader

Abstract

In this paper, we study the scheduling and optimization problems of parallel query processing using interoperation parallelism in a shared-memory environment and propose our solutions for XPRS. We first study the scheduling problem of a set of a continuous sequence of independent tasks that are either from a bushy tree plan of a single query or from the plans of multiple queries, and present a clean and simple scheduling algorithm. Our scheduling algorithm achieves maximum resource utilizations by running an IO-bound task and a CPU-bound task in parallel with carefully calculated degrees of parallelism and maintains the maximum resource utilizations by dynamically adjusting the degrees of parallelism of running tasks whenever necessary. Real performance figures are shown to confirm the effectiveness of our scheduling algorithm. We also revisit the optimization problem of parallel execution plans of a single query and extend our previous results to consider inter-operation parallelism by introducing a new cost estimation method to the query optimizer based on our scheduling algorithm.

References

[1]

Bhide, A. and Stonebraker, M., "A Performance Comparison of Two Architectures for Fast Transaction Processing," Proceedings of 1988 International Conference on Data Engineering.

Digital Library

Google Scholar

[2]

Copeland, O., et. al., "Data Placement in Bubba," Proceedings of 1988 ACM- SIGMOD International Conference on Management of Data, Chicago, IL, June 1988.

Digital Library

Google Scholar

[3]

Dewitt, D., et al, "The Gamma Database Machine Project," IEEE Transactions on Knowledge and Data Engineering, Vol. 2, No. 1, March 1990.

Digital Library

Google Scholar

[4]

Graefe, G., "Encapsulation of Parallelism in the Volcano Query Processing System," Proceedings of 1990 ACM-SIGMOD International Conference on Management of Data.

Digital Library

Google Scholar

[5]

Hong, W. and Stonebraker, M., "Optimization of Parallel Query Execution Plans in XPRS," Proceedings of the 1st International Conference on Parallel and Distributed Information Systems, Miami, Florida, December 1991.

Digital Library

Google Scholar

[6]

Lu, H., et al, "Optimization of Multi-Way Join Queries for Parallel Execution," Proceedings of 1991 International Conference on Very Large Data Bases.

Digital Library

Google Scholar

[7]

Pirahesh, H., et al, "Parallelism in Relational Database Systems' Architectural issues and Design Approaches," Proceedings of the 2nd International Symposium on Database in Parallel and Distributed Systems, July 1990.

Digital Library

Google Scholar

[8]

Schneider, D. and Dewitt, D., "Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines," Proceedings of 1990 International Conference on Very Large Data Bases.

Digital Library

Google Scholar

[9]

Stonebraker, M., "The Case for Shared Nothing," Proceedings of 1986 International Conference on Data Engineering.

Google Scholar

[10]

Stonebraker, M., et. al., "The Design of XPRS," Proceedings of 1988 international Conference on Very Large Data Bases.

Digital Library

Google Scholar

[11]

Stonebraker, S., et al, "The Postgres Next Generation DBMS," Communications of ACM, vol. 34 no. 10, pp. 78-92, October 1991.

Digital Library

Google Scholar

Cited By

View all

Jankov DYuan BLuo SJermaine C(2021)Distributed numerical and machine learning computations via two-phase execution of aggregated join treesProceedings of the VLDB Endowment10.14778/3450980.345099114:7(1228-1240)Online publication date: 12-Apr-2021
https://dl.acm.org/doi/10.14778/3450980.3450991
Bouganim L(2018)Query Load Balancing in Parallel Database SystemsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_1080(3004-3008)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_1080
Bouganim L(2017)Query Load Balancing in Parallel Database SystemsEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_1080-2(1-5)Online publication date: 1-Aug-2017
https://doi.org/10.1007/978-1-4899-7993-3_1080-2
Show More Cited By

Recommendations

Exploiting inter-operation parallelism in XPRS
SIGMOD '92: Proceedings of the 1992 ACM SIGMOD international conference on Management of data

In this paper, we study the scheduling and optimization problems of parallel query processing using interoperation parallelism in a shared-memory environment and propose our solutions for XPRS. We first study the scheduling problem of a set of a ...
Exploiting Inter-Operation Parallelism in XPRS
Exploiting Distributed-Memory and Shared-Memory Parallelism on Clusters of SMPs with Data Parallel Programs

Clusters of SMPs are hybrid-parallel architectures that combine the main concepts of distributed-memory and shared-memory parallel machines. Although SMP clusters are widely used in the high performance computing community, there exists no single ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGMOD Record Volume 21, Issue 2

June 1, 1992

415 pages

ISSN:0163-5808

DOI:10.1145/141484

Editor:
Michael Stonebraker

Issue’s Table of Contents

SIGMOD '92: Proceedings of the 1992 ACM SIGMOD international conference on Management of data
June 1992
416 pages
ISBN:0897915216
DOI:10.1145/130283
Editor:
Michael Stonebraker
Univ. of California at Berkeley

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1992

Published in SIGMOD Volume 21, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
197
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)9

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jankov DYuan BLuo SJermaine C(2021)Distributed numerical and machine learning computations via two-phase execution of aggregated join treesProceedings of the VLDB Endowment10.14778/3450980.345099114:7(1228-1240)Online publication date: 12-Apr-2021
https://dl.acm.org/doi/10.14778/3450980.3450991
Bouganim L(2018)Query Load Balancing in Parallel Database SystemsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_1080(3004-3008)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_1080
Bouganim L(2017)Query Load Balancing in Parallel Database SystemsEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_1080-2(1-5)Online publication date: 1-Aug-2017
https://doi.org/10.1007/978-1-4899-7993-3_1080-2
Bouganim L(2009)Query Load Balancing in Parallel Database SystemsEncyclopedia of Database Systems10.1007/978-0-387-39940-9_1080(2268-2272)Online publication date: 2009
https://doi.org/10.1007/978-0-387-39940-9_1080
Taniar DLeung CRahayu WGoel S(2008)BibliographyHigh‐Performance Parallel Database Processing and Grid Databases10.1002/9780470391365.biblio(511-539)Online publication date: 11-Mar-2008
https://doi.org/10.1002/9780470391365.biblio
Hameurlain AMorvan F(2006)A cost evaluator for parallel database systemsDatabase and Expert Systems Applications10.1007/BFb0049113(146-156)Online publication date: 1-Feb-2006
https://doi.org/10.1007/BFb0049113
Hameurlain AMorvan F(2005)Parallel relational database systems: Why, how and beyondDatabase and Expert Systems Applications10.1007/BFb0034690(302-312)Online publication date: 26-Jun-2005
https://doi.org/10.1007/BFb0034690
Rahm E(2005)Dynamic load balancing in parallel database systemsEuro-Par'96 Parallel Processing10.1007/3-540-61626-8_4(37-52)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-61626-8_4
Hameurlain AMorvan F(2005)Exploiting inter-operation parallelism for SQL query optimizationDatabase and Expert Systems Applications10.1007/3-540-58435-8_242(759-768)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-58435-8_242
Jianzhong Li Zhipeng Cai Shuoying Chen (2000)Multi-weighted tree based query optimization method for parallel relational database systemsProceedings of the Third International Symposium on Cooperative Database Systems for Advanced Applications. CODAS 200110.1109/CODAS.2001.945166(186-193)Online publication date: 2000
https://doi.org/10.1109/CODAS.2001.945166
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Exploiting inter-operation parallelism in XPRS

Exploiting Inter-Operation Parallelism in XPRS

Exploiting Distributed-Memory and Shared-Memory Parallelism on Clusters of SMPs with Data Parallel Programs