SQL Server 의 세 가지 물리 적 연결 작업(성능 비교)

SQL Server 에서 흔히 볼 수 있 는 표 와 표 사이 의 Inner Join,Outer Join 은 엔진 이 선택 한 열,데이터 에 색인 이 있 는 지,선택 한 데이터 의 선택성 은 Loop Join,Merge Join,Hash Join 등 세 가지 물리 적 연결 중 하나 로 전 환 됩 니 다.이 세 가지 물리 적 연결 을 이해 하 는 것 은 표 연결 시 성능 문 제 를 해결 하 는 기초 이다.다음은 내 가 이 세 가지 연결 의 원 리 를 장면 에 적용 하여 설명 하 겠 다.끼 워 넣 기 순환 연결(Nested Loop Join)순환 끼 워 넣 기 연결 은 가장 기본 적 인 연결 입 니 다.이름 에서 보 듯 이 순환 끼 워 넣 기 가 필요 합 니 다.끼 워 넣 기 순환 은 세 가지 방식 중 유일 하 게 부등식 연결 을 지원 하 는 방식 입 니 다.이러한 연결 방식 의 과정 은 다음 그림 으로 간단하게 보 여 줍 니 다.그림 1.순환 끼 워 넣 기 연결 의 첫 번 째 단계 입 니 다.     
     그림 2.순환 끼 워 넣 기 연결 의 두 번 째 단 계 는 위의 두 그림 에서 알 수 있 습 니 다.순환 끼 워 넣 기 연결 은 내부 순환 표를 찾 는 횟수 가 외부 순환 의 줄 수 와 같 습 니 다.외부 순환 이 더 많은 줄 이 없 을 때 순환 끼 워 넣 기 가 끝 납 니 다.또한 이러한 연결 방식 은 내부 순환 의 표 질서(즉 색인 이 있 음)가 필요 하고 외부 순환 표 의 줄 수 는 내부 순환 의 줄 수 보다 작 아야 한 다 는 것 을 알 수 있다.그렇지 않 으 면 조회 분석 기 는 Hash Join(본문 뒤에 설명 할 것)을 선 호한 다.
    포 함 된 순환 연결 을 통 해 알 수 있 듯 이 데이터 양 이 증가 함 에 따라 성능 에 대한 소 모 는 지수 급 의 증 가 를 나타 내기 때문에 데이터 양 이 어느 정도 되면 조회 분석 기 는 이런 방식 을 사용한다.
    다음은 예 를 들 어 마이크로소프트 AdventureWorks 데이터 베 이 스 를 이용 하여 순환 플러그 인 연결 을 살 펴 보 겠 습 니 다.
   
    그림 3.간단 한 끼 워 넣 기 순환 연결   
    그림 3 에서 ProductID 는 색인 이 있 고 순환 하 는 외부 표(Product 표)에서 ProductID=870 에 부합 되 는 줄 은 4688 개 이 므 로 해당 하 는 SalesOrder Detail 표 는 4688 회 를 찾 아야 한다.그림 4 참조.
   
    그림 4.추가 열 에서 가 져 온 추가 책 갈피 찾기
  
    그림 4 에서 보 듯 이 UnitPrice 열 을 하나 더 선택 하여 연 결 된 색인 이 원 하 는 검색 어 를 덮어 쓸 수 없 게 되 었 습 니 다.책 갈 피 를 통 해 찾 아야 합 니 다.이것 은 바로 우리 가 Select 에 필요 한 열 만 선택 하 는 좋 은 습관 을 기 르 는 이유 입 니 다.위의 문 제 를 해결 하기 위해 서 는 색인 을 덮어 쓸 수도 있 고 필요 한 열 을 줄 여 책 갈 피 를 피 할 수도 있 습 니 다.또한 위 에서 ProductID 에 부합 되 는 줄 은 5 개 에 불과 하기 때문에 조회 분석 기 는 책 갈 피 를 선택 하여 찾 습 니 다.만약 에 우리 가 조건 에 부합 되 는 줄 을 확대 하면 조회 분석 기 는 표 스 캔(일반적으로 표 중 줄 수의 1%이상 에 이 르 면 책 갈피 가 아 닌 table scan 을 하 는 경향 이 있 습 니 다.그러나 이것 은 절대적 이지 않 습 니 다)그림 5 참조.
   
    그림 5.조회 분석 기 가 표 스 캔 을 선택 했다.
 
    이 를 통 해 알 수 있 듯 이 조회 분석 기 는 이때 표 스 캔 을 선택 하여 연결 하 는데 이런 방식 은 효율 이 매우 낮 기 때문에 좋 은 커버 색인 과 Select*는 모두 주의해 야 할 부분 이다.또한 위의 상황 은 표 스 캔 과 관련 되 더 라 도 비교적 이상 적 인 상황 이다.더 나 쁜 상황 은 여러 개의 부등식 을 연결 할 때 조회 분석 기 는 각 열의 통계 분 포 를 알 지만 몇 가지 조건 의 결합 분 포 를 모 르 기 때문에 잘못된 집행 계획 이 발생 한다.그림 6 참조.
   
    그림 6.연합 분 포 를 예측 할 수 없 기 때문에 발생 하 는 편차
   그림 6 에서 알 수 있 듯 이 예상 되 는 줄 수 와 실제 줄 수 에 큰 차이 가 존재 하기 때문에 표 스 캔 을 사용 해 야 하지만 조회 분석 기 는 책 갈 피 를 선택 하여 찾 았 다.이런 상황 이 표 스 캔 보다 성능 에 미 치 는 영향 이 더욱 클 것 이다.구체 적 으로 어느 정도 클 까요?우 리 는 강제 표 스 캔 과 분석 기의 기본 계획 을 비교 할 수 있다.그림 7 참조.
   
    그림 7.강제 표 스캐닝 성능 이 오히려 좋다.
 연결 병합(Merge Join)
    합병 연결 에 대해 말하자면,나 는 갑자기 시애틀 에서 SQL Pass 정상 회의 에 참가 하 는 저녁 에 술집 에서 줄 을 서서 술 을 주문 하 는 것 이 생각 났 다.나 는 다른 친구 와 잘못 서 있 었 기 때문에,마치 우리 둘 이 새치기 하 는 것 같 았 다.나 는 서둘러"I'm sorry,i thought here is end of line"이 라 고 말 했다.상대방 은"It's OK,In SQL Server,We called it merge join"이 라 고 유머 러 스 하 게 말 했다.
    위의 작은 이 야 기 를 통 해 알 수 있 듯 이 Merge Join 은 사실 두 개의 질서 있 는 대기 열 을 연결 하 는 것 입 니 다.양 끝 이 모두 질서 가 있어 야 하기 때문에 Loop Join 처럼 순환 내부 의 표를 계속 찾 을 필요 가 없습니다.그 다음으로 Merge Join 은 표 연결 조건 중 적어도 하나의 등호 조회 분석 기 가 있어 야 Merge Join 을 선택 할 수 있 습 니 다.
    Merge Join 의 과정 은 아래 그림 으로 간단하게 설명 할 수 있 습 니 다.
   
    그림 8.Merge Join 첫걸음
 
    Merge Join 은 우선 두 입력 집합 에서 각각 첫 줄 을 가 져 오고,일치 하면 일치 하 는 줄 로 되 돌려 줍 니 다.두 줄 이 일치 하지 않 으 면 작은 값 의 입력 집합+1 이 있 습 니 다.그림 9 참조.
   
    그림 9.더 작은 입력 집합 아래로 1
    C\#코드 로 Merge Join 을 표시 하면 코드 1 과 같 습 니 다.

 
