반응형
| INF: 조인 기술의 비교 | E-study | 2005/01/05 10:24 | |||||||||
| http://blog.naver.com/gravitycage/140009166561 | ||||||||||
요약Microsoft SQL Server 7.0 버전에서는 기존에 있던 중첩 루프 조인(Nested Loop Join)을 보완하기 위해서 해시 조인과 정렬 병합 조인(Sort-Merge Join)과 같은 몇 가지 조인 기술이 새로 추가되었습니다. 본 문서에서는 이러한 새로운 조인 기술을 설명하고 그 기술들을 비교합니다.
http://support.microsoft.com/default.aspx?scid=kb;ko;kr197297 INF: 조인 기술의 비교
이 문서는 이전에 다음 ID로 출판되었음: KR197297 요약Microsoft SQL Server 7.0 버전에서는 기존에 있던 중첩 루프 조인(Nested Loop Join)을 보완하기 위해서 해시 조인과 정렬 병합 조인(Sort-Merge Join)과 같은 몇 가지 조인 기술이 새로 추가되었습니다. 본 문서에서는 이러한 새로운 조인 기술을 설명하고 그 기술들을 비교합니다. 추가 정보Microsoft SQL Server 6.5 이전 버전에서는 레코드들을 조인하는 기술로 중첩 루프 조인(Nested Loop Join) 하나만 있었습니다. 하지만 SQL Server 7.0에서는 해시 및 정렬 기반의 알고리즘을 구현합니다. 쿼리 엔진이 해시나 정렬 중에서 어떤 기술을 사용할 지에 대한 결정은 입력의 상대적인 크기, 정렬 여부 또는 해시 테이블이 메모리에 완전하게 적합한지 등에 따릅니다. 최적화 프로그램(Optimizer)은 쿼리를 실행하기 위해 항상 최적의 조인 계획을 선택하게 되는데 여기에는 세 가지 옵션이 있습니다. 해시 조인과 병합(Merge) 조인은 거의 비슷하지만 상황에 맞게 더 유리한 조인을 사용할 수 있습니다. 하지만 이 두 조인과 중첩 루프 조인(Nested Loop Join) 사이에는 다음에 나오는 것처럼 상당한 차이가 있습니다. 본 문서에 나오는 예는 모두 설명을 목적으로 제공됩니다. 그리고 본 문서의 마지막에 나오는 표는 사용할 조인 유형에 영향을 줄 수 있는 몇 가지 결정을 실례로 표시한 것입니다. 일반적으로 사용자는 최적화 프로그램(Optimizer)을 무시하면서까지 조인 유형을 고집하지 않는 것이 좋습니다. 중첩 루프 조인(Nested Loop Join)중첩 루프 조인(Nested Loop Join)에서는 우선 테이블 중 하나를 스캔합니다. 이 때 그 테이블의 모든 행에 대하여 두 번째 테이블을 조회하여 일치되는 행을 검색합니다. 이 경우에 두 테이블을 외부(Outer) 입력 및 내부(Inner) 입력이라고 부릅니다. 외부(Outer) 입력의 각 값마다 내부(Inner) 입력을 스캔하여 일치하는 것을 찾는 것이 바로 기본 알고리즘입니다. 내부(Inner) 입력에 인덱스가 있으면 조회를 훨씬 효과적으로 실행할 수 있습니다. 인덱스가 있는 중첩 루프 조인(Nested Loop Join)은 분명히 인덱스가 없는 중첩 루프 조인(Nested Loop Join)보다 더 효과적입니다. 또한 테이블이 일대일 관계에 있는 경우 내부(Inner) 테이블을 스캔하다가 외부(Outer) 테이블의 행과 일치하는 행을 찾으면 스캔 작업을 종료합니다.부동 조건의 조인을 포함하는 이러한 방법을 사용하여 모든 쿼리를 처리할 수 있습니다. 중첩 루프 예: Reserves는 529 페이지와 100000개의 행으로 되어 있습니다. Sailors는 모두 195 페이지와 40000개의 행으로 되어 있습니다. 'sailors' 테이블. 스캔 횟수 100000, 논리적 읽기 207596, 물리적 읽기 3, 미리 읽기 0. 'reserves' 테이블. 스캔 횟수 1, 논리적 읽기 529, 물리적 읽기 0, 미리 읽기 0. |--Nested Loops(Inner Join) 해시 조인(Hash Join)해시 일치에서는 반복적인 임의 추출 함수를 사용하여 입력 중의 하나에 대해 Build Input 메모리에 해시 테이블을 작성합니다. 그리고 이 테이블에 다른 입력(Probe Input)과 일치되는 값이 있는지 검색합니다. 해시 테이블은 인덱스와 같은 기능을 합니다. Build Input의 데이터는 메모리에 저장됩니다. 이 때 Build Input의 크기가 메모리에 맞지 않는 경우 메모리에 맞을 때까지 반복적으로 분할됩니다. 그리고 나서 Probe Input을 해시하여 일치하는 것이 있는지 검색합니다. 중첩 루프와는 달리 인덱스의 유무가 그렇게 중요한 것은 아닙니다. 중첩 루프와 비교했을 때 해시 조인은 CPU를 많이 사용하며 사용 가능한 메모리 공간의 영향을 받습니다. 해시 조인은 조인할 테이블의 크기가 많이 차이나는 경우 더 효과적으로 작용합니다.해시 조인에서 Build Input은 반복 횟수를 결정하게 되는데, 이는 입력이 메모리 크기에 맞게 되면 분할을 멈추기 때문입니다. 그룹화 특성이 조인 특성과 일치하는 경우 단일 해시 조인은 그룹화와 조인을 동시에 수행할 수 있습니다. 이 조인의 결과에는 어떤 특정 순서가 있는 것이 아닙니다. 이러한 유형의 조인은 부동 조건을 만족시킬 수는 없습니다. |--Hash Match(Inner Join, HASH:([s1].[sid])=([r1].[sid]),'reserves' 테이블. 스캔 횟수 1, 논리적 읽기 529, 물리적 읽기 0, 미리 읽기 0. 'sailors' 테이블. 스캔 횟수 1, 논리적 읽기 208, 물리적 읽기 0, 미리 읽기 0. 정렬 병합 조인(Sort-Merge Join)정렬 병합(Sort-Merge)에서는 다량의 입력을 정렬하면 총 비용이 많이 듭니다. 병합(Merge) 조인에서는 조인 열로 입력을 정렬하여 정렬한 쌍을 하나로 병합(Merge)하는데, 이 과정에서 정렬한 결과 집합과 일치하지 않는 열(Column) 값은 없애 버립니다.이 알고리즘은 먼저 한 입력을 검사하고 나서 크거나 같은 조인 값을 가진 행을 찾을 때까지 두 번째 정렬한 입력을 스캔합니다. R1의 튜플을 R2에 있는 모든 튜플과 짝을 지어 조인값을 일치시킵니다. R1에 있는 모든 튜플에 대해서도 이 과정을 반복합니다. 병합(Merge) 조인은 둘 중에서 더 작은 입력만 메모리에 두는 해시 조인과는 반대로 두 개의 입력이 모두 메모리에 있어야 합니다. 병합(Merge) 조인은 입력이 이미 정렬되어 있는 경우 훨씬 더 효과적입니다. 또한 이 조인의 결과는 조인 특성에서 정렬됩니다. 이러한 유형의 조인은 부동 조건을 만족시킬 수는 없습니다. |--Merge Join(Inner Join, MANY-TO-MANY MERGE:([r1].[sid])=([s1].[sid]), 'sailors' 테이블. 스캔 횟수 1, 논리적 읽기 208, 물리적 읽기 0, 미리 읽기 0. 'reserves' 테이블. 스캔 횟수 1, 논리적 읽기 529, 물리적 읽기 0, 미리 읽기 0. 상대적으로 크기가 매우 다양한 입력의 크기를 변경하면(보기에서 제시한 500개의 행이 있는 reserves와 50,000개의 행이 있는 sailors에서) 위와 동일한 쿼리의 병합(Merge) 조인은 다음에서 보는 것과 같이 해시 조인보다 훨씬 더 오래 걸립니다. 병합(Merge) 조인: SQL Server 실행 시간: CPU 시간 = 1081 ms, 경과 시간 = 2211 ms. 해시 조인 SQL Server 실행 시간: CPU 시간 = 181s, 경과 시간 = 479s. 조인 키에 인덱스가 있다면 데이터를 정렬할 필요가 없으므로 병합(Merge) 조인을 선택하는 것이 가장 좋습니다. ========================================================================== | ||||||||||
반응형