Article

Free access

On optimal processor allocation to support pipelined hash joins

Authors:

Ming-Syan Syan Chen,

C. V. Ravishankar,

Philip S. YuAuthors Info & Claims

SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of data

Pages 69 - 78

https://doi.org/10.1145/170035.170053

Published: 01 June 1993 Publication History

Abstract

In this paper, we develop algorithms to achieve optimal processor allocation for pipelined hash joins in a multiprocessor-based database system. A pipeline of hash joins is composed of several stages, each of which is associated with one join operation. The whole pipeline is executed in two phases: (1) the table-building phase, and (2) the tuple-probing phase. We focus on the problem of allocating processors to the stages of a pipeline to minimize the query execution time. We formulate the processor allocation problem as a two-phase mini-max optimization problem, and develop three optimal allocation schemes under three different constraints. The effectiveness of our problem formulation and solution is verified through a detailed tuple-by-tuple simulation of pipelined hash joins. Our solution scheme is general and applicable to any optimal resource allocation problem formulated as a two-phase mini-max problem.

References

[1]

H. Boral, W. Alexander, et al. Prototyping Bubba, A Highly Parallel Database System. IEEE Transactions on Knowledge and Da#a Engineering, 2(1):4-24, March 1990.

Digital Library

[2]

M.-S. Chen, M.-L. Lo, P. S. Yu, and Y. C. Young. Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins. Proceedings of the 18th International Conference on Very Large Data Bases, page5 15-26, August 1992.

Digital Library

[3]

M.-S. Chen, P. S. Yu, and K.-L. Wu. Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries. Proceedings of the 8th International Conference on Data Engineering, pages 58-67, February 1992.

Digital Library

[4]

D. j. DeWigt and R. Gerber. Multiproceasor Hash-Based Join Algorithms. Proceedings of the 11th International Conference on Very Large Data Bases, pages 151-162, August 1985.

[5]

D. J. DeWitt, S. Ghandeharizadeh, D. A. Schneider, A. Bricker, H.I. Hsiao, and R. Rasmussen. The Gamma Database Machine Project. IEEE Transactions on Knowledge and Data Engineering, 2(1):44-62, March 1990.

Digital Library

[6]

D. J. DeWitt and J. Gray. Parallel Database Systems: The Future of High Performance Database Systems. Comm. of ACM, 35(6):85-98, June 1992.

Digital Library

[7]

W. Hong. Exploiting Inter-Operator Parallelism in XPRS. Proceedings of A CM SIGMOD, pages 19- 28, June 1992.

Digital Library

[8]

K. Hun, Y.-L. Lo, and H. C. Young. Including the Load Balancing Issue in the Optimization of Multi- Way Join Queries for Shared-Nothing Database Computers. Proceedings of the 2nd Conference on Parallel and Distributed Information Systems, pages 74-83, January 1993.

Digital Library

[9]

T. Ibaraki and N. Katoh. Resource Allocation Problems: Algorithmic Approaches. The MIT Press, Cambridge, Massachusetts, 1988.

Digital Library

[10]

M. Kitsuregawa, H. Tanaka, and T. Moto-Oka. Architecture and Performance of Relational Algebra Machine GRACE. Proceedings of the International Conference on Parallel Processing, pages 241-250, August 1984.

[11]

M.-L. Lo, M.-S. Chen, C. V. Ravishankar, and P. S. Yu. Optimal Processor Allocation for Pipelined Hash Joins. IBM Research Report, RC 18303, September 1992.

[12]

R. A. Lorie, J.-J. Daudenarde, J. W. Stamos, and H. C. Young. Exploiting Database Parallelism In A Message-Passing Multiprocessor. IBM journal of Research and Development, 35(5/6):681-695, September/November 1991.

Digital Library

[13]

H. Lu, K. L. Tan, and M.-C. Shan. Hash- Based Join Algorithms for Multiprocessor Computers with Shared Memory. Proceedings of the 16th International Conference on Very Large Data Bases, pages 198-209, August 1990.

Digital Library

[14]

P. Mishra and M. H. Etch. Join Processing in Relational Databases. A CM Computing Surveys, 24(1):63-113, March 1992.

Digital Library

[15]

N. Roussopoulos and H. Kang. A Pipeline N- Way Join Algorithm Based on the 2-Way Semijoin Program. IEEE Transactions on Knowledge and Data Engineering, 3(4):461-473, December 1991.

Digital Library

[16]

D. Schneider and D. J. DeWitt. Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. Proceedings of the 16th International Conference on Very Large Data Bases, pages 469-480, August 1990.

Digital Library

[17]

M. Stonebraker, R. Katz, D. Patterson, and j. Ousterlaout. The Design of XPR#. P#'oeeed#ng8 of the l$th International Conference on Very Large Data Bases, pages 318-330, 1988.

