Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Multiple Pipelined Hash Joins using Synchronization of Page Execution Time

페이지 실행시간 동기화를 이용한 다중 파이프라인 해쉬 결합

  • 이규옥 (한국기계연구원) ;
  • 원영선 (아주대학교 정보및컴퓨터공학부) ;
  • 홍만표 (아주대학교 정보및컴퓨터공학부)
  • Published : 2000.07.15
Download PDF
⟨ Previous Next ⟩

Abstract

In the relational database systems, the join operation is one of the most time-consuming query operations. Many parallel join algorithms have been developed to reduce the execution time. Multiple hash join algorithm using allocation tree is one of most efficient ones. However, it may have some delay on the processing each node of allocation tree, which is occurred in tuple-probing phase by the difference between one page reading time of outer relation and the processing time of already read one. In this paper, to solve the performance degrading problem by the delay, we develop a join algorithm using the concept of 'synchronization of page execution time' for multiple hash joins. We reduce the processing time of each nodes in the allocation tree and improve the total system performance. In addition, we analyze the performance by building the analytical cost model and verify the validity of it by various performance comparison with previous method.

관계형 데이타베이스 시스템에서 결합 연산자는 데이타베이스 질의를 구성하는 연산자들 중 가장 많은 처리시간을 요구한다. 따라서 이러한 결합 연산자를 효율적으로 처리하기 위해 많은 병렬 알고리즘들이 소개되었다. 그 중 다중 해쉬 결합 질의의 처리를 위해 할당 트리를 이용한 방법이 가장 우수한 것으로 알려져 왔다. 그러나 이 방법은 할당 트리의 각 노드에서 필연적인 지연이 발생되는 데 이는 튜플-시험 단계에서 외부 릴레이션을 디스크로부터 페이지 단위로 읽는 비용과 이미 읽는 페이지에 대한 해쉬 결합 비용간의 차이에 의해 발생하게 된다. 본 논문에서는 이 비용 차이로 인해 발생되는 전체 시스템의 성능 저하를 방지하기 위해 페이지 실행시간 동기화 기법을 제안하였고 이 기법을 통해 각 노드에서의 처리시간을 줄이고 나아가 전체 시스템의 성능을 향상시켰다. 또한 분석적 비용 모형을 세우고 기존 방식과의 다양한 성능 분석을 통해 비용 모형의 타당성을 입증하였다.

Keywords

References

  1. Hui-I Hsiao, Ming-Syan Chen, 'Parallel Execution of Hash Joins in Parallel Databases,' IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 8, pp.872-883, Aug. 1997 https://doi.org/10.1109/71.605772
  2. Hui-I Hsiao, Ming-Syan Chen, and Philip S. Yu, 'On Parallel Execution of Multiple Pipelined Hash Jois,' Proc. ACM SIGMOD, pp.185-196, May 1994 https://doi.org/10.1145/191839.191879
  3. Ming-Syan Chen, Ming-Ling Lo, Philip S. Yu, and Honesty C. Young, 'Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins,' 18th International Conference on VLDB, pp.15-26, August 1992
  4. Ming-Syan Chen, P.S. Yu, and K.L. Wu, 'Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries,' Proc. 8th International Conf. Data Engineering, pp.58-67,Feb. 1992 https://doi.org/10.1109/ICDE.1992.213205
  5. Ming-Syan Chen, Mingling Lo, Philip S. Yu, and Honesty C. Young, 'Applying Segmented Right-Deep Trees to Pipelining Hash Joins,' IEEE Trans. on Knowledge and Data Engineering, Vol. 7, No. 4, August 1995 https://doi.org/10.1109/69.404036
  6. Donovan A. Schneider and D.J. DeWitt, 'Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines,' Proceedings of the 16th VLDB Conference,pp.469-480, August 1990
  7. Mingling Lo, Ming-Syan Chen, C. V. Ravishankar, and Philip S. Yu, 'On Optimal Processor Allocation to Support Pipelined Hash Joins,' Proc. ACM SIGMOD, pp.69-78, May 1993 https://doi.org/10.1145/170035.170053
  8. D.J.DeWitt, and J. Gray, 'Parallel Database System: The Future of High PerformanceDatabase System,' Comm. of ACM, pp.85-98, June 1992 https://doi.org/10.1145/129888.129894