Nested Loop 조인 (NL 조인)
NL 조인의 작동 순서는 다음과 같습니다.
- 드라이빙 테이블의 인덱스를 범위 스캔합니다.
- 필터조건이 있다면 테이블 액세스를 통해 필터 조건을 만족하는 레코드를 찾습니다.
- 드라이빙 테이블의 결과 레코드의 조인 칼럼의 수만큼 조인조건을 만족하는 드리븐 테이블의 레코드를 찾기위해 드리븐 테이블의 인덱스를 범위스캔합니다.
- 드리븐 인덱스에서 읽은 ROWID로 드리븐 테이블을 액세스해서 필터 조건을 만족하는 레코드를 찾습니다.
- 조인된 레코드를 정렬칼럼을 기준으로 정렬합니다.
NL 조인 부하지점
드라이빙 테이블의 인덱스를 스캔하는 양이 NL 조인의 첫 번째 부하지점입니다. 드라이빙 테이블로 많은 랜덤 액세스가 발생했는데 테이블 필터조건으로 필터링 되는 비율이 높다면 테이블 필터조건에 쓰인 칼럼을 인덱스에 추가하는 방안을 고려해야합니다.
두번째 부하지점은 드리븐 테이블의 인덱스를 탐색하는 부분입니다. 드리븐 테이블의 인덱스 높이가 높고 리프블록의 스캔범위가 넓다면 많은 랜덤 엑세스가 발생할 수 있습니다.
세 번째 부하지점은 드리븐 테이블을 테이블엑세스 하는 부분입니다. 테이블 필터조건에 의해 필터링되는 비율이 높으면 해당 칼럼을 인덱스에 추가하는 방안을 고려해야합니다.
OLTP 시스템에서 조인을 튜닝할 때는 일차적으로 NL 조인부터 고려하는 것이 올바른 순서입니다. 부하지점을 파악해 과도한 랜덤 엑세스가 발생하는 것을 방지해야합니다. NL 조인 효율화 방안을 검토한 후 NL 조인이 효과적이지 못하다고 판단되면 해시 조인이나 소트머지 조인을 검토합니다.
NL 조인의 특징
NL 조인은 렌덤 엑세스 위주의 조인 방식입니다. 따라서 인덱스 구성상 비효율이 없더라도 대량 데이터를 조인할 때 매우 비효율적입니다. 두 번째 특징은 조인을 한 레코드씩 순차적으로 진행한다는 점입니다. 엑세스되는 테이블의 처리 범위에 의해 전체 일량이 결정됩니다. 다른 조인방식과 비교했을 때, 인덱스 구성 전략이 특히 중요합니다. 조인 칼럼에 대한 인덱스 유무와 구성에 따라 조인효율이 크게 달라집니다.
이런 특징을 고려할때, NL 조인은 소량의 데이터 혹은 부분범위처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식입니다.
NL 조인 확장 메커니즘
PREPETCH
인덱스를 이용해 테이블을 엑세스하다가 디스크 i/O가 필요해지면, 이어서 읽게 될 데이터블록까지 미리 읽어 버퍼캐시에 적재하는 기능입니다.
BATCH I/O
테이블 엑세스를 미뤘다가 읽어야하는 블록이 일정량 쌓이면 한번에 처리하는 기능입니다. 두 기능 모두 읽는 블록마다 건건이 SINGLE BLOCK I/O 가 발생하는 비효율을 줄이기 위해 고안된 기능입니다.
--- 전통적인 실행계획
NESTED LOOPS
TABLE ACCESS BY INDEX ROWID OF EMP
INDEX RANGE SCAN OF EMP_X1
TABLE ACCESS BY INDEX ROWID OF CUS
INDEX RANGE SCAN OF CUS_X1
--- TABLE PREFECTH EXECUTEPLAN
TABLE ACCESS BY INDEX ROWID OF CUS
NESTED LOOP
TABLE ACCESS BY INDEX ROWID OF EMP
INDEX RANGE SCAN OF EMP_X1
INDEX RANGE SCAN OF CUS_X1
-- BATCH I/O EXECUTEPLAN
NESTED LOOPS
NESTED LOOPS
TABLE ACCESS BY INDEX ROWID OF EMP
INDEX RANGE SCAN OF EMP_X1
INDEX RANGE SCAN OF CUS_X1
TABLE ACCESS BY INDEX ROWID OF CUS
오라클 11g 이후 세 가지 실행계획이 모두 나타나는데 INNER 쪽 테이블 블록을 모두 버퍼캐시에서 읽으면 성능 상 차이는 없습니다. 다만 디스크 I/O가 발생하면 성능에 차이가 나타날 수 있습니다. 배치 I/O 실행계획이 나타날때는 결과 집합의 정렬순서도 달라질 수 있습니다.
소트머지조인
NL 조인은 드라이븐 테이블에 조인 칼럼을 선두로 갖는 인덱스가 있는지가 중요합니다. 만약 없다면 드라이빙 테이블의 결과 레코드마다 드라이븐 테이블 전체를 스캔하기 때문입니다. 이때 옵티마이저는 소트머지 조인이나 해시조인을 고민합니다.
소트머지 조인은 이름이 두 테이블을 각각 정렬한 다음 두 집합을 머지합니다.
- 소트단계 : 양쪽 집합을 조인 칼럼 기준으로 정렬합니다.
- 머지단계 : 정렬된 양쪽 집합을 merge 합니다.
조인 칼럼이 인덱스에 있으면 조인 칼럼을 기준으로 이미 정렬해 있기 때문에 소트 단계를 거치지 않고 곧바로 조인할 수 있습니다. ORACLE은 조인 연산자가 부등호이거나 아예 조인조건이 없어도 소트머지 조인을 처리할 수 있지만, SQL SERVER는 조인 연산자가 등치조건 일때만 소트머지조인을 수행합니다.
메커니즘
소트머지조인의 특징은 드라이븐 테이블이 정렬돼있기 때문에 조인에 실패하는 레코드를 만는 순간 추가적인 탐색이 불필요합니다. 또한 드라이빙 테이블 또한 같은 순서로 정렬되 있으므로 드라이븐 테이블에서 스캔 시작점을 찾기위해 매번 탐색하지 않아도 됩니다.
OUTER 집합(정렬된 dept) 에서 첫 번째 로우 o를 가져온다.
INNER 집합 (정렬된 emp) 에서 첫 번째 로우 i를 가져온다.
LOOP
양쪽 집합 중 어느 것이든 끝에 도달하면 Loop를 빠져나간다
IF O = I
조인에 성공한 로우를 리턴한다
inner 집합에서 다음 로우 i 를 가져온다.
ELSE IF I < O
inner 집합에서 다음 로우 o를 가져온다.
ELSE
outer 집합에서 다음 로우 I를 가져온다
END IF
END LOOP소트머지조인의 특징
조인 전 양쪽 집합을 정렬합니다.
NL 조인은 정렬없이 드라이빙 집합의 레코드를 순차적으로 조인합니다. 반면, 소트머지조인은 양쪽집합을 조인칼럼기준으로 정렬 후 조인합니다.
랜덤 액세스 위주의 NL 조인은 대량 데이터 조인의 경우 비효율이 발생할 수 있습니다. 초대량 데이터의 경우 정렬 자체가 큰 비용을 수반할 수 있기때문에 소소트머지조인을 통한 성능 개선효과를 얻지 못할 수 있습니다. 하지만 일반 인덱스나 클러스터형 인데스 처럼 미리 정렬된 오브젝트를 이용하면 추가적인 정렬없이 조인할 수 있어 좋은 대안이 됩니다.
부분범위처리가 가능합니다.
일부레코드만 FETCH 하다가 멈춘다면 OUTER 집합은 끝까지 읽지 않아도 됩니다.
테이블별 검색 조건에 의해 전체 일량이 좌우됩니다.
검색조건에 해당하는 집합을 정렬 후에 조인하기때문에 테이블 별 검색 조건에 의해 일량이 좌우됩니다.
스캔위주의 조인방식입니다.
NL 조인이 랜덤 엑세스 위주의 조인방식이라면 소트머지조인은 스캔 위주의 조인방식입니다. INNER TABLE은 반복 엑세스하지 않기때문에 머지과정에서 랜덤 엑세스가 발생하지 않습니다. 각 테이블의 검색조건에 해당하는 대상집합을 찾을 때 인덱스를 이용한 랜덤 액세스가 발생할 수 있고, 이때 발생하는 랜덤 엑세스가 많다면 소트머지 조인의 효과가 상쇄될 수 있습니다.
해시조인
메커니즘
해시조인은 NL JOIN 과 SORT MERGE JOIN의 비효율을 개선한 방식입니다. 해시 조인은 두 테이블의 결과 집합중 작은 집합을 읽어 해시 영역에 해시 테이블을 생성하고 반대쪽 큰 집합을 읽어 헤시테이블을 탐색하면서 조인하는 방식입니다. 해시 함수는 같은 입력에 대해 같은 출력을 보장합니다.
해시 테이블 생성시, 두 테이블의 결과집합 중 크기가 작을것으로 판단되는 집합을 읽어 해시 테이블을 만듭니다. 해시 테이블을 만들 때는 해시 함수를 사용합니다. 해시 함수에서 리턴 받은 값이 같은 데이터는 해시 버킷에 체인으로 연결합니다.(BUILD INPUT)
BUILD INPUT으로 선택되지 못한 테이블을 스캔해 결과집합을 PROBE INPUT으로 만듭니다. PROBE INPUT에서 읽은 데이터로 BUILD INPTU을 탐색할 때도 해시 함수를 사용합니다. 해시함수의 리턴 값으로 해시 체인을 스캔하며 조인할 데이터를 찾습니다.
해시조인은 조인과정에서 발생하는 랜덤 엑세스나 정렬에 대한 부담이 없습니다. 다만, 해시테이블을 생성하는 비용이 수반됩니다. 따라서 해시테이블을 만들 BUILD INPUT이 작을 때 효과적입니다. BUILD INPUT이 대용량 테이블일 경우 디스크 I/O가 발생하기 때문에 성능이 저하됩니다.
또한, 키 값으로 사용되는 칼럼에 중복 값이 없을때 효과적입니다. 해시테이블을 만드는 단계는 반드시 전체범위처리해야하지만 PROBE INPUT을 스캔하는 단계에서는 부분범위처리가 가능합니다.
BUILD INPUT의 크기가 가용 메모리 공간을 초과할 때 처리방식
IN-MEMORY 해시조인이 불가할때 DBMS는 GRACE 해시조인이라고 알려진 조인 알고리즘을 사용합니다.
파티션 단계
조인되는 양쪽 집합 모두 조인 칼럼에 해시함수를 적용하고 반환되는 해시 값에 따라 동적 파티셔닝을 생성합니다. 독립적으로 처리할 수 있는 작은 서브집합을 분할하여 파티션 짝을 생성합니다. 파티션 단계에서 양쪽 집합을 모두 읽어 디스크 상의 임시공간에 저장해야하므로 IN-MEMORY 해시조인보다 성능이 떨어집니다.
조인 단계
파티션이 완료되면 각 파티션 짝에 대해 하나씩 조인을 수행합니다. BUILD INPUT과 PROBE INPUT은 독립적으로 결정됩니다. 파티션 하기전 어느 쪽이 작은 집합이었는지에 상관없이 각 파티션 짝 별로 작은 쪽을 BUILD INPUT으로 삼아 해시 테이블을 생성합니다. 테이블이 생성되면 반대 쪽 파티션 로우를 하나
씩 읽으면서 해시 테이블을 탐색하고 모든 파티션 짝에 대한 처리가 완료될 때까지 반복합니다.
RECURSIVE 해시 조인
디스크에 기록된 파티션 짝끼리 조인을 수행하려고 작은 파티션을 메모리에 로드하는 과정에서 또다시 가용 메모리를 초과하는 경우 추가적인 파티셔닝 단계를 거칩니다. 이를 RECURSIVE 해시 조인라고 합니다.
해시조인 사용기준
해시 조인의 성능을 좌우하는 두 가지는 다음과 같습니다.
- 한 쪽 테이블이 가용 메모리에 담길정도로 충분히 작아야한다.
- BUILD INPUT 해시 키의 중복 값이 적어야한다.
해시 조인을 사용하는 것이 효과적인 기준은 다음과 같습니다.
- 조인 칼럼에 적당한 인덱스가 없어 NL 조인이 비효율적일때.
- 조인 칼럼이 인덱스에 있더라도 NL 조인 드라이빙 집합에서 드라이븐 집합쪽으로 조인 액세스량이 많아 랜덤 엑세스 부하가 심할때
- 소트 머지 조인을 하기에는 두 테이블이 너무 커 소트 부하가 심할때
- 수행빈도가 낮고 쿼리 수행시간이 오래 걸리는 대용량 테이블을조인할 때