2.3.1. Nested Loops 조인 (by rnsl) [2009.05.17]
2.3.1. Nested Loops 조인
가장 전통적인 방법이면서도 가장 보편적으로 사용되는 조인 방법이다.
먼저 액세스한 결과를 다음의 액세스에 상수값으로 제공해 줄 수 있다는데 가장 큰
특징이 있다.
SELECT a.FLD1, ........, b.COL1, ............
FROM TAB1 a, TAB2 b
WHERE a.FLD1 = '111'
AND a.FLD2 LIKE 'AB%'
AND b.COL1 = '10';
가정 : TAB1 과 TAB2 는 M:1 관계에 있으며, 연결고리는 정상이고, 상수값으로
조건을 받고 있는 컬럼들은 각각 독립적으로 인덱스를 가진다고 가정 
[VLDB: 그림 2-2-14 ]
1) 먼저 TAB1의 FLD1 인덱스를 경유하여 FLD1='111' 인 처리범위 중 첫 번째 로우를
액세스한다.
2) FLD1 인덱스에 있는 ROWID 에 의해 TAB1 의 로우를 액세스한다. 액세스된 로우의
모든 컬럼값들은 상수값이 된다. 이 상수값을 가지고 FLD2 LIKE 'AB%' 조건을
체크하여 성공한 것은 다음으로 진행하고 실패하면 1)로 돌아가서 다음 건으로
다시 처리를 시도한다.
3) 여기서 성공한 것들에 대해 TAB1의 KEY1의 상수값을 이용하여 TAB2의 KEY2 인덱스로
대응되는 인덱스 로우를 찾는다. 물론 여기서도 대응되는 로우가 없다면 실패가 되어
1) 로 돌아가 다음 건을 시도한다.
4) KEY2 인덱스에 있는 ROWID 에 의해 TAB2 의 로우를 액세스한다. 이때 만약 KEY2+COL1
으로 인덱스가 구성되어 있다면 이 단계에서 COL1='10' 조건을 체크하고, 그렇지 않으면
다음 단계로 넘어간다. 물론 액세스된 TAB2의 모든 컬럼값들은 상수값이 된다.
5) COL1='10'의 확인을 위해 테이블에서 추출된 상수값을 가지고 비교하여 조건을 만족하면
최종적인 결과를 운반단위로 보낸다.
6) 이렇게 한 싸이클이 돌았으면 다시 FLD1 인덱스의 두 번째 로우를 읽어 위의 작업을
반복하게 된다. 만약 부분범위처리가 가능하다면 운반단위가 채워질 때까지만 수행되고
일단 멈출것이며, 전체범위처리라면 FLD1 범위가 끝날 때까지 계속(Nested)해서
반복(Loops) 수행된다.
\- 실제 사용된 인덱스는 드라이빙 범위를 수행한 'FLD1' 과 조인의 연결고리 역할을
수행한 KEY2만 사용되었음을 유의해야 한다.
이처럼 비록 조건에 사용된 모든 컬럼에 각각 인덱스가 있다고 하더라도 수행
절차에 따라서 인덱스가 사용될 수도 있고, 단순히 체크 조건 역할만 할 수 있다는
것을 확인 하기 바란다.
가) Nested Loops 조인의 특징
1) 순차적으로 처리된다. 선행 테이블(Driving table) 의 처림범위에 있는 각각의
로우들이 순차적으로 수행될 뿐만 아니라 테이블간의 연결도 순차적이다. (순차적)
2) 먼저 액세스되는 테이블의 처리범위에 의해 처리량이 결정된다. 즉, 선행하는
집합의 처리범위가 전체 일의 양을 결정한다. (선행적)
3) 나중에 처리되는 테이블은 앞서 처리된 값을 받아 액세스된다. 즉, 자신에게
주어진 상수값만으로 범위를 줄이는 것이 아니라 이미 가지고 있던 상수값과
제공받은 상수값을 합쳐서 그 중 가장 유리한 방법으로 연결이 진행된다. (종속적)
4) 주로 램덤 액세스 방식으로 처리된다. 선행 테이블의 인덱스를 액세스하는 방법은
첫 번째 로우만 랜덤 액세스이고, 나머지는 스캔이다. 그러나, 연결 작업은
모두 랜덤 액세스로 수행된다. (램덤 액세스)
5) 주어진 조건에 있는 모든 컬럼들이 인덱스를 가지고 있더라도 모두가 사용되는 것은
아니다. 연결되는 방향에 따라 사용되는 인덱스들이 전혀 달라질 수 있다. (선택적)
6) 연결고리가 되는 인덱스에 의해 연결작업이 수행되므로 연결고리 상태가 매우
중요하다. 연결고리의 인덱스 유무에 따라 액세스 방향 및 수행속도에 많은
차이가 발생된다 ( 연결고리 상태, 방향성 )
7) 부분점위 처리가 가능하다. 선행하는 집합의 하나씩의 로우를 대상으로 연결을 진행하기
때문에 부분범위 처리 조건을 만족하고 있다면 운반단위가 채워지는 순간에 우선 멈출
수가 있다. 물론 2차 가공을 해야 한다면 전체범위 처리를 할 수 밖에 없다
( 부분범위 처리 가능 )
8) 연결작업을 수행한 후 마지막으로 체크 되는 조건의 범위가 넓을수록 빨리 운반단위를
채울수 있으므로 오히려 빨라질 수 있으나, 2차 가공을 해야 하는 전체범위 처리일
때는 가공해야할 대상이 많아지기 때문에 수행속도가 나빠진다. (체크 조건의 영향력)
나) Nested Loops 조인의 적용기준
1) 부분범위처리를 하는 경우에 유리해진다.
대부분의 댜른 방식의 조인들은 원천적으로 부분범위 처리가 불가능해지기 때문에
부분범위로 처리하고자 한다면 이 조인 방식을 선택해야 한다. [VLDB: 예외도 있다. ]
2) 조인되는 어느 한쪽이 상대방 테이블에서 제공한 결과를 받아야만 처리범위를 줄일
수 있는 상황이라면 이 조인 방식을 선택해야 한다. 이것은 이 조인 방식을 적용해야
하는 가장 중요한 선택 요건이다.
3) 주로 처리량이 적은 경우(많더라도 부분범위처리가 가능한 경우) 라면 대개 이 조인
방식이 가장 무난하다.
4) 이 조인 방식은 연결 고리의 인덱스를 이용하기 때문에 연결고리의 상태에 따라 매우
큰 차이가 발생한다.
5) 먼저 수행한 집합의 처리범위의 크기와 얼마나 많은 처리 범위를 미리 줄여 줄 수
있느냐가 수행속도에 많은 영향을 미친다.
6) 부분범위처리를 하는 경우에는 운반단위의 크기가 수행속도에 상당한 영향을
미칠 수 있다. 운반단위가 적을 수록 빨리 운반단위를 채울 수 있으나 패치(fetch)
횟수에서는 불리해지는 이중성을 가지고 있다.
7) 선행 테이블의 처리 범위가 많거나 연결 테이블의 랜덤 액세스의 양이 아주 많다면
Sort Merge 조인이나 해쉬조인을 검토해야 한다.
2.3.1.2 Nested Loops 조인의 순서 결정
Nested Loop 조인은 먼저 수행된 결과가 다음에 연결할 범위에 절대적인 영향을
미치기 때문에 어떤 순서로 수행되느냐에 따라 조인의 효율은 크게 달라진다.
가장 큰 영향을 미치는 것은 최초에 수행되는 선행집합이다.
일단 먼저 인덱스 구성을 무시한 상태에서 조인의 순서에 따른 논리적인 처리 방법의
변화부터 살펴보기로 한다.
SELECT ...............
FROM TAB1 x, TAB2 y, TAB3 z
WHERE z.A1 = y.B1
AND z.C1 = y.B2
AND x.A2 = '10'
AND y.B2 LIKE 'AB%'
(1) TAB1 \-> TAB2 \-> TAB3
TAB1 A2 = '10'
TAB2 B1 = A1 AND B2 LIKE 'AB%'
TAB3 C1 = B2
(2) TAB2 \-> TAB3 \-> TAB1
TAB2 B2 LIKE 'AB%'
TAB3 C1 = B2
TAB1 A1 = B1 AND A2 = '10'
(3) TAB3 \-> TAB2 \-> TAB1
TAB3 FULL TABLE SCAN [VLDB: TAB3 의 모든 컬럼값은 '상수값' 이 된다. ]
TAB2 B2 = C1 AND B2 LIKE 'AB%'
TAB1 A1 = B1 AND A2 = '10'
어떤 컬럼이 액세스의 조건이 되기 위해서는 반드시 비교되는 값이 '상수값'
이어야 한다.
조인의 순서에 매우 중요한 영향을 미치는 또 하나의 요소는 조인의 성공률이다.
여기서 말하는 성공률이란 연결고리로 연결할 때의 성공률뿐만 아니라 연결한
후에 추가로 체크하는 조건을 통과한 최종 결과까지 감안한 것을 말한다.
두 개의 집합을 조인할 때는 보다 많은 처리범위를 줄여주는 집합이 선행되는
것만 중요하지만 세 개 이상의 테이블을 조인할 때는 각 조인의 단계의 성공률은
다음 단계의 조인량을 결정하게 된다.
집합이 증가할수록 다음에 조인할 대상이 증가하는 것은 당연하므로 조인의
순서를 결정할 때 가능하다면 'M' 집합은 나중에 처리될수록 좋다.
물론 항상 그렇다는 것은 아니다. 여기서 '가능하다면' 이라는 말의 진정한 의미는
'자신의 처리범위를 줄여줄 수 있는 다름 집합들이 액세스 된 후에'라는 의미와
'자신이 먼저 처리범위를 줄여줄 수 있다면 그들보다 먼저' 라는 의미가 포함되어 있다고
생각하면 된다.
SELECT .................
FROM ITEM_MST m, ITEM_MOVE v, VENDOR a, DEPT d.
WHERE m.ITEM_CD = v.ITEM_CD
AND a.VENDRO = v.MANUFACTURE
AND d.DEPTNO = v.ACT_DEPT
AND m.CATEGORY = :b1
AND m.PMA LIKE :b2
AND v.PATTERN = :b3
AND v.MOVE_DATE BETWEEN :b4 AND b5
AND d.LOCATION = :b6 ;
0 SELECT STATEMENT
124 NESTED LOOPS \
\- (b)
4218 NESTED LOOPS \---\- (a)
4218 NESTED LOOPS
4253 TABLE ACCESS ( BY ROWID ) OF 'ITEM_MST'
9621 INDEX ( RANGE SCAN ) OF 'ITEM_M_IDX1' (NON UNIQUE) \
--\- (1)
83212 TABLE ACCESS ( BY ROWID ) OF 'ITEM_MOV'
243209 INDEX ( RANGE SCAN SCAN ) OF 'ITEM_V_PK' (UNIQUE) \
--\- (2)
4218 TABLE ACCESS ( BY ROWID ) OF 'VENDOR'
4218 INDEX (UNIQUE SCAN) OF 'VENDOR_PK' (UNIQUE) \
-\- (3)
4218 TABLE ACCESS ( BY ROWID ) OF 'DEPT'
4218 INDEX ( UNIQUE SCAN ) OF 'DEPT_PK' (UNIQUE) \
--\- (4)
ITEM_MST \-> ITEM_MOVE \-> VENDOR \-> DEPT 순으로 수행
1) 인덱스를 스캔한 로우 수가 9621 인데 테이블을 액세스한 숫자는 4,253 이다.
이것은 무엇을 의미하는가 인덱스를 스캔한 개수보다 테이블을 액세스한 숫자가
적다는 것은 인덱스 내부에서 체크하여 걸러졌다는 것을 의미한다.
다시 말해서 'ITEM_M_IDX1' 인덱스에 주어진 조건인 CATAGORY 와 PMA 사이에
또 다른 칼럼이 존재하고 있었기 때문에 CATEGORY 의 처리범위인 9,620 개를
스캔하여 PMA 조건을 체크하니 4,253 개가 되었다는 것이다.
여기서 일단 인덱스 구조의 문제로 약간의 비효율이 발생되었다.
2) 선행처리되는 ITEM_MST 의 4,253 개에 대해 M 쪽 집합인 ITEM_MOV 가 기본키를
이용해 연결을 하고 있다. 약 1:57 [VLDB: 4253 - 243209 ] 의 비율로 연결이 되어
인덱스를 스캔한 숫자는 243.209 가 되었다. 그러나, 이것 역시 테이블을
액세스 한 것이 그 보다 적은 83,212 이었다는 것은 조건을 받은 PATTERN 이나
MOV_DATE 중 하나가 기본키에 포함되어 있기는 하지만 그 사이에 다른 칼럼이
존재하고 있어 인덱스 내에서 체크되었음을 알 수 있다. 이렇게 조인한 결과는
(a)에 나타나는 4,218 로 크게 감소한 것을 발견할 수 있다. 이것은 곧 기본키에
포함되지 않은 조건(아마 여기서는 MOV_DATE로 예상됨)으로 체크 되었기 때문이다.
3) 이제 상수값이 된 ITEM_MOV 의 MANUFACTURE 를 이용해 VENDOR 테이블을 연결하고
있다. 물론 기본키 연결하기 때문에 나타난 숫자는 인덱스, 테이블 스캔 모두 4,218
이다. 이것은 곧 연결을 통해서는 아무것도 줄여주지 못했음을 의미한다.
4) 마찬가지 방법으로 DEPT를 연결하였다. 그러나, (b)를 보면 최종적으로 성공한
것은 124 개에 불과하다는 것을 알 수 있다. 이것은 바로 DEPT에 부여한 조건인
LOCATION 으로 인한 것임을 쉽게 알 수 있다. 대부분의 처리가 완료된 후에
버려진 후에 버리게 되었다는 것은 이유가 어떠하든 간에 비효율 발생한 것은
틀림없다.
가장 이상적인 처리방법은 가장 많은 데이터를 가진 ITEM_MOV 테이블을 가장 먼저
최소의 범위를 만드는 일이다. 이를 위해 가장 많이 범위를 줄여주는 조건인
MOV_DATE 와 LOCATION 이 :b6 를 가진 DEPTNO 가 협렵해서 처리범위를 최소화 시켜주는
것이다.
결론부터 말한다면 DEPT \-> ITEM_MOVE \-> ITEM_MST \-> VENDOR 순으로 처리되는 것이
가장 유리하다. 많은 처리범위를 줄여주었던 LOCATION 이 영향력을 발휘하려면 가장 먼저
액세스하여 해당 DEPTNO 만 ITEM_MOV 에 제공해야 한다. 이때 가장 이상적인 인덱스
구조는 'ACT_DEPT+PATTERN+MOV_DATE' 이다. 이제 이들은 모두 상수값을 가지게 되었고
결합인덱스의 원리에 의해 완벽하게 필요한 범위만 스캔하게 된다.
[VLDB:그림 2-2-15 ]
최적의 조인 순서를 결정 하기 위해
\- 조인 하는 집합 중에서 제일 하위의 집합 찾기
\- 제일 하위의 집합이 확보할 수 있는 조건 체크 (상수값 ?은 비교조건)
\- 상기 2개 조건을 가지고 어느 쪽이 보다 처리범위를 많이 줄일 수 있는지 체크
\- 우열을 가릴수 없다면 소트머지 조인이나 해쉬조인으로 수행하는 것이 좋다.
문서에 대하여
- 이 문서는 오라클클럽 대용량 데이터베이스 스터디 모임에서 작성하였습니다.
- {*}이 문서의 내용은 이화식님의 새로쓴 대용량 데이터베이스 솔루션을 참고했습니다.*
- 이 문서를 다른 블로그나 홈페이지에 게재할 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^