메뉴 건너뛰기

bysql.net

이화식 선생님의 새로쓴 대용량 데이터 베이스 1의 온라인 스터디 입니다.
매주 각 스터디 팀원들이 담당 분량을 정리해서 올리고 토론식으로 진행합니다.
스터디 포스팅은 팀원들에의해 이루어지지만 스터디 참여는 사이트 회원 모두가 가능합니다.

진행기간: 2009.07 ~ 2009.10. 종료

2.3.4. 해쉬 (Hash) 조인

2009.09.14 00:00

휘휘 조회 수:98312

 
p 565 - 605

2.3.4. 해쉬 (Hash) 조인
데이터 처리범위가 초기보다 초대형으로 증가하면서 Sort Merge로 처리할수 없는 수준에 까지 도달
해쉬조인이 랜덤와 정렬의 부담을 벗어나게 할수 있는 원리를 알필요가 있음
- 인덱스를 경유하여 랜덤을 하지 않고 해쉬함수를 이용한 연결을 수행
- 파티션 단위로 처리하기 때문에 대량의 처리에 수행속도가 급격히 상승하지 않음

해쉬영역(Hash Area)
- 해쉬조인을 수행하기 위해 메모리 내에 만들어진 영역
- 비트맵 백터 ; 먼저 액세스 하는 빌드 입력의 유일한 값을 생성해 두었다가 나중에 검색하는 검색입력을 필터링
   해쉬테이블 ; 파티션들의 위치정보를 가지고 있으며 조인의 연결 작업을 수행하거나 디스크의 파티션 짝들을 찾는데 사용
   파티션테이블 ; 여러개의 파티션이 존재, 조인할 집합의 실제 로우들을 가짐

파티션 (Partition)
- 파티션을 결정하기 위해 수행하는 첫번째 해쉬함수가 리턴한 동일한 해쉬값을 갖는 묶음 (동일한 해쉬갑을 갖는 로우들의 버캣)
- Fan-out ; 인메모리에서 작업이 불가능하여 만들어진 파티션의 수
- 하나의 파티션은 여러개의 클러스터로 분리
- 2차 해싱을 하면 저장할 클러스터의 위치가 결정( I/O의 단위, 검색 단위 로활용)

클러스터(Cluster)
- 파티션의 분할
- 연속된 블록으로 이루어지며 디스크와 I/O를 하는 단위
- Hash_multiblock_io_count에 의해 동시 I/O 양 결정
- 해쉬테이블을 만들어 해당 클러스터를 찾고 클러스터를 스캔하여 원하는 로우와 연결

빌드입력(Build Input)과 검색입력(Probe Input)
- 빌드입력 ; 조인을 위해 먼저 액세스하여 필요한 준비를 처리
- 검색입력 ; 액세스하면서 조인을 수행하는 처리(검정 혹은 검색입력)

인-메모리(In-Memory) 해쉬조인과 유예 해쉬조인
- 인메모리 해쉬조인 ; 빌드입력이 해쉬영역에 모두 위치할수있는 경우 수행
- 유예 해쉬조인 ; 빌드입력이 해쉬영역에 모두 위치할수 없는 경우 수행

비트맵 백터(Bitmap Vector)
- 빌드입력에 대해 파티션을 구하는 작업중에 생성
- 빌드입력값들에 대한 유일한 값을 메모리 내의 해쉬영역에 정의하는것( 검색입력의 파티션 생성작업시 필터링에사용)
- 해쉬영역에 만들어지는 비트맵 벡터는 빌드 입력의 전체 집합에 대해서 생성
 (처리대상이 커서 해쉬영역을 초과하여 임시 세그먼트에 저장하게 되더라도 처리할 빌드 입력의 모든 집합에 대해 조인 종료시까지 유지)


해쉬 테이블(Hash Table)
- 메모리 내에 생성
- 조인의 연결 작업에서 대응되는 로우를 찾기 위한 해쉬 인덱스로 사용 (조인수행시 임시적으로 생성)
- 해쉬값과 해쉬 클러스터의 주소를 보유
- 검색입력에 있는 연결고리 값으로 해쉬키 값을 찾고, 그곳에 있는 클러스터 주소를 이용해 해당 클러스터를 찾아 스캔
- 해당 처리 단위의 빌드 입력에 대해서만 정보를 가지고 있음 (연결작업을 위한 인덱스 개념)


