Join and Semijoin Algorithms for a Multiprocessor Database Machine

ACM Transactions on Database Systems - Tập 9 Số 1 - Trang 133-161 - 1984
Patrick Valduriez1, Georges Gardarin1
1INRIA and University of Paris VI

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

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

10.1145/320064.320065

10.1145/582250.582265

10.1145/320289.320292

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

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. 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.

10.1147/sj.164.0363

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. 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.

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 ). 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).

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. 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.

10.1145/362384.362685

10.1145/582095.582098

10.1145/582250.582266

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

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

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

10.1145/500080.500089

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

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 ). 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).

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

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

10.1145/320544.320553

10.1109/TC.1978.1675167

10.1145/320128.320129

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

10.1145/320473.320476

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

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

Thông tin
Thông tin xuất bản

ACM Transactions on Database Systems

Tập 9 Số 1

133-161

Thông tin tác giả