본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

부하 균형 유지를 고려한 파이프라인 해시 조인 방법
A Pipelined Hash Join Method for Load Balancing

문진규   (국방과학연구소CC0136088  ); 박노상   (한국기계연구원 전산실CC0007559  ); 김평중   (도립충북과학대학 컴퓨터정보과학과  ); 진성일   (충남대학교 정보통신공학부UU0001302  );
  • 초록

    다중 조인 연산의 파이프라인 방식 처리에서 조인 어트리뷰트의 자료 불균형(data skew)이 성능에 주는 영향을 연구하고, 자료 불균형을 대비하여 적재부하를 라운드-로빈 방식으로 정적 분할하는 방법과 자료분포도를 이용하여 적응적으로 분할하는 두 가지 파이프라인 해시 조인 알고리즘을 제안한다. 해시 기반 조인을 사용하면 여러 개의 조인을 파이프라인 방식으로 처리할 수 있다. 다중 조인의 파이프라인 방식 처리는 조인 중간 결과를 디스크를 통하지 않고 다른 프로세서에게 직접 전달하므로 효율적이다. 파이프라인 해시 조인 알고리즘이 자료 불균형을 대비한 부하 균형 유지 메커니즘을 갖고 있지 않다면 자료 불균형은 성능에 매우 심각한 영향을 줄 수 있다. 본 논문은 자료 불균형의 영향과 제안된 두 가지 기법을 비교하기 위하여 파이프라인 세그먼트의 실행 모형, 비용 모형, 그리고 시뮬레이터를 개발한다. 다양한 파라미터로 모의 실험을 한 결과에 의하면 자료 불균형은 조인 선택도와 릴레이션 크기에 비례하여 시스템 성능을 떨어뜨림을 보여준다. 그러나 제안된 파이프 라인 해시 조인 알고리즘은 다수의 버켓 사용과 분할의 조율을 통해 자료 불균형도가 심한 경우에도 좋은 성능을 갖게 한다.


    We investigate the effect of the data skew of join attributes on the performance of a pipelined multi-way hash join method, and propose two new hash join methods with load balancing capabilities. The first proposed method allocates buckets statically by round-robin fashion, and the second one allocates buckets adaptively via a frequency distribution. Using hash-based joins, multiple joins can be pipelined so that the early results from a join, before the whole join is completed, are sent to the next join processing without staying on disks. Unless the pipelining execution of multiple hash joins includes some load balancing mechanisms, the skew effect can severely deteriorate system performance. In this paper, we derive an execution model of the pipeline segment and a cost model, and develop a simulator for the study. As shown by our simulation with a wide range of parameters, join selectivities and sizes of relations deteriorate the system performance as the degree of data skew is larger. But the proposed method using a large number of buckets and a tuning technique can offer substantial robustness against a wide range of skew conditions.


  • 주제어

    병렬 데이터베이스 .   파이프라인 해시 조인 .   자료 불균형 .   부하 균형 유지.  

  • 참고문헌 (16)

    1. M. S. Lakshmi and P. S. Yu, 'Effectiveness of Parallel Joins,' IEEE Trans. Knowledge and Data Engineering, Vol. 2, No.4, pp.410-424, December, 1990 
    2. D. J. DeWitt, J. F. Naughton, D. A. Schneider, and S. Seshadri, 'Practical Skew Handling in Parallel-joins,' Proc. Int'l Conf. VLDB, pp.27-40, August, 1992 
    3. K. A. Hua, C. Lee, and C. M. Hua, 'Dynamic Load Balancing in Multicomputer Database Systems Using Partition Tuning,' IEEE Trans. Knowledge and Data Engineering, Vol.7, No.6, pp.968-983, December, 1995 
    4. M-S. Chen, H-I. Hsiao, and P. S. Yu, 'Applying Hash Filters to Improving the Execution of Bushy Trees,' Proc. 14th Int'l Conf. VLDB, pp.505-516, August, 1993 
    5. M-S. Chen, M. La, P. S. Yu, and H. C. Young, 'Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins,' IEEE Trans. Knowledge and Data Engineering, Vol. 7, No.4, pp.656-668, August, 1995 
    6. H-I. Hsiao and M-S. Chen, 'Parallel Execution of Hash Joins in Parallel Databases,' IEEE Trans. Parallel and Distributed Systems, Vol.8, No.8, pp.872-883, August, 1997 
    7. M-S. Chen and P. S. Yu, 'Interleaving a Join Sequence with Semijoins in Distributed Query Processing,' IEEE Trans. Parallel and Distributed Systems, Vol.3, No.5, pp. 611-621, September, 1992 
    8. D. Schneider and D. J. DeWitt, 'Tradeoffs in Processing Complex Join Queries via Hashing in Multicomputer Database Machines,' Proc. 16th Int'l Conf. VLDB, pp.469-480, August, 1990 
    9. N. Roussopoulos and H. Kang, 'A Pipeline n-way Join Algorithm based on the 2-way Semijoin Program,' IEEE Trans. Knowledge and Data Engineering, Vol.3, No.4, pp. 461-473, December, 1991 
    10. A. Wilschut and P. Apers, 'Dataflow query execution in parallel main memory environment,' Proc. First Conf. Parallel and Distributed Information Systems, pp.68-77, December, 1991 
    11. E. Rahm, 'Parallel Query Processing in Shared Disk Database Systems,' Proc. Of Intl. Conf. On Management of Data, ACM SIGMOD, pp.32-37, 1993 
    12. P. Scheuermann, G. Weikum, and P. Zabback, 'Data partitioning and load balancing in parallel disk systems,' VLDB Journal, pp.48-66, 1998 
    13. D. A. Schneider and D. J. DeWitt, 'A Performance Evaluation of Four Parallel Join Algorithms in a Shared-nothing Multiprocessor Environment,' Proc. SIGMOD Conf., pp. 110-121, May, 1989 
    14. P. Mishra and M. H. Eich, 'Join Processing in Relational Databases,' ACM Computing Surveys, Vol.24, No.1, pp.63-113, March, 1992 
    15. G. Graefe, 'Query Evaluation Techniques for Large Databases,' ACM Computing Surveys, Vol.25, No.2, pp.73-170, June, 1993 
    16. D. J. DeWitt and J. Gray, 'Parallel Database Systems: The Future of High Performance Database Systems,' Comm. ACM, Vol.35, No.6, pp.85-98, June, 1992 

 저자의 다른 논문

  • 문진규 (1)

    1. 2002 "다중 해시 조인의 파이프라인 처리에서 분할 조율을 통한 부하 균형 유지 방법" 정보과학회논문지. Journal of KIISE. 데이타베이스 29 (3): 180~192    
  • 박노상 (0)

  • 진성일 (27)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기