public class MergeJoin 
{ 
// Assume that left and right are already sorted 
public static Relation Sort(Relation left, Relation right) 
{ 
Relation output = new Relation(); 
while (!left.IsPastEnd() && !right.IsPastEnd()) 
{ 
if (left.Key == right.Key) 
{ 
output.Add(left.Key); 
left.Advance(); 
right.Advance(); 
} 
else if (left.Key < right.Key) 
left.Advance(); 
else //(left.Key > right.Key) 
right.Advance(); 
} 
return output; 
} 
} 

코드 1.Merge Join 의 C\#코드 표시
    따라서 일반적으로 Merge Join 은 양 끝 을 질서 있 게 입력 하면 Merge Join 의 효율 이 매우 높 지만,Merge Join 을 질서 있 게 구현 하기 위해 명시 적 Sort 를 사용 해 야 한다 면 Hash Join 은 효율 적 인 선택 이 될 것 입 니 다.그러나 예외 도 있다.그것 이 바로 조회 에 order by,group by,distinct 등 이 존재 하기 때문에 조회 분석 기 가 명시 적 순 서 를 해 야 할 수도 있다 는 것 이다.그러면 조회 분석 기 에 있어 서 어차피 명시 적 Sort 가 진행 되 었 는데 왜 일석이조 가 Sort 후의 결 과 를 직접 이용 하여 원가 가 더 적은 MERGE JOIN 을 하지 않 겠 는가?이런 상황 에서 Merge Join 은 더 좋 은 선택 이 될 것 이다.
    또한 Merge Join 의 원 리 를 통 해 알 수 있 듯 이 연결 조건 이 부등식 일 때(단,포함 되 지 않 습 니 다!=)예 를 들 어><>=등 방식 일 때 Merge Join 은 더욱 효율 적 입 니 다.
    다음은 간단 한 Merge Join 을 살 펴 보 겠 습 니 다.이 Merge Join 은 집합 색인 과 비 집합 색인 으로 Merge Join 의 양 끝 을 질서 있 게 합 니 다.그림 10 참조.
   
    그림 10.집합 색인 과 비 집합 색인 으로 입력 양 끝 이 질서 있 음 을 보증 합 니 다.
 
    물론 Order By,Group By 를 조회 할 때 분석 기 는 명시 적 Sort 를 사용 해 야 하기 때문에 일거양득 일 때 Hash Join 이 아 닌 Merge Join 을 선택 합 니 다.그림 11 참조.
   
    그림 11.일석이조 의 Merge Join 해시 매 칭(Hash Join)
    해시 매 칭 연결 은 앞의 두 가지 방식 에 비해 더욱 복잡 하지만 해시 매 칭 은 대량의 데이터 와 일치 하고 무질서 한 상황 에서 성능 이 Merge Join 과 Loop Join 보다 좋 습 니 다.연결 열 이 정렬 되 지 않 은 경우(즉 색인 이 없 는 경우)검색 분석 기 는 Hash Join 을 사용 하 는 경향 이 있 습 니 다.
    해시 매 칭 은 생 성과 탐측 단계 로 나 뉘 는데 먼저 생 성 단계 이 고 1 단계 생 성 단계 의 구체 적 인 과정 은 그림 12 와 같다.
   
    그림 12.해시 가 일치 하 는 1 단계
    그림 12 에서 입력 소스 의 모든 항목 을 해시 함수 의 계산 을 거 쳐 서로 다른 Hash Bucket 에 넣 었 다.그 중에서 Hash Function 의 선택 과 Hash Bucket 의 수량 은 모두 블랙 박스 이 고 마이크로소프트 는 구체 적 인 알고리즘 을 발표 하지 않 았 으 나 나 나 는 이미 매우 좋 은 알고리즘 이 라 고 믿는다.그리고 Hash Bucket 안에 있 는 항목 은 무질서 합 니 다.일반적으로 검색 유 틸 리 티 는 양 끝 에 비교적 작은 입력 집합 을 연결 하여 첫 번 째 단계 의 입력 원 으로 사용 합 니 다.
    다음은 탐지 단계 입 니 다.다른 입력 집합 에 대해 서도 각 줄 에 대해 해시 함 수 를 진행 하여 해당 하 는 Hash Bucket 을 확인 하고 이 줄 에 대응 하 는 Hash Bucket 의 모든 줄 과 일치 하 며 일치 하면 해당 하 는 줄 로 돌아 갑 니 다.
    해시 매 칭 의 원 리 를 알 아 보 는 것 은 어렵 지 않 습 니 다.해시 매 칭 은 해시 함수 와 관련 되 기 때문에 CPU 에 대한 소모 가 매우 높 습 니 다.또한 해시 Bucket 의 줄 은 무질서 하기 때문에 출력 결과 도 무질서 합 니 다.그림 13 은 전형 적 인 해시 매 칭 이다.그 중에서 조회 분석 기 는 표 데이터 양 이 비교적 적은 제품 표를 사용 하여 생 성 했 고 데이터 양 이 많은 SalesOrder Detail 표를 사용 하여 탐지 했다.
   
    그림 13.전형 적 인 해시 매 칭 연결 상의 경우 메모리 가 생 성 단계 에 필요 한 메모 리 를 수용 할 수 있 습 니 다.메모리 가 부족 하면 Grace 해시 매 칭 과 재 귀 해시 매 칭 과 관련 될 수 있 습 니 다.그러면 TempDB 를 사용 하여 대량의 IO 를 먹 을 수 있 습 니 다.여기 서 자세히 말 하지 않 겠 습 니 다.관심 있 는 학생 은 걸음 을 옮 길 수 있 습 니 다.http://msdn.microsoft.com/zh-cn/library/aa178403(v=SQL.80).aspx다음 에 우 리 는 하나의 표를 통 해 이 몇 가지 연결 방식 의 소모 와 사용 장면 을 간단하게 요약 한다.
