Join and Semijoin Algorithms for a Multiprocessor Database Machine

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: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• 3: François Bancilhon , Micheł Scholl, Design of a backend processor for a data base machine, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582265]
• 4: Jayanta Banerjee , David K. Hsiao , Richard I. Baum, Concepts and capabilities of a database computer\, ACM Transactions on Database Systems (TODS), v.3 n.4, p.347-384, Dec. 1978 [doi>10.1145/320289.320292]
• 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.
• 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: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 14: David J. DeWitt, Query execution in DIRECT, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582098]
• 15: Haran Boral , David J. DeWitt, Design considerations for data-flow database machines, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582266]
• 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: Leo R. Gotlieb, Computing joins of relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500089]
• 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: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 23: LEBIHAN, J., ET AL. SIRIUS: a French nationwide project on distributed databases. In 6th International Conference on Very Large Databases (Montreal, 1980).
• 24: E. A. Ozkarahan , S. A. Schuster , K. C. Sevcik, Performance evaluation of a relational associative processor, ACM Transactions on Database Systems (TODS), v.2 n.2, p.175-195, June 1977 [doi>10.1145/320544.320553]
• 25: PREPARATA, F.P. New parallel-sorting schemes. IEEE Trans. Comput. C-27 (July 1978).
• 26: J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980 [doi>10.1145/320128.320129]
• 27: ROHMER, J. Machines et langages pour traiter les ensembles de donnees (textes, tableaux, fichiers). These d'Etat, Grenoble, Dec. 1980.
• 28: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 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.

INDEX TERMS

Primary Classification:
  A. General Literature