대용량 데이터베이스솔루션 1 (2009년)
조인의 최적화 0 0 80,577

by 구루비스터디 Nested Loop Join Sort Merge Join 조인 최적화 [2009.04.29]


2.1 조인효율 향상의 원리

가. 조인 순서

(1) 조인의 효율
  • 조인되어야 할 각 집합의 처리범위와 순서에 따라 영향을 받는다.
  • 즉, 처리범위가 가장 좁은 범위를 먼저 처리할 수록 조인의 효율은 증가한다.

(2) TABLE1 -> TABLE2 -> TABLE3
  • 1)TABLE1의 처리 범위인 10,000 로우의 첫번째 로우를 읽는다.
  • 2)읽혀진 TABLE1의 값에 대응하는 TABLE2의 로우를 찾는다
  • 3)TABLE2의 조인 컬럼값과 대응되는 TABLE3의 로우를 찾는다.
  • 4)TABLE1의 처리범위가 모두 끝날 때까지 계속한다. => 최소 10,000회 이상ACCESS
(3) TABLE3 -> TABLE2 -> TABLE1
  • 1)TABLE3의 처리 범위인 2개 로우의 첫번째 로우를 읽는다.
  • 2)읽혀진 TABLE3의 값에 대응하는 TABLE2의 로우를 찾는다
  • 3)TABLE2의 조인 컬럼값과 대응되는 TABLE1의 로우를 찾는다.
  • 4)TABLE3의 두번째 로우를 읽어 위의 작업을 반복한다. => 최대 6회 이하ACCESS
(4) 결론
  • Nested Loop 조인에서는 가장 먼저 수행되는 집합의 처리범위가 전체 일량을 좌우한다.
  • 따라서 가장 적은 처리 범위를 가진 테이블이 먼저 수행되도록 하면 최적의 조인을 구현할 수 있다.

나. 조인 성공률

(1) 조인 작업이 수행된 후 조건을 만족하는 총 로우수(성공된 로우수)

(2) TABLE1 -> TABLE2 -> TABLE3
  • 1) TABLE1의 처리 범위인 100 로우의 첫번째 로우를 읽는다.
  • 2) 읽혀진 TABLE1의 값에 대응하는 TABLE2의 로우를 찾는다
  • 3) TABLE21과 TABLE2의 연결작업에 성공한 각각의 로우들에 대응하는 TABLE3의 로우를 찾는다.
  • 4) TABLE1의 두번째 로우를 읽어 위의 작업을 반복한다. => TABLE1:TABLE2=1:10 이므로 1000회 ACCESS
    • 이 1000개의 로우에 대해 TABLE3와 연결작업(1000회 ACCESS)
(3) TABLE1 -> TABLE3 -> TABLE2
  • 1) TABLE1의 처리 범위인 100 로우의 첫번째 로우를 읽는다.
  • 2) 읽혀진 TABLE1의 값에 대응하는 TABLE3의 로우를 찾는다.(2개)
  • 3) TABLE21과 TABLE3의 연결작업에 성공한 각각의 로우들에 대응하는 TABLE2의 로우를 찾는다.
  • 4) TABLE1의 두번째 로우를 읽어 위의 작업을 반복한다. => TABLE1:100회 ACCESS, TABLE3:2회 ACCESS (총102회)
(4) 결론
  • -> 세 개 이상의 집합에 대한 조인 효율은 조인 성공률이 낮은 집합의 조인이 먼저 일어나는 것이 유리하다.

다. 연결고리 상태

(1) 연결고리 정상
  • 조건절에 기술되는 조인의 연결 컬럼에 인덱스가 모두 존재하는 상태

1) TAB1 -> TAB2
  • ㄱ) TAB1의 처리 범위인 첫번째 로우를 읽는다.
  • ㄴ) TAB2의 연결고리가 되는 인덱스가 있으므로 TAB1의 연결고리의 값에 대응되는 로우를 KEY2에서 찾는다.
  • ㄷ) KEY2에 있는 ROWID를 이용하여 TAB2를 읽는다.
  • ㄹ) TAB1의 두번째 로우를 읽어 위의 작업을 반복한다.
2) TAB2 -> TAB1
  • ㄱ) TAB2의 처리 범위인 첫번째 로우를 읽는다.
  • ㄴ) TAB1의 연결고리가 되는 인덱스가 있으므로 TAB2의 연결고리의 값에 대응되는 로우를 KEY1에서 찾는다.
  • ㄷ) KEY1에 있는 ROWID를 이용하여 TAB1를 읽는다.
  • ㄹ) TAB2의 두번째 로우를 읽어 위의 작업을 반복한다.
3) 결론
  • 연결고리가 정상인 상태에서는 어느 방향으로 연결작업이 수행되든 간에 발생되는 연결작업은 동일하다.
  • 그러나 처리범위를 줄여주는 테이블이 먼저 처리되면 수행속도가 향상된다.
  • (연결고리가 정상인 경우 수행속도를 좌우하는 것은 연결고리가 아니라 먼저 연결되는 테이블의 처리범위이다.)

처리 범위에 따른 ACCESS량

1) SQL

 SELECT a.FLD1, ........., b.FLD1, .........
 FROM TAB2 b, TAB1 a
 WHERE a.KEY1 = b.KEY2
 AND b.FLD2 LIKE 'ABC%' * => 만족범위: 10 로우
 AND a.FLD1 = '10' * => 만족범위: 200 로우

2) TAB1 -> TAB2
  • ㄱ) FLD1='10'의 처리범위인 첫번째 로우를 찾아 인덱스의 ROWID를 이용하여 TAB1의 로우를 찾는다.
  • ㄴ) TAB2의 KEY2인덱스를 이용해 KEY1의 상수값과 대응되는 로우를 찾는다. 연결에 성공했다면 KEY2인덱스에 있는 ROWID를 이용하여 TAB2의 로우를 찾는다.
  • ㄷ) FLD2 LIKE 'ABC%'를 만족하는 로우만 운반단위로보낸다. 만약 'KEY2+FLD2'로 결합인덱스가 있다면 3의 작업은 수행하지 않고 2작업시 같이 처리된다.
  • ㄹ) 다시 TAB1의 두번째 로우를 읽어 위의 작업을 반복한다.
    • TAB1의 처리범위인 200로우를 모두 처리하였거나, 만약 부분범위처리라면 200로우까지 수행하지 않았더라도
    • 추출된 로우가 운반단위까지 도달한 경우 반복작업이 멈추게 된다. => 최소 200회 이상
3) TAB2 -> TAB1
  • ㄱ) FLD2 LIKE 'ABC%'의 처리범위인 첫번째 로우를 찾아 인덱스의 ROWID를 이용하여 TAB2의 로우를 찾는다.
  • ㄴ) TAB1의 KEY1인덱스를 이용해 KEY2의 상수값과 대응되는 로우를 찾는다. 연결에 성공했다면 KEY1인덱스에 있는 ROWID를 이용하여 TAB1의 로우를 찾는다.
  • ㄷ) FLD1='10'를 만족하는 로우만 운반단위로 보낸다. 만약 'KEY1+FLD1'로 결합인덱스가 있다면 3의 작업은 수행하지 않고 2작업시 같이 처리된다.
  • ㄹ) 다시 TAB2의 두번째 로우를 읽어 위의 작업을 반복한다.
    • TAB2의 처리범위인 10로우를 모두 처리하였거나, 만약 부분범위처리라면 10로우까지 수행하지 않았더라도
    • 추출된 로우가 운반단위까지 도달한 경우 반복작업이 멈추게 된다. => 최대 20회 이내
만약 규칙기반 옵티마이저(RBD) 모드라면..
  • 수정 전

SELECT a.FLD1, ........., b.FLD1, .........
  FROM TAB2 b, TAB1 a
 WHERE a.KEY1 = b.KEY2
   AND b.FLD2 LIKE 'ABC%'
   AND RTRIM(a.FLD1) = '10'

  • 수정 후

SELECT /*\+ ORDERED \*/
       a.FLD1, ........., b.FLD1, .........
  FROM TAB2 b, TAB1 a
 WHERE a.KEY1 = b.KEY2
   AND b.FLD2 LIKE 'ABC%'
   AND RTRIM(a.FLD1) = '10'

  • 우선 규칙에 따라 TAB1이 먼저 처리 되므로 사용제한 기능이나 힌트를 사용하여 TAB2가 먼저 처리되도록 한다.
만약 비용기반 옵티마이저(CBD) 모드라면
  • b.FLD2와 a.FLD1의 분포도에 따라 유리한 TAB이 먼저 엑세스 되도록 실행계획이 수립된다.
(2) 한쪽 연결고리 이상
  • 어느 한쪽의 연결고리에 인덱스(혹은 클러스터)가 없는 연결고리 이상인 상태

1) TAB1 -> TAB2
  • ㄱ) TAB1에서 처리해야 할 범위의 첫번째 로우를 읽는다.
  • ㄴ) TAB2의 KEY2에는 인덱스가 없으므로 TAB2를 전부 스캔하여 'KEY2=KEY1'을 만족하는 로우를 찾는다.
  • ㄷ) 값을 찾더라도 멈추지 않고 테이블 끝까지 스캔한다.
  • ㄹ) TAB1의 두번째 로우를 읽어 TAB2의 전체 테이블 스캔을 한다.(TAB1의 처리범위가 끝날 때까지)
2) TAB2 -> TAB1
  • ㄱ) 이 그림은 '연결고리 정상'상태의 두번째 그림과 동일함.(TAB2는 한번만 액세스 된다.)
  • ㄴ)OPTIMIZER는 무조건 현재의 방법으로 처리함.
3) 결론
  • 연결고리가 어느 한쪽에 이상이 있는 경우는 이상이 발생한 테이블을 반드시 먼저 처리해야만 유리하다.

연결고리 이상상태를 발생시키는 유형

1) 조인되는 컬럼이 1:1로 대응되지 않는 경우

 SELECT ..., columns, ...
 FROM TABLE1, TABLE2 * -> TABLE1컬럼들 사용제한,그러므로 TABLE1 먼저엑세스
WHERE A \|\| B \|\| C = D


 SELECT ..., columns, ...
 FROM TABLE1, TABLE2 * -> TABLE2컬럼들 사용제한,그러므로 TABLE2 먼저엑세스
 WHERE A = substr(D,1,2)
 AND B = substr(D,3,1)
 AND B = substr(D,4,3)

2) 데이터 타입의 차이에 의해 발생되는 경우
  • CHAR 타입의 컬럼과 NUMBER 타입의 컬럼을 비교할 경우 연결고리 이상발생

2.2 조인의 튜닝(Tuning)

  • 옵티마이져는 단지 액세스 경로를 찾아준다.(경로를 새롭게 생성하지는 않는다)
  • 옵티마이져의 판단과는 상관없이 최적의 처리경로를 알아야 한다.
  • 어떤 옵티마이져든 항상 최적의 액세스 경로를 찾아줄 수는 없다.(높은 확률로 최적의 경로를 찾아준다)
  • 중요한 몇 개의 자료를 토대로 통계학적으로 분석하여 가능한 보다 높은 확률로 양호한 액세스 경로를 판단한다.
  • 옵티마이져의 액세스 경로를 결정하는 요소(인덱스, 클러스터 등) 들에 따라 차이가 발생한다.
    즉, 같은 액세스 경로로 처리되더라도 비교한 값의 실제 처리 범위에 따라 큰 차이가 날 수도 있다.
  • 옵티마이져는 경우에 따라 별도의 튜닝이 필요할 수도 있다.

1) TAB1 -> TAB2 -> TAB
  • ㄱ)TAB1: 상수값을 가진 칼럼(x.A2='10')의 첫번째 로우를 읽는다. => TAB1의 모든 컬럼 값은 상수가 된다.
  • ㄴ)TAB2: y.B1=x.Aq, y.b2 LIKE 'B%'의 조건으로 액세스 한다.
  • ㄷ)TAB3: z.C1=y.B2의 조건으로 액세스 된다.
2) TAB2 -> TAB3 -> TAB1
  • ㄱ)TAB2: y.b2 LIKE 'B%'의 조건으로 액세스 한다.
  • ㄴ)TAB3: z.C1=y.B2의 조건으로 액세스 된다. (<= y.B2가 상수값이 되었으므로)
  • ㄷ)TAB1: x.A1=y.B1, x.A2='10'의 조건으로 액세스된다. (<= y.B1이 상수값이 되었으므로)
3) TAB3 -> TAB2 -> TAB1
  • ㄱ)TAB3: z.C1=y.B2의 조건으로 액세스 해야 하나 y.B2가 미지수 이므로 전체 테이블 스캔한다.
  • (=> TAB3의 첫번째 로우를 읽는 순간 모든 컬럼값은 상수가 된다.)
  • ㄴ)TAB2: y.B2=z.C1, y.b2 LIKE 'B%'의 조건으로 액세스 한다.(<= z.C1이 상수값이 되었으므로)
  • ㄷ)TAB1: x.A1=y.B1, x.A2='10'의 조건으로 액세스된다. (<= y.B1이 상수값이 되었으므로)
튜닝의 절차
  • 1)유리한 조인 유형 선택 (Nested Loop, Sort Merge조인)
  • 2)연결고리의 상태 확인 (연결고리에 이상이 있다면 인덱스 추가여부 결정)
  • 3)연결고리를 제외한 컬럼들의 조건에 사용된 연산자와 인덱스의 상태를 비교하여 처리범위를 가장 줄여주는 조건을 찾는다.

2.3 조인과 반복연결(Loop Query)

가. 전체범위처리방식의 조인

(1) JOIN
  • 1)TAB1에서 처리해야 할 전체범위를하나씩 스캔하여 대응되는 TAB2의 로우를 연결한다.
  • 2)1000번의 연결을 하더라도 단 한번의 SQL만 수행된다.
(2) LOOP-QUERY
  • 1)TAB1에서 처리해야 할 전체범위를 하나씩 스캔한 후 별도의 SQL을 수행하여 TAB2의 로우들을 랜덤 액세스한다.
  • 2)1000번의 연결에 1001번의 SQL이 수행된다.
(3) 반복 연결이 유리한 경우 1
  • 1) SQL

SELECT a.FLD1, ........., b.FLD1, .........
  FROM TAB2 b, TAB1 a
 WHERE a.KEY1 = b.KEY2
   AND a.FLD1 = '10'
 ORDER BY a.FLD2 * -> 이 SQL에서 ORDER BY 절 때문에 전체범위처리를 한다.

  • 2) 개선

SELECT FLD1, ........., FLDn
  FROM TAB1*
WHERE FLD1 = '10'
 ORDER BY FLD2


SELECT COL1, ........., COLn
  FROM TAB2
 WHERE KEY2 = :a.KEY1

(4) 반복 연결이 유리한 경우 2
  • 1) SQL

 SELECT b.부서명, SUM(a.매출액)* -> 이 SQL은 두개 테이블의 전체범위를 모두 조인한 후
 FROM TAB1 a, TAB2 b* GROUP BY를 하여 운반단위만큼 추출.
 WHERE a.부서코드 = b.부서코드 * -> 불필요한 부서명TABLE(TAB2)에 대하여 연결작업을 반복함.
 AND a.매출일 LIKE '9503%'
GROUP BY b.부서명

  • 2) 개선

SELECT 부서코드, sum(a.매출액)
  FROM TAB1
 WHERE 매출일 LIKE '9503%'
 GROUP BY 부서코드\\


SELECT 부서명
FROM TAB2
WHERE 부서코드 = :a.부서코드

나. 부분범위처리방식의 조인

(1) JOIN
  • 1)단 한번의 SQL이 수행됨
  • 2)SQL내에서 조인된 모든 컬럼 가공
(2) LOOP-QUERY
  • 1)(운반단위 \+1)번의 SQL이 수행됨
  • 2)별도의 언어를 통해서 추가적인가공 필요

다. 결론

  • 전체범위처리가 된 이유가 연결되는 모든 테이블에 원인이 있다면 조인이 빠르다.
  • 연결되는 테이블 중 하나를 부분범위처리로 바꿀 수 있다면 반복연결방식이 빠르다.
  • SQL이 부분범위처리가 된다면 조인이 빠르다.

2.4 Nested Loop 조인과 Sort Merge 조인

가. Nested Loop 조인

  • 어떤 테이블의 처리범위를 하나씩 엑세스 하면서 그 추출된 값으로 연결할 테이블을 조인하는 방식

(1) SQL

 SELECT a.FLD1, ........., b.COL1, .........
 FROM TAB1 a, TAB2 b
 WHERE a.KEY1 = b.KEY2
 AND a.FLD1 = 'AB'
 AND b.FLD2 = '10'

(2) TAB1 -> TAB2
  • 1)TAB1의 FLD1인덱스를 경유하여 FLD1='AB'인 처리범위 중 첫번째 로우 액세스.
  • 2)FLD1인 인덱스에 있는 ROWID에 의해 TAB1로우를 액세스.
  • 3)TAB2의 KEY2인덱스를 이용하여 대응되는 인덱스 로우를 찾는다.
  • 4)KEY2인덱스에 있는 ROWID에 의해 TAB2의 로우를 액세스 한다.
  • 5)테이블에서 추출된 값을 가지고 조건을 만족하면 최종결과를 운반단위로 보낸다.(조건: FLD2='10')
(3) 특징
  • 1) 순차적으로 처리된다.
    • 선행테이블(Driving table)의 처리범위에 있는 각각의 로우들이 순차적으로 수행될 뿐만 아니라 테이블 간의 연결도 순차적이다. (* 순차적)
  • 2) 먼저 액세스 되는 테이블의 처리범위에 의해 처리량이 결정된다. (* 선행적)
  • 3) 나중에 처리되는 테이블은 앞서 처리된 값을 받아 액세스 된다.
    • 즉, 자신에게 주어진 상수값에 의해 스스로 범위를 줄이는 것이 아니라 값을 받아서 처리범위가 정해진다. (* 종속적)
  • 4) 주로 랜덤액세스 방식으로 처리된다.
    • 선행테이블의 인덱스 액세스는 첫번째 로우만 랜덤 액세스이고 나머지는 스캔이며 연결작업은 모두 랜덤 액세스이다. (* 랜덤액세스)
  • 5) 주어진 조건에 있는 모든 컬럼들이 인덱스를 가지고 있더라도 모두가 사용되는 것은 아니다.
    • 연결되는 방향에 따라 사용되는 인덱스들이 전혀 달라질 수 있다. (* 선택적)
  • 6) 연결고리가 되는 인덱스에 의해 연결작업이 수행되므로 연결고리 상태가 매우 중요하다.
    • 연결고리의 인덱스 유무에 따라 액세스 방향 및 수행속도에 많은 차이가 발생된다. (* 연결고리상태, * 방향성)
  • 7) 연결작업 수행 후 마지막으로 CHECK되는 조건은 부분범위처리를 하는 경우에는 조건의 범위가 넓을 수록, 아예 없다면 오히려 빨라진다. (* 부분범위처리 가능)
(4) 사용기준
  • 1) 부분범위처리를 하는 경우에 주로 유리하다.
  • 2) 조인되는 어느 한쪽이 상대방 테이블에서 추출된 결과를 받아야 처리범위를 줄일 수 있다.
  • 3) 주로 처리량이 적은 경우에 유리하다. (처리방식이 주로 랜덤액세스이기 때문에 많은 양의 랜덤액세스에서는 수행속도가 당연히 나빠진다.)
  • 4) 가능한 한 연결고리 이상 상태를 만들지 않도록 주의해야 한다.
  • 5) 최적의 액세스 순서가 되도록 조치해야 한다. (순차적으로 처리되기 때문에 어떤 테이블이 먼저 액세스 되느냐에 따라 수행속도에 영향을 미친다.)
  • 6) 부분범위처리를 하는 경우에는 운반단위의 크기가 수행속도에 많은 영향을 미칠 수 있다.
  • 7) 선행테이블의 처리범위가 많거나 연결테이블의 랜덤액세스의 양이 아주 많다면 Sort Merge조인보다 불리해 질 수 있다.

나. Sort Merge 조인

  • 양쪽 테이블의 처리범위를 각자 액세스하여 정렬한 결과를 차례로 스캔하면서 연결고리의 조건으로 머지해 가는 방식

(1) SQL

 SELECT a.FLD1, ........., b.COL1, .........
 FROM TAB1 a, TAB2 b
WHERE a.KEY1 = b.KEY2
 AND a.FLD1 = 'AB'
 AND b.FLD2 = '10'

(2) TAB1 -> TAB2
  • 1) TAB1의 FLD1인덱스를 경유하여 FLD1='AB'인 범위를 차례로 액세스 하여 연결고리인 KEY1의 값으로 정렬해 둔다.
  • 2) TAB2도 FLD2인덱스를 경유하여 FLD2= '10'인 범위를 차례로 액세스하여 연결고리인 KEY2의 값으로 정렬해 둔다.
  • 3) 두개의 정렬된 결과를 스캔하면서 KEY1= KEY2를 만족하는 로우를 찾도록 머지하여 운반단위가 채워지면 추출한다.
  • 4) TAB1은 FLD1,TAB2는 FLD2인덱스만 사용됨
  • 5) 연결고리인 KEY1, KEY2의 인덱스는 전혀 사용되지 않았고 단지 머지 조건으로만 사용되었다.
(3) 특징
  • 1) 동시에 처리된다. 테이블 각자가 자신의 처리범위를 액세스하여 정렬해 둔다.(* 동시적)
  • 2) 각 테이블은 다른 테이블에서 어떠한 상수값도 제공받지 않고 자신에게 주어진 상수값만으로 범위를 줄인다.(* 독립적)
  • 3) 부분범위처리를 할 수 없으며 항상 전체범위처리를 한다.(* 전체범위처리)
  • 4) 주로 스캔방식으로 처리한다. 자신의 처리범위를 줄이기 위해 인덱스를 사용하는 경우엔 랜덤액세스 이고, 머지하는 작업은 스캔방식이다.
  • 5) 주어진 조건에 있는 컬럼들이 인덱스를 가지고 있더라도 모두가 사용되는 것은 아니다. 연결고리가 되는 컬럼은 인덱스를 전혀 사용하지 않는다.
  • 6) 조인의 방향과는 무관하다.(* 무방향성)
  • 7) 스스로 자신의 처리범위를 줄이기 위해서 사용되는 인덱스는 대개 가장 유리한 한가지만 사용된다. (머지할 작업대상을 줄여주는 역할을 하기 때문에 중요한 의미를 가진다.)
(4) 사용기준
  • 1) 전체범위처리를 하는 경우에 주로 유리하다.
  • 2) 상대방 테이블에서 어떤 상수값을 받지 않고도 처리범위를 줄일 수 있는 상태인 경우 주로 유리하다.
  • 3) 주로 처리량이 많은 경우에 유리하다. (처리방식이 스캔방식이기 때문에 많은 양의 랜덤 액세스를 줄일 수 있기 때문)
  • 4) 연결고리를 위한 인덱스를 생성할 필요가 없을 때 유용하다.
  • 5) 스스로 자신의 처리범위를 어떻게 줄이느냐가 수행속도에 많은 영향을 미친다.(효율적으로 액세스 할 수 있는 인덱스구성이 중요함)
  • 6) 전체범위처리를 하므로 운반단위의 크기가 수행속도에 영향을 미치지 않는다.
  • 7) 처리할 데이터 량이 적은 온라인 애플리케이션에서는 Nested Loop조인이 유리한 경우가 많으므로 사용시 주의해야 한다.
  • 8) 옵티마이져 목표(goal)가 'ALL_ROWS'인 경우는 Sort Merge조인으로 실행계획이 수립되므로 부분처리를 하고자 한다면 주의해야 한다.

참고문헌

문서에 대하여

  • 최초작성자 : 이재광
  • 최초작성일 : 2009년 02월 20일
"구루비 데이터베이스 스터디모임" 에서 2009년에 "대용량 데이터베이스 솔루션 1" 도서를 스터디하면서 정리한 내용 입니다.

- 강좌 URL : http://www.gurubee.net/lecture/2466

- 구루비 강좌는 개인의 학습용으로만 사용 할 수 있으며, 다른 웹 페이지에 게재할 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^

- 구루비 강좌는 서비스 제공을 위한 목적이나, 학원 홍보, 수익을 얻기 위한 용도로 사용 할 수 없습니다.

댓글등록
SQL문을 포맷에 맞게(깔끔하게) 등록하려면 code() 버튼을 클릭하여 작성 하시면 됩니다.
로그인 사용자만 댓글을 작성 할 수 있습니다. 로그인, 회원가입