파티션 테이블 (Partition Table)
- 빌드입력이 메모리 크기를 초과하여 파티션을 생성하게 되면 관련정보가 저장되는곳
- 디스크의 임시세그먼트로 이동하면 그 위치정보 또한 보유
- 같은 묵음으로 처리되는 단위마다 파티션의 크기의 합이 적은 집합을 빌드입력으로, 나머지는 검색입력의 역할
- 동적 역할 반전 (Dynamic Role Reverse) ; 처리 되는 단위마다 동적으로 역할이 변함


2.3.4.1. 인-메모리 해쉬조인


INMEMORYHASH.PNG


* 빌드입력; 빨간색(통계정보를 참조하여 효과적인 카디널리티를 갖는 집합선택)



- 조인의 연결을 위해서 기존의 인덱스를 전혀 사용하지 않음 (인라인뷰에서 가공한집합과 조인하는경우 유용)
- 부분처리가 가능 (빌드 입력이 처리범위를 줄여줄수있거나 소형인경우에는 유용)

2.3.4.2. 유예 해쉬조인

- 빌드 입력이 해쉬영역을 최과하게 되면 디스크에저장하여 처리
- 인-메모리의 처리과정에 임시 세그먼트를 생성하여 디스크상에 위치시켜가면서 처리시키는 과정이 추가
- 연결을 수행할수 없는 파티션들을 디스크로 이동

- 미리 생성되어 있는 인덱스를 사용하지 않음
- 부분범위 처리가 불가능하게됨
- 해쉬조인이 소트머지 조인보다 더많은 메모리 영역을 필요 (처리량에 따라 손익의 차이가 나는 시점이 존재)
- SORT MERGE조인과 해쉬조인의 큰차이가 나지 않는경우 해쉬조인은 추가적인 SORT과정이 필요할수 있음


2.3.5.세미(Semi) 조인

- 서브쿼리를 사용했을 대 메인쿼리와의 연결하는 처리

2.3.5.1. 세미조인의 개념 및 특징
- 서브쿼리를 사용했을 때 메인 쿼리와의 연결을 하기 위해 적용되는 광범위한 유사 조인을 의미
- 조인은 동일한 동급상에 위치 서브쿼리는 주종관계를 가짐
- 조인은 집합의 곱 1*1=1, 1*M=M, M*1=M,M*M=MM(카티젼곱) 과 동일한 결과집합을 가짐
- 세미조인은 메인쿼리의 결과집합과 동일
- 서브쿼리는 메인쿼리의 컬럼을 마음대로 사용할수있지만 메인쿼리는 서브쿼리의 집합에 잇는 컬럼들을 사용할수 없음


2.3.5.2. 세미조인의 실행계획
가) Nested Loops 형 세미조인

- 서브쿼리가 '제공자' 역할을 할수도 '확인자' 역할을 할수도 있음
- 메인쿼리 집합의 보호

제공자
SELECT COL1,COL2,...
FROM TAB1 x
WHERE KEY1 IN (SELECT KEY2 FROM TAB2 y
                       WHERE y.COL1 ... AND y.COL2 ... );

실행계획

NESTED LOOPS
    VIEW
        SORT (UNIQUE) ---> 메인 쿼리 집합을 보호
            TABLE ACCESS BY ROWID OF TAB2
                INDEX RANGE SCAN OF COL1_IDX
TABLE ACCESS BY ROWID OF TAB1
    INDEX RANGE SCAN OF KEY1_IDX


확인자

SELECT 사번,성명,직급,입사일,....
FROM 사원 X
WHERE 부서='경리과'
    AND 사번 IN (SELECT 사번 FROM 가족 y
                      WHERE y.사번=x.사번 <-- 논리적으로 종속시킴 (실행에는 필요없음)
                        AND y.생년월일 < '20050101');


실행계획

FILTER
    TABLE ACCESS (BY ROWID) OF '사원'
            INDEX (RANGE SCAN) OF '부서_INDEX'
    TABLE ACCESS (BY ROWID) OF '가족'
            INDEX (RANGE SCAN) OF 'PK_INDEX'

SUB쿼리에 메인쿼리 집합의 컬럼을 종속시키게 되면 서브쿼리가 우선 실행되게 되어
경우에 따라 실행계획의 비효율이 발생할수도 있다.


나) Sort Merge 형 세미조인
연결고리의 이상이 발생하거나 대량의 데이터를 연결해야 할 때는 세미조인역시 SORT MERGE형 조인이 적용될수 있음

실행계획의 예

SELECT STATEMENT
    MERGE JOIN
        SORT (JOIN)
            TABLE ACCESS (FULL) OF '사원'

                SORT (JOIN)
                VIEW
                    SORT (UNIQUE)
                        TABLE ACCESS (BY ROWID) OF '근태'
                            INDEX (RANGE SCAN) OF '유형_일자_IDX' (NON-UNIQUE)




다) 필터(Filter)형 세미조인

먼저 수행하여 액세스한 결과를 서브쿼리를 통해 체크하여 취할것인지 아니면 버려야 할것인지를 결정하는 역할
버퍼내에 이전의 값을 저장해 두었다가 대응되는 집합을 액세스하기 전에 먼저 저장된값과 비교함으로 액세스를 최소화
EXISTS를 사용한 서브쿼리에서 대부분 나타남(언제나 확인자 역할만 가능함)

SELECT ... FROM ORDER x
WHERE ORDDATE LIKE '200506%'
    and    EXISTS (SELECT 'X'
                         FROM DEPT y
                         WHERE y.DEPTNO = x.SALDEPT  and y.TYPE1 = '1')

실행계획

FILTER
    TABLE ACCESS (BY ROWID) OF 'ORDER'
        INDEX (RANGE SCAN) OF 'ORDDATE_INDEX' (NON_UNIQUE)
    TABLE ACCESS (BY ROWID) OF 'DEPT'
        INDEX (UNIQUE SCAN) OF 'DEPT_PK' (UNIQUE)

필터 처리는 연결을 시도하다가 성공하는 로우를 만나면 연결작업을 멈춤
버퍼를 이용한 처리를 하여 랜덤 액세스 양을 최소화

라) 해쉬(Hash)형 세미조인

SELECT ... FROM ORDER x
WHERE ORDDATE LIKE '200506%'
    and    EXISTS (SELECT /*+ HASH_SJ(x,y) */  'X'
                         FROM DEPT y
                         WHERE y.DEPTNO = x.SALDEPT  and y.TYPE1 = '1')


실행계획
HASH JOIN SEMI
    TABLE ACCESS (BY ROWID) OF 'ORDER'
        INDEX (RANGE SCAN) OF 'ORDDATE_INDEX' (NON_UNIQUE)
    TABLE ACCESS (FULL) OF 'DEPT'

서브쿼리는 하나의 테이블만 존재
서브뭐리내에 또다시 서브쿼리를 사용했을 경우 사용불가
연결고리 연산자는 반드시 '=' 이어야 함
서브쿼리내에 GROUP BY,CONNECT BY, ROWNUM 을 사용할수 없음 (버전에 따라 다름)



마) 부정(Anti)형 세미조인
알지 못하는 값을 가지고 인덱스를 적용할 수 없기 때문에 연결 작업이 수행된다면 매우 심각한 부담이 발생

머지 부정형 조인으로 유도

SELECT COUNT(*) FROM TAB1
WHERE COL1 LIKE 'ABC%'
    and COL2 IS NOT NULL
    and COL2 NOT IN (SELECT /*+ MERGE_AJ */ FLD2
                             FROM TAB2
                             WHERE FLD3 between '20050101' and '20050131'
                                and FLD2 IS NOT NULL);

