'해시 조인'에 해당되는 글 1건

  1. 2013.11.29 [SQL Server 운영과 튜닝] - Hash Join
IT-Study2013.11.29 09:55

 

3.3 해시 조인

  • 해시 조인은 인덱스를 사용할 없는 환경에서 결과를 정렬할 필요가 없을 효율적으로 사용할 있는 조인이다.
  • 해시 조인은 해시 키와 해시 테이블을 통해서 조인을 한다.
  • 해시 조인은 해시 테이블에서 같은 해시 키를 찾는 조인이다.
  • 빌드 입력: 해시 테이블을 만드는데 사용되는 입력
  • 프로브 입력: 해시 테이블을 탐색하는 입력
  • 해시 조인은 메모리가 부족할 경우 디스크에 발생한는 I/O 효율적으로 관리하기 위해서 메모리 상태에 따라 서로 다른 알고리즘을 사용한다.
  • 슈도 코드

 

 

 

 

1. -메모리-해시 조인(해시 테이블을 메모리에 유지할 있는 경우)

작은 테이블을 빌드 입력, 테이블을 프로브 입력으로 선택함

빌드 테이블의 조인 조건에 해시 함수를 적용하여 해시 키를 만든 , 해시 키와 결과에 출력될 컬럼들도 같이 저장함

프로브 입력의 조인 조건에 해시함수를 적용하여 해시키를 만든 , 해시 테이블을 검색한다. 검색이 같으면 결과 집합으로 선택하고, 틀리면 조인 실패로 판단

프로브 입력에 데이터가 없을 때까지 ~③을 반복한다.

 

2. 유예 해시 조인(메모리가 부족해서 디스크가 필요한 경우)

작은 테이블을 빌드 입력, 테이블을 프로브 입력으로 선택함

해시 테이블 생성 까지는 -메모리 해시 조인의 방식과 같으나, 유예 해시 조인은 메모리에 해시테이블을 저장할 없으므로, 해시키 기반으로 임시 파일로 저장함

프로브 입력 역시 해시 키를 기반으로 여러 임시 파일중 개를 선택해서 해시키와 SELECT 기술된 컬럼들을 같이 저장한다.

빌드 입력 테이블과 프로브 입력 테이블은 같은 해시 키를 기반으로 임시 파일을 저장되기 때문에 해시 키를 기반으로 저장된 임시 파일을 찾을 있다.

빌드 입력과 프로브 입력이 모두 임시 파일에 저장되면 같은 해시 키를 가진 파일들을 같이 메모리에 올린다.

임시 파일을 메모리에 올려 -메모리 해시 조인으로 진행한다.

파일을 메모리로 올릴 작은 쪽을 빌드 입력으로 선택하는데, 기존의 프로브 입력이 빌드 입력이 되는 역할 반전이 일어날 있다.

모든 임시 파일에 대해서 조인이 완료 까지 ⑥번을 반복한다.

 

빌드 입력 크기와 STOP&GO

  • -메모리 동작시: 메모리에 해시 테이블을 만드는 시간
  • 유예 해시 조인: 빌드 입력과 프로브 입력을 임시 파일에 파티셔닝을 후에 다시 메모리에 올리는 만큼
  • 작은 입력을 빌드 입력으로 선택하는 것은 메모리뿐만 아니라 반응성에도 이점으로 작용할 있음

 

메모리 부족으로 인한 성능 저하

  • 메모리가 부족하면 부족한 부분을 디스크에 저장하기 위해서 추가 작업이 발생한다.

 

해시 재귀(Hash Recursion) 해시 재귀 초과

  • 해시 재귀: 유예 해시 조인에서 테이블을 해시키를 기반으로 분할하는데, 분할을 후에도 메모리에 모두 저장할 없을 해당 범위를 다시 분할 하는
  • 이유: 1. 실제 메모리 부족 2. 잘못된 실행 계획 3. 잘못된 통계 정보 사용
  • 재귀 초과: 일정 횟수 이상 반복 경우
  • 확인 방법: Hash Warning, #10887958 테이블 생성

 

-메모리 해시 조인에서 유예 해시 조인으로 진행

  • 대용량 테이블의 경우 실제 데이터를 정확히 수가 없기 때문에 처음에는 -메모리 해시 조인으로 실행해서 점차 유예 해시 조인으로 전환하는 방법 사용

 

통계와 빌드 입력 선택

  • 테이블의 통계 정보를 사용해서 작은 쪽을 빌드 입력으로 선택
  • 만약 통계가 잘못되어 있다면, 빌드 입력과 프로브 입력이 바뀔수 있음

 

해시 충돌과 성능 이슈

  • 해시 테이블을 만드는 과정에서 같은 해시 키를 가지는 행이 존재하면, 하나의 버킷에 들어갈 없어서 이를 리스트로 관리한다.
  • 같은 해시 키를 가지는 이유

1. 실제로 같은 값을 가지는 경우: M쪽이 해시 테이블로 선택이되면 중복된 해시 키를 가질 있다.

2. 해시 충돌이 발생한 경우: 해시 함수마다 일정확률로 같은 해시 키가 만들어 진다.

  • 리스트가 길어지면 선형 검색 시간이 필요하기 때문에 성능저하가 발생한다.

 

조인 제약 조건과 해시 충돌

  • 해시 조인은 <, >같은 범위 조건을 조인 조건으로 사용할 없다. 이유는 해시 키가 계산된 값이기 때문에 해시 함수를 적용하기 후의 순서가 같다는 보장을 수가 없다.
  • 만약 조인 조건에 '=' 조건과 <, > 조건이 같이 주어진다면 '=' 이외의 조건은 필터 조건으로 사용됨
  • 나머지 검색에 조인 조건이 포함된 이유: 해시 함수를 적용하기 전의 값도 비교를 해야 해시 충돌로 인하여 포함된 다른 해시키 값을 필터 있기 때문

 

Left Deep & Right Deep & Bushy 해시 트리에  따른 메모리 사용량

Left Deep

 

 

  • 마지막에 조인된 결과만 메모리에 해시 테이블로 만들면 된다. 그래서 현재 해시 테이블을 만드는 만큼의 메모리만 있으면 되기 때문에 적은 메모리로 조인할 있다.

 

RIGHT Deep

 

 

  • 프로브 입력의 조인이 모두 끝날때 까지 모든 해시 테이블을 메모리에 유지해야 하는 부담이 생긴다.

 

Bushy

 

  • 독립적으로 조인한 결과의 크기가 작아 -메모리 해시 조인을 있는 경우 효과적인 조인이다.

 

정리

  • 정렬이나 인덱스 탐색 부하가 없어 대용량 데이터 조인에도 효과적이다.
  • 항상 해시 테이블을 메모리에 만들어야 하기 때문에 충분한 메모리가 필요하고 머지 조인처럼 대기(STOP&GO) 피할 방법도 없다.
  • OLTP보단 OLAP같은 분석을 위한 환경에서 사용되기 때문에 쿼리가 충분한 자원을 사용할 있게 SQL Server 구성해 주면 위와 같은 이슈는 최소화 있을 것이다.

 

 

 

신고
Posted by TM ~ing