Digital Library

[18]

A. Wilschut and P. Apers. Datafiow Query Execution in Parallel Main-Memory Environment. Proceedings of the 1st Conference on Parallel and Distributed Information Systems, pages 68-77, December 1991.

Digital Library

[19]

P. S. Yu, M.-S. Chen, H. Heiss, and S. H. Lee. On Workload Characterization of Relational Database Environments. IEEE Transactions on Software Engineering, 18(4):347-355, April 1992.

Digital Library

Cited By

Viglas S(2014)A Comparative Study of Implementation Techniques for Query Processing in Multicore SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2012.24326:1(3-15)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1109/TKDE.2012.243
Han HJung HEom HYeom H(2011)Scatter-Gather-MergeCluster Computing10.1007/s10586-010-0144-514:2(183-197)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s10586-010-0144-5
Li RChen LLi W(2010)Cloudweaver: Adaptive and Data-Driven Workload Manager for Generic CloudsHandbook of Cloud Computing10.1007/978-1-4419-6524-0_9(219-236)Online publication date: 27-Aug-2010
https://doi.org/10.1007/978-1-4419-6524-0_9
Show More Cited By

Recommendations

On optimal processor allocation to support pipelined hash joins

In this paper, we develop algorithms to achieve optimal processor allocation for pipelined hash joins in a multiprocessor-based database system. A pipeline of hash joins is composed of several stages, each of which is associated with one join operation. ...
Register allocation for software pipelined multi-dimensional loops
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Software pipelining of a multi-dimensional loop is an important optimization that overlaps the execution of successive outermost loop iterations to explore instruction-level parallelism from the entire n-dimensional iteration space. This paper ...
Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins

The pipelined execution of multijoin queries in a multiprocessor-based database system is explored in this paper. Using hash-based joins, multiple joins can be pipelined so that the early results from a join, before the whole join is completed, are sent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of data

June 1993

566 pages

ISBN:0897915925

DOI:10.1145/170035

Editors:
Peter Buneman
Univ. of Pennsylvania
,
Sushil Jajodia

ACM SIGMOD Record Volume 22, Issue 2
June 1, 1993
558 pages
ISSN:0163-5808
DOI:10.1145/170036
Editors:
Peter Buneman
Univ. of Pennsylvania
,
Sushil Jajodia,
Won Kim
UniSQL, Inc., Austin, TX
Issue’s Table of Contents

Copyright © 1993 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS93

Sponsor:

SIGMOD/PODS93: Joint ACM SIGMOD International Conference on Management of Data and ACM SIGMOD

May 25 - 28, 1993

D.C., Washington, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
417
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)21

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Viglas S(2014)A Comparative Study of Implementation Techniques for Query Processing in Multicore SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2012.24326:1(3-15)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1109/TKDE.2012.243
Han HJung HEom HYeom H(2011)Scatter-Gather-MergeCluster Computing10.1007/s10586-010-0144-514:2(183-197)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s10586-010-0144-5
Li RChen LLi W(2010)Cloudweaver: Adaptive and Data-Driven Workload Manager for Generic CloudsHandbook of Cloud Computing10.1007/978-1-4419-6524-0_9(219-236)Online publication date: 27-Aug-2010
https://doi.org/10.1007/978-1-4419-6524-0_9
Luo YAntoniou GSterling L(2007)Incorporating Security Requirements into Communication Protocols in Multi-agent Software SystemsProceedings of the Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies10.1109/PDCAT.2007.53(159-160)Online publication date: 3-Dec-2007
https://dl.acm.org/doi/10.1109/PDCAT.2007.53
Liu BRundensteiner EBratbergsengen K(2005)Revisiting pipelined parallelism in multi-join query processingProceedings of the 31st international conference on Very large data bases10.5555/1083592.1083688(829-840)Online publication date: 30-Aug-2005
https://dl.acm.org/doi/10.5555/1083592.1083688
Ganguly SGerasoulis AWang W(2005)Partitioning pipelines with communication costsInformation Systems and Data Management10.1007/3-540-60584-3_40(302-320)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-60584-3_40
Weikum G(2005)Tutorial on parallel database systemsDatabase Theory — ICDT '9510.1007/3-540-58907-4_3(33-37)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-58907-4_3
Datta AVanderMeer DRamamritham K(2002)Parallel Star Join + DataIndexesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2002.104776914:6(1299-1316)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1109/TKDE.2002.1047769
Gopal RRamesh RZionts S(2001)Criss-Cross Hash JoinsIEEE Transactions on Knowledge and Data Engineering10.1109/69.94073713:4(637-653)Online publication date: 1-Jul-2001
https://dl.acm.org/doi/10.1109/69.940737
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.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents