Hash Join & Semi Join
Hash Join
초 대형 데이터 처리를 위해서 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): 처리 되는 단위마다 동적으로 역할이 변함
1. 인-메모리 해쉬 조인
빌드입력; 빨간색(통계정보를 참조하여 효과적인 카디널리티를 갖는 집합선택)
- 조인의 연결을 위해서 기존의 인덱스를 전혀 사용하지 않음(인라인 뷰에서 가공한 집합과 조인하는 경우 유용)
- 부분 처리 가능(빌드 입력이 처리 범위를 줄여 줄 수 있거나 소형인 경우에 유용)
2. 유예 해쉬 조인
- 빌드 입력이 해쉬 영역을 초과하게 되면 디스크에 저장하여 처리
- 인-메모리의 처리 과정에 임시 세그먼트를 생성하여 디스크상에 위치시켜 가면서 처리 시키는 과정 추가
- 연결을 수행 할 수 없는 파티션들을 디스크로 이동
- 미리 생성되어 있는 인덱스를 사용하지 않음
- 부분 범위 처리가 불가능하게 됨
- 해쉬 조인이 소트머지 조인보다 더 많은 메모리 영역 필요(처리량에 따라서 손익의 차이가 나는 시점이 존재)
- SORT MERGE 조인과 해쉬 조인의 큰차이가 나지 않는경우 해쉬 조인은 추가적인 SORT 과정이 필요할 수 있음
Semi Join
서브 쿼리를 사용했을 때 메인 쿼리와의 연결 처리
1. 세미 조인의 개념 및 특징
- 서브 쿼리를 사용했을 때 메인 쿼리와의 연결을 하기 위해 적용되는 광범위한 유사 조인을 의미
- 조인은 동일한 동급상에 위치 서브 쿼리는 주종관계를 가짐
- 조인은 집합의 곱 1 * 1 = 1, 1 * M = M, M * 1 = M, M * M = MM(카티전곱)과 동일한 결과 집합을 가짐
- 세미 조인은 메인 쿼리의 결과 집합과 동일
- 서브 쿼리는 메인 쿼리의 컬럼을 마음대로 사용할 수 있지만 메인 쿼리는 서브쿼리의 집합에 있는 컬럼들을 사용할 수 없음
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'
서브 쿼리에 메인 쿼리 집합의 컬럼을 종속시키게 되면 서브 쿼리가 우선 실행되게 되어 경우에 따라 실행 계획의 비효율이 발생 할 수도 있다.
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인 경우 가능(해쉬 조인과 같은 방법으로 처리하다가 성공여부 결정만 반대로 수행)하다. 긍정형 연산에서는 NULL은 어차피 찾는 값이 아니므로 문제 될 것이 없으며, 부정형에서는 NULL이 비교연산에서 무시되어 원하는 값과는 달라질 수 있다.
출처: 두리누리