On optimal processor allocation to support pipelined hash joins

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 , 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]
• 2: 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
• 3: 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
• 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 , 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]
• 6: 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]
• 7: Wei Hong, Exploiting inter-operation parallelism in XPRS, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.19-28, June 02-05, 1992, San Diego, California, United States
• 8: Kien A. Hua , Honesty C. Young , Yu-lung Lo, Including the load balancing issue in the optimization of multi-way join queries for shared-nothing database computers, Proceedings of the second international conference on Parallel and distributed information systems, p.74-83, January 1993, San Diego, California, United States
• 9: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 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 , H. C. Young, Exploiting database parallelism in a message-passing multiprocessor, IBM Journal of Research and Development, v.35 n.5-6, p.681-695, Sept./Nov. 1991
• 13: Hongjun Lu , Kian-Lee Tan , Ming-Chien Sahn, Hash-based join algorithms for multiprocessor computers with shared memory, Proceedings of the sixteenth international conference on Very large databases, p.198-209, September 1990, Brisbane, Australia
• 14: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 15: N. Roussopoulos , H. Kang, A Pipeline N-Way Join Algorithm Based on the 2-Way Semijoin Program, IEEE Transactions on Knowledge and Data Engineering, v.3 n.4, p.486-495, December 1991 [doi>10.1109/69.109109]
• 16: 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
• 17: 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
• 18: 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
• 19: Philip S. Yu , Ming-Syan Chen , Hans-Ulrich Heiss , Sukho Lee, On Workload Characterization of Relational Database Environments, IEEE Transactions on Software Engineering, v.18 n.4, p.347-355, April 1992 [doi>10.1109/32.129222]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

General Terms:
Algorithms, Design, Performance