Parallel evaluation of multi-join queries

ABSTRACT

A number of execution strategies for parallel evaluation of multi-join queries have been proposed in the literature; their performance was evaluated by simulation. In this paper we give a comparative performance evaluation of four execution strategies by implementing all of them on the same parallel database system, PRISMA/DB. Experiments have been done up to 80 processors. The basic strategy is to first determine an execution schedule with minimum total cost and then parallelize this schedule with one of the four execution strategies. These strategies, coming from the literature, are named: Sequential Parallel, Synchronous Execution, Segmented Right-Deep, and Full Parallel. Based on the experiments clear guidelines are given when to use which strategy.

REFERENCES

• Ame91: R America, ed., Proc of the PRISMA workshop on parallel database systems, Springer-Verlag, New York- Heidelberg-Berlin, 1991.
• ABF92: P. M. G. Apers , C. A. van den Berg , J. Flokstra , P. W. P. J. Grefen , M. L. Kersten , A. N. Wilschut, PRISMA/DB: A Parallel, Main Memory Relational DBMS, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.541-554, December 1992 [doi>10.1109/69.180605]
• ApW94: P. M. G. Apers & A. N. Wilschut, "Understanding large scale parallelism for data management ," in Keynote at the 3rd PDIS Conf, Austin, Texas, USA, September 1994.
• BDT83: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• BAC90: H. Boral , W. Alexander , L. Clay , G. Copeland , S. Danforth , M. Franklin , B. Hart , M. Smith , P. Valduriez, Prototyping Bubba, A Highly Parallel Database System, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.4-24, March 1990 [doi>10.1109/69.50903]
• BrG89: K. Bratbergsengen , T. Gjelsvik, The development of the CROSS8 and HC16-186 parallel (database) computers, Database Machines Sixth International Workshop, IWDM '89, Springer-Verlag New York, Inc., New York, NY, 1989
• CaK92: Felipe Cariño , Pekka Kostamaa, Exegesis of DBC/1012 and P-90 - Industrial Supercomputer Database Machines, Proceedings of the 4th International PARLE Conference on Parallel Architectures and Languages Europe, p.877-892, June 15-18, 1992
• CLY92: Ming-Syan Chen , Ming-Ling Lo , Philip S. Yu , Honesty 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, p.15-26, August 23-27, 1992
• CYW92: Ming-Syan Chen , Philip S. Yu , Kun-Lung Wu, Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries, Proceedings of the Eighth International Conference on Data Engineering, p.58-67, February 03-07, 1992
• DGS90: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• DeG92: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• Gre92: P. W. P. J. Grefen, Integrity control in paratlet database systems, PhD-Thesis, University of Twente, 1992.
• GWF91: R W. R J. Grefen, A. N. Wilschut & J. Flokstra, "PRISMA/DBI User Manual," Memorandum INF91-06, Universiteit Twente, Enschede, The Netherlands, 1991.
• HoS91: Wei Hong , Michael Stonebraker, Optimization of parallel query execution plans in XPRS, Proceedings of the first international conference on Parallel and distributed information systems, p.218-225, December 1991, Miami, Florida, United States
• HWF93: Maurice A. W. Houtsma , Annita N. Wilschut , Jan Flokstra, Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithm on PRISMA/DB, Proceedings of the 19th International Conference on Very Large Data Bases, p.206-217, August 24-27, 1993
• HCY94: Hui-I Hsiao , Ming-Syan Chen , Philip S. Yu, On parallel execution of multiple pipelined hash joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.185-196, May 24-27, 1994, Minneapolis, Minnesota, United States
• KBZ86: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• LVZ93: Rosana S. G. Lanzelotte , Patrick Valduriez , Mohamed Zaït, On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces, Proceedings of the 19th International Conference on Very Large Data Bases, p.493-504, August 24-27, 1993
• LST91: Hongjun Lu , Ming-Chien Shan , Kian-Lee Tan, Optimization of Multi-Way Join Queries for Parallel Execution, Proceedings of the 17th International Conference on Very Large Data Bases, p.549-560, September 03-06, 1991
• Sch90: Donovan Alfred Schneider , David J. Dewitt, Complex query processing in multiprocessor database machines, 1990
• ScD89: Donovan A. Schneider , David J. DeWitt, A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.110-121, June 1989, Portland, Oregon, United States
• ScD90: Donovan A. Schneider , David J. DeWitt, Tradeoffs in processing complex join queries via hashing in multiprocessor database machines, Proceedings of the sixteenth international conference on Very large databases, p.469-480, September 1990, Brisbane, Australia
• SAC79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• SHV92: Myra Spiliopoulou , Michael Hatzopoulos , Costas Vassilakis, Using Parallelism and Pipeline for the Optimisation of Join Queries, Proceedings of the 4th International PARLE Conference on Parallel Architectures and Languages Europe, p.279-294, June 15-18, 1992
• SrE93: Jaideep Srivastava, Optimizing multi-join queries in parallel relational databases, Proceedings of the second international conference on Parallel and distributed information systems, p.84-92, January 1993, San Diego, California, United States
• SKP88: Michael Stonebraker , Randy H. Katz , David A. Patterson , John K. Ousterhout, The Design of XPRS, Proceedings of the 14th International Conference on Very Large Data Bases, p.318-330, August 29-September 01, 1988
• SwG88: Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
• Wil93: A.N. Wilschut, Parallel query execution in a main-memory database system., PhD-Thesis, University of Twente, 1993.
• WiA91: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
• WiA93: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Distributed and Parallel Databases, v.1 n.1, p.103-128, Jan. 1993 [doi>10.1007/BF01277522]
• WiA90: A. N. Wilschut & E M. G. Apers, "Pipelining in query execution," in Proc of the International Conference on Databases, Parallel Architectures and their Applications, Miami, USA, March i990.
• WAF91: Annita N. Wilschut , Peter M. G. Apers , Jan Flokstra, Parallel query execution in PRISMA/DB, Proceedings of the PRISMA workshop on Parallel database systems, p.424-433, June 1991, Noordwijk, The Netherlands
• WFA92: Annita N. Wilschut , Jan Flokstra , Peter M. G. Apers, Parallelism in a Main-Memory DBMS: The Performance of PRISMA/DB, Proceedings of the 18th International Conference on Very Large Data Bases, p.521-532, August 23-27, 1992
• WiG93: Annita N. Wilschut , Stephan A. van Gils, A Model for Pipelined Query Execution, Proceedings of the International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.225-232, January 17-20, 1993
• ZZS93: Mikal Ziane , Mohamed Zaït , Pascale Borla-Salamet, Parallel query processing in DBS3, Proceedings of the second international conference on Parallel and distributed information systems, p.93-102, January 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Experimentation, Performance