소켓 순환 연결
병합 연결
해시 연결
적용 필드
외부 순환 이 적 고 메모리 순환 조건 열 이 질서 가 있 습 니 다.
입력 양 끝 모두 질서 정연
데이터 양 이 많 고 색인 이 없습니다.
CPU
낮다
낮 음(명시 적 정렬 이 없 으 면)
높다
메모리
낮다
낮 음(명시 적 정렬 이 없 으 면)
높다
IO
이 가능 하 다,~할 수 있다,...
낮다
SQL Server 라 는 몇 가지 물리 적 연결 방식 이 성능 개선 에 있어 적지 않 을 수 있 습 니 다.선별 조건 이 많 을 때 분석 기 를 조회 하 는 것 이 그렇게 스마트 하지 않 을 수 있 기 때문에 이 몇 가지 연결 방식 을 이해 하 는 것 이 포 지 셔 닝 문제 에 특히 중요 합 니 다.또 업무 차원 에서 조회 범 위 를 줄 여 저 성능 연결 가능성 을 줄 일 수 있다.참고 문헌:http://msdn.microsoft.com/zh-cn/library/aa178403(v=SQL.80).aspxhttp://www.dbsophic.com/SQL-Server-Articles/physical-join-operators-merge-operator.html글 은 다음 과 같다.http://www.cnblogs.com/CareySon/