On parallel execution of multiple pipelined hash joins

ABSTRACT

In this paper we study parallel execution of multiple pipelined hash joins. Specifically, we deal with two issues, processor allocation and the use of hash filters, to improve parallel execution of hash joins. We first present a scheme to transform a bushy execution tree to an allocation tree, where each node denotes a pipeline. Then, processors are allocated to the nodes in the allocation tree based on the concept of synchronous execution time such that inner relations (i.e., hash tables) in a pipeline can be made available approximately the same time. In addition, the approach of hash filtering is investigated to further improve the overall performance. Performance studies are conducted via simulation to demonstrate the importance of processor allocation and to evaluate various schemes using hash filters. Simulation results indicate that processor allocation based on the allocation tree significantly outperforms that based on the original bushy tree, and that the effect of hash filtering becomes prominent as the number of relations in a query increases.

REFERENCES

• 1: Dina Bitton , Jim Gray, Disk Shadowing, Proceedings of the 14th International Conference on Very Large Data Bases, p.331-338, August 29-September 01, 1988
• 2: 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]
• 3: Ming-Syan Chen , Hui-I Hsiao , Philip S. Yu, Applying Hash Filters to Improving the Execution of Bushy Trees, Proceedings of the 19th International Conference on Very Large Data Bases, p.505-516, August 24-27, 1993
• 4: 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
• 5: 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
• 6: D. J. DeWitt and R. Gerber. Multiprocessor Hash-Based Join Algorithms. Proceedings of the 11#h International Conference on Very Large Data Bases, pages 151-162, August 1985.
• 7: 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]
• 8: 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]
• 9: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• 10: Danièle Grady , Claude Puech, On the effect of join operations on relation sizes, ACM Transactions on Database Systems (TODS), v.14 n.4, p.574-603, Dec. 1989 [doi>10.1145/76902.76907]
• 11: 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
• 12: Hui-I Hsiao , David J. DeWitt, A performance study of three high availability data replication strategies, Proceedings of the first international conference on Parallel and distributed information systems, p.18-29, December 1991, Miami, Florida, United States
• 13: 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
• 14: Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
• 15: Ming-Ling Lo , Ming-Syan Syan Chen , C. V. Ravishankar , Philip S. Yu, On optimal processor allocation to support pipelined hash joins, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.69-78, May 25-28, 1993, Washington, D.C., United States
• 16: 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
• 17: 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
• 18: 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]
• 19: D. Schneider. Complex Query Processing in Multiprocessor Database Machines. Technical Report Tech. Rep. 965, Computer Science Department# University of Wisconsin-Madison, September 1990.
• 20: 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
• 21: 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
• 22: 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]
• 23: 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
• 24: 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
• 25: A. Swami, Optimization of large join queries: combining heuristics and combinatorial techniques, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.367-376, June 1989, Portland, Oregon, United States
• 26: 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
• 27: Joel L. Wolf , John Turek , Ming-Syan Chen , Philip S. Yu, Scheduling multiple queries on a parallel machine, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.45-55, May 16-20, 1994, Nashville, Tennessee, United States
• 28: 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: Query processing

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

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

General Terms:
Algorithms, Performance