실행계획
SELECT STATEMENT Optimizer=FIRST_ROWS
    MERGE JOIN (ANTI)
        SORT (JOIN)
            TABLE ACCESS (BY ROWID) OF 'TAB1'
                INDEX (RANGE SCAN) OF 'COL1_INDEX' (NON-UNIQUE)
        SORT (UNIQUE)
            VIEW
                TABLE ACCESS (BY ROWID) OF 'TAB2'
                    INDEX (RANGE SCAN) OF 'FLD3_INDEX' (NON-UNIQUE)

- 반드시 NOT IN 을 사용, 비용기준 옵티마이져, NOT NULL 이 보장

해쉬 부정형 조인으로 유도

SELECT COUNT(*) FROM TAB1
WHERE COL1 LIKE 'ABC%'
    and COL2 IS NOT NULL
    and COL2 NOT IN (SELECT /*+ HASH_AJ */ FLD2
                             FROM TAB2
                             WHERE FLD3 between '20050101' and '20050131'
                                and FLD2 IS NOT NULL);

실행계획
SELECT STATEMENT Optimizer=FIRST_ROWS
    HASH JOIN (ANTI)
            TABLE ACCESS (BY ROWID) OF 'TAB1'
                INDEX (RANGE SCAN) OF 'COL1_INDEX' (NON-UNIQUE)
            VIEW
                TABLE ACCESS (BY ROWID) OF 'TAB2'
                    INDEX (RANGE SCAN) OF 'FLD3_INDEX' (NON-UNIQUE)


-'NOT IN' 만가능
- NOT NULL 이라는 전제가 있을때만 가능 (HASH조인과 같은방법으로 처리하다가 성공여부 결정만 반대로 수행)
- 긍정형연산에서는 NULL은 어차피 찾는 값이 아니므로 문제 될것이 없음
- 부정형에서는 NULL이 비교연산에서 무시되어 원하는값과는 달라질수 있음

번호 제목 글쓴이 날짜 조회 수
» 2.3.4. 해쉬 (Hash) 조인 file 휘휘 2009.09.14 98312
24 2.3. 조인 종류별 특징및 활용 방안 휘휘 2009.09.13 93137
23 2부 2.3.(2.3.6-2.3.8) 조인 종류별 특징 및 활용 방안(스타조인, 비트맵조인인덱스) [1] file balto 2009.09.08 107160
22 제2부 2장 조인의 최적화 방안 file 휘휘 2009.09.06 98426
21 제2부 1.4.7. 저장형 함수를 이용한 부분 범위 처리 휘휘 2009.09.06 81252
20 2.2. 연결고리 상태가 조인에 미치는 영향 file balto 2009.09.05 118351
19 2부 1.4.(1.4.1-1.4.7) 부분범위처리로의 유도 (중요하지 않은 부분 조금 미완성) file balto 2009.08.29 95778
18 4.2. 클러스터링 형태의 결정 기준 file balto 2009.08.27 99650
17 4.1.6. 인덱스 선정 절차 휘휘 2009.08.24 102471
16 3.2.4. 비트맵(Bitmap) 실행계획 휘휘 2009.08.24 95075
15 3.3. 실행계획의 제어 [1] 휘휘 2009.08.18 100492
14 4.1. 인덱스 선정기준(4.1.1.-4.1.5.) [3] file balto 2009.08.17 100766
13 3.2.2. 데이터 연결을 위한 실행 계획 [2] file balto 2009.08.06 101229
12 3.2. 실행계획의 유형 (1/3) - 3.2.1. 스캔의 기본유형 휘휘 2009.08.03 103259
11 3.1 SQL의 실행계획 (2/3) 운영자 2009.07.25 101062
10 3.1 SQL의 실행계획 (3/3) file 운영자 2009.07.19 93361
9 3.1 SQL의 실행계획 (1/3) 운영자 2009.07.19 102160
8 2.2. 비트맵(Bitmap) 인덱스 [2] file 휘휘 2009.07.15 122543
7 2.3 함수기반 인덱스 (FBI,Function-Based Index) [1] 운영자 2009.07.12 160348
6 2.1. B-tree 인덱스 [2] 운영자 2009.07.10 107210