article

Free access

Join and Semijoin Algorithms for a Multiprocessor Database Machine

Editor: Robert W. Taylor Authors:

Patrick Valduriez,

Georges GardarinAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 9, Issue 1

Pages 133 - 161

https://doi.org/10.1145/348.318590

Published: 23 March 1984 Publication History

Abstract

This paper presents and analyzes algorithms for computing joins and semijoins of relations in a multiprocessor database machine. First, a model of the multiprocessor architecture is described, incorporating parameters defining I/O, CPU, and message transmission times that permit calculation of the execution times of these algorithms. Then, three join algorithms are presented and compared. It is shown that, for a given configuration, each algorithm has an application domain defined by the characteristics of the operand and result relations. Since a semijoin operator is useful for decreasing I/O and transmission times in a multiprocessor system, we present and compare two equi-semijoin algorithms and one non-equi-semijoin algorithm. The execution times of these algorithms are generally linearly proportional to the size of the operand and result relations, and inversely proportional to the number of processors. We then compare a method which consists of joining two relations to a method whereby one joins their semijoins. Finally, it is shown that the latter method, using semijoins, is generally better. The various algorithms presented are implemented in the SABRE database system; an evaluation model selects the best algorithm for performing a join according to the results presented here. A first version of the SABRE system is currently operational at INRIA.

References

[1]

AUER, H. ET AL. R.D.B.M.: a relational database machine. Internal Rep. nr8005, Technisch Univ. Braunchweig, June 1980.

[2]

BABB, E. Implementing a relational database by means of specialized hardware. ACM Trans. Database Syst. 4, 1 (March 1979), 1-29.

Digital Library

[3]

BANCILHON, F.; AND SCHOLL, M. Design of a back-end processor for a database machine. In Proc. ACM-SIGMOD (Santa Monica, Calif., May 1980), ACM, New York, 1980.

Digital Library

[4]

BANERJEE, J.; HSlAO, D.K.; AND BAUM, R.I. Concepts and capabilities of a database computer. ACM Trans. Database Syst. 3, 4 (Dec. 1978), 347-384.

Digital Library

[5]

BERNSTEIN, P.A.; AND CHIU, D.M. Using semijoins to solve relational queries.

[6]

BERNSTEIN, P.A.; AND GOODMAN, N. Full reducers for relational queries using multiattribute semijoins. In Proc. 1979 NBS Symposium on Computer Networks (Dec. 1979), NBS, Washington, D.C.

[7]

BERNSTEIN, P.A.; AND GOODMAN, N. Inequality semijoins. Tech. Rep. CCA-79-28, Computer Corp. of America, Cambridge, Mass., Dec. 1979.

[8]

BLASGEN, M.W.; AND ESWARAN, K.P. Storage and access in relational databases. IBM Syst. J. 16, 4 (1977), 363-378.

Digital Library

[9]

BORAL, H.; DEW}TT, D.J.; FRIEDLAND, D.; AND WILKINSON, W.K. Parallel algorithms for the execution of relational operations. Tech. Rep. 402, Computer Science Dept., Univ. of Wisconsin, Madison, Jan. 1980.

[10]

BORAL, H.; DEWITT, D.J.; AND WILKINSON, W.K. Performances evaluation of associative disk designs. In 6th Workshop on Computer Architecture for Nonnurneric Processing (Hyeres, France, June 1981), ACM, New York, 1981.

[11]

CHAMBERLIN, D.D.; GILBERT, A.M.; AND YOST, R.A. A history of System-R and SQL/data system. In 7th International Conference on Very Large Data Bases (Cannes, France, Sept. 1981).

[12]

CHIU, D.M.; AND HO, Y.C. A methodology for interpreting tree queries into optimal semijoin expressions. ACM Trans. Database Syst. 5, 4 (Dec. 1980), 169-178.

[13]

CODD, E.F. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387.

Digital Library

[14]

DEWITT, D.J. Query execution in DIRECT. In Proc. of the ACM-SIGMOD 1979 International Conference on Management of Data (May 1979), ACM, New York, 1979, pp 13-22.

Digital Library

[15]

BORAL, H.; AND DEWlTT, D.J. Design considerations for data-flow database machines. In Proc. of the ACM-SIGMOD Conference on Management of Data (Los Angeles, Calif., 1980), ACM, New York, 1980, pp 94-104.

Digital Library

[16]

FAUDEMAY, P. Sur une nouvelle classe de filtres multiexpressions. J. Machines Bases de Donnees (Sophia Antipolis, Sept. 1980), INRIA.

[17]

FINGER, U.; AND MEDIGUE, G. Architectures multimicroprocesseurs et disponibilith: la SM90. L'echo des Recherches 105 (July 1981).

[18]

GARDARIN, G. An introduction to SABRE: a multimicmprocessor database machine. In 6th Workshop on Computer Architecture for Nonnumeric Processing (Hyeres, France, June 1981).

[19]

GOTLIEB, L.R. Computing joins of relations. In Proc. of the ACM-SIGMOD Conference on Management of Data (San Jose, Calif., May 1975), ACM, New York, 1975, pp 55-63.

Digital Library

[20]

INTEL. Les concepts systemes d'intel: le multibus et ses signaux. E.A.I.263, A. Sabatier, Intel- France, Feb. 1979.

[21]

KARLSSON, K. Reduced cover-trees and their application in the SABRE access path model. In 7th International Con{erence on Very Large Data Bases (Cannes, France, Sept. 1981).

[22]

KNUTH, D.E. The Art o{ Computers Programming; vol. 3: Sorting and Searching, Addison- Wesley, Reading, Mass., 1973.

Digital Library

[23]

LEBIHAN, J., ET AL. SIRIUS: a French nationwide project on distributed databases. In 6th International Conference on Very Large Databases (Montreal, 1980).

[24]

OZKARAHAN, E.A.; SCHUSTER, S.A.; AND SEVCIK, K.C. Performance evaluation of a relational associative processor. ACM Trans. Database Syst. 2, 2 (June 1977), 175-196.

Digital Library

[25]

PREPARATA, F.P. New parallel-sorting schemes. IEEE Trans. Comput. C-27 (July 1978).

Digital Library

[26]

ROTHNIE, J.B., ET AL. SDDI: a system for distributed databases. ACM Trans. Database Syst. 5, 1 (March 1980), 1-17.

Digital Library

[27]

ROHMER, J. Machines et langages pour traiter les ensembles de donnees (textes, tableaux, fichiers). These d'Etat, Grenoble, Dec. 1980.

[28]

STONEBRAKER, M., WONG, E.; AND KREPS, P. The design and implementation of INGRES. ACM Trans. Database Syst. 1, 3 (Sept. 1976).

Digital Library

[29]

VALDURIEZ, P. Algorithmes de jointures de relations. Colloque Les Bases de Donnees {Tunis, April 1981), AFCET.

[30]

WAH, B.W.; AND YAO, S.B. DIALOGUE: a distributed-processor organization for a database machine. In 1980 National Computer Conference, pp 243-253.

Cited By

Zhang YChronis YPatel JRekatsinas T(2023)Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and AnalysisProceedings of the VLDB Endowment10.14778/3611479.361150116:11(2962-2975)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611501
Ding BChaudhuri SNarasayya VMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Bitvector-aware Query Optimization for Decision Support QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389769(2011-2026)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389769
Whitman RMarsh BPark MHoel E(2019)Distributed Spatial and Spatio-Temporal Join on Apache SparkACM Transactions on Spatial Algorithms and Systems10.1145/33251355:1(1-28)Online publication date: 27-Jun-2019
https://dl.acm.org/doi/10.1145/3325135
Show More Cited By

Index Terms

Join and Semijoin Algorithms for a Multiprocessor Database Machine
1. General and reference
  1. Document types

Recommendations

Semi-join algorithms for multiprocessor systems
SIGMOD '82: Proceedings of the 1982 ACM SIGMOD international conference on Management of data

Semi-join is a relational operator that decreases the cost of processing queries involving binary operations. This is accomplished by initially selecting the data relevant to answer the queries and thereby reducing the size of the operand relations. ...
Improvement Algorithms for Semijoin Query Processing Programs in Distributed Database Systems

The problem of optimal query processing in distributed database systems was shown to be NP-hard. This means that heuristic algorithms are necessary to solve the query processing problem. In this paper, we describe algorithms to improve the solutions ...
A Pipeline N-Way Join Algorithm Based on the 2-Way Semijoin Program

The semijoin has been used as an effective operator in reducing data transmission and processing over a network that allows forward size reduction of relations and intermediate results generated during the processing of a distributed query. The authors ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 9, Issue 1

March 1984

161 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/348

Editor:
Robert W. Taylor
IBM Research Laboratory, San Jose, CA

Issue’s Table of Contents

Copyright © 1984 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 1984

Published in TODS Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

205
Total Citations
View Citations
1,255
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)20

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YChronis YPatel JRekatsinas T(2023)Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and AnalysisProceedings of the VLDB Endowment10.14778/3611479.361150116:11(2962-2975)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611501
Ding BChaudhuri SNarasayya VMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Bitvector-aware Query Optimization for Decision Support QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389769(2011-2026)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389769
Whitman RMarsh BPark MHoel E(2019)Distributed Spatial and Spatio-Temporal Join on Apache SparkACM Transactions on Spatial Algorithms and Systems10.1145/33251355:1(1-28)Online publication date: 27-Jun-2019
https://dl.acm.org/doi/10.1145/3325135
Sinuraya JRezky STarigan M(2019)Data Search Using Hash Join Query and Nested Join QueryJournal of Physics: Conference Series10.1088/1742-6596/1361/1/0120791361(012079)Online publication date: 18-Dec-2019
https://doi.org/10.1088/1742-6596/1361/1/012079
Bressan S(2018)Semijoin ProgramEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_709(3440-3444)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_709
Sattler K(2018)SemijoinEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_706(3436-3440)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_706
Roy AOlmsted A(2017)Distributed query processing and data sharing2017 12th International Conference for Internet Technology and Secured Transactions (ICITST)10.23919/ICITST.2017.8356387(221-224)Online publication date: Dec-2017
https://doi.org/10.23919/ICITST.2017.8356387
Zhu JPotti NSaurabh SPatel J(2017)Looking ahead makes query plans robustProceedings of the VLDB Endowment10.14778/3090163.309016710:8(889-900)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.14778/3090163.3090167
Whitman RPark MMarsh BHoel E(2017)Spatio-Temporal Join on Apache SparkProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139963(1-10)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139963
Lawrence R(2017)Faster Querying for Database Integration and Virtualization with Distributed Semi-Joins2017 International Conference on Computational Science and Computational Intelligence (CSCI)10.1109/CSCI.2017.246(1406-1410)Online publication date: Dec-2017
https://doi.org/10.1109/CSCI.2017.246
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents