결합 알고리즘은 결합의 성능을 결정하고 SQL 전체의 성능을 좌우하는 요인으로, 옵티마이저가 어떤 알고리즘을 선택할지 여부는 데이터 크기 또는 결합 키의 분산이라는 요인에 의존한다.
Nested Loop
Nested Loop는 중첩 반복을 사용하는 알고리즘이다.
1) Nested Loop의 작동
① outer loop: 결합 대상 테이블(구동 테이블)에서 레코드를 하나씩 반복해가며 스캔한다. ② inter loop: 구동 테이블의 레코드 마다 내부 테이블의 레코드를 하나씩 스캔해서 결합 조건에 맞으면 리턴한다. ③ 이러한 작동을 구동 테이블의 모든 레코드에 대해 반복한다.
2) Nested Loops의 특징
Nested Loops의 실행 시간은 레코드 수에 비례한다. (접근 대상 레코드 수 = R(A) x R(B))
한 번의 단계에서 처리하는 레코드 수가 적으므로 Hash 또는 Sorted Merge에 비해 메모리 소비가 적다.
모든 DBMS에서 지원한다.
구동 테이블의 레코드 수가 작을수록 성능이 좋아진다.
3) Nested Loops 실행 계획
Nested Loops의 성능을 개선하기 위해서는 내부 테이블의 반복을 얼마나 생략할 수 있을지가 포인트이다. 가령 '구동 테이블이 작은 Nested Loops 구조'에서 '내부 테이블의 결합 키 필드에 인덱스가 존재'한다면 내부 테이블의 반복이 크게 생략될 수 있다. 반대로 말하면 물리 ER 모델과 인덱스를 설정하는 초기 단계부터 어떤 테이블을 내부 테이블로 하고, 어떤 결합 키에 인덱스를 작성해야 하는지 고민해야 한다는 뜻이다.
EXPLAIN
SELECT E.EMP_ID, E.EMP_NAME, E.DEPT_ID, D.DEPT_NAME
FROM EMPLOYEES E INNER JOIN DEPARTMENTS D ON E.DEPT_ID = D.DEPT_ID;
결과
이처럼 내부 테이블인 'departments' 테이블에 대해 결합 키 인덱스인 'pk_departments'가 사용된다면 내부 테이블의 반복을 생략할 수 있어 Nested Loops 결합의 속도가 빨라진다.
가장 이상적인 것은 구동 테이블의 레코드 하나에 내부 테이블의 레코드 하나가 대응하고, 해당 레코드를 내부 테이블의 인덱스를 사용해 찾을 수 있는 경우이다. 이렇게 되면 접근 대상 레코드 수는 R(A) x 2가 된다.
※ Nested Loops의 단점
한편 결합 키가 내부 테이블에 대해 유일하지 않다면 인덱스로 내부 테이블에 접근하더라도 여러 개의 레코드가 히트될 가능성이 있다. 즉 내부 테이블의 데이터의 양이 절대적으로 많다면 그만큼 반복이 발생하여 성능이 저하될 수 있다.
이 문제에 대처하는 방법 중 하나는 구동 테이블로 큰 테이블을 선택하는 것이다. 이렇게 하면 내부 테이블에 대한 접근이 기본키로 수행되므로 항상 하나의 레코드로 접근하는 것이 보장된다. 따라서 데이터의 양에 따른 성능 비균등 문제를 해결하여 극단적으로 성능이 저하되는 것을 막을 수 있다.내부 테이블에 접근할 때 히트되는 레코드 수가 많으면 Nested Loops 성능이 저하된다
Hash
Hash는 해시 테이블을 생성하여 입력에 대해 유일성과 균일성을 가진 값을 출력하는 함수를 해시라고 한다.
1) Hash의 작동
① 스캔: 작은 테이블을 스캔한다 ② 생성: 결합 키에 해시 함수를 적용하여 해시값을 가지는 테이블을 생성한다 ③ 매칭: 큰 테이블을 스캔하고 결합 키가 해시값에 존재하는지 확인하여 결합을 수행한다
작은 테이블에서 해시 테이블을 만드는 이유는 해시 테이블이 DBMS의 워킹 메모리에 저장되므로 조금이라도 작은 것이 효율적이기 때문이다. (단 해시가 사용되는 경우는 어떤 한 쪽의 테이블이 극단적으로 작거나 크지 않다)
2) Hash의 특징
결합 테이블로부터 해시 테이블을 만들어서 활용하므로 Nested Loops에 비해 메모리를 많이 소모한다
메모리가 부족하면 디스크를 사용하므로 성능 저하가 발생한다
출력되는 해시값은 입력값의 순서를 알지 못하므로 등치 결합에만 사용할 수 있다
Nested Loops가 효율적으로 작동하지 않을 때 차선책으로 사용할 수 있다
3) Hash실행 계획
해시는 다음과 같은 상황에서 유용하다. Nested Loops에서 적절한 구동 테이블(상대적으로 충분히 작은 테이블)이 존재하지 않거나, 구동 테이블로 사용할만한 작은 테이블은 있지만 내부 테이블에서 히트되는 레코드의 수가 너무 많은 경우와 같이 Nested Loops가 효율적으로 작동하지 않을 때 해시가 사용된다.
EXPLAIN
SELECT *
FROM EMPLOYEES E INNER JOIN EMPLOYEE_TERRITORIES ET ON E.EMPLOYEE_ID = ET.EMPLOYEE_ID;
결과
※ Hash의 단점
결합 테이블로부터 해시 테이블을 만들어서 활용하므로 Nested Loops에 비해 메모리를 많이 소모한다. 따라서 동시 실행성이 높은 OLTP 처리를 할 때 해시가 사용되면 DBMS가 사용할 수 있는 메모리가 부족해져 디스크를 사용하게 되는데 결과적으로 성능 저하가 발생할 수 있다. * OLTP : OnLine Transaction Processing
또한 반드시 양쪽 테이블의 레코드를 전부 읽어야 하므로 테이블 풀 스캔이 수행되는 경우가 많고 이 때 테이블의 크기가 크다면 풀 스캔에 많은 시간이 소요된다.
Sort Merge
Sort Merge는 결합 대상 테이블들을 각각 결합 키로 정렬하고 일치하는 결합 키를 찾으면 결합하는 방식의 알고리즘이다.
1) Sort Merge의 작동
① 정렬: 결합 대상 테이블을 각각 결합 키로 정렬한다. ② 매칭: 정렬한 두 테이블 간 일치하는 결합 키를 찾으면 결합한다.
2) Sort Merge의 특징
대상 테이블을 모두 정렬해야 하므로 Nested Loops에 비해 메모리를 많이 소모한다
한 쪽 테이블에 대해서만 해시 테이블을 생성하는 hash에 비해 메모리를 많이 소모한다
동치 결합뿐만 아니라 부등호를 사용한 결합에도 사용할 수 있다. (단 <> 조건에서는 사용 불가)
※ 크로스 결합
SELECT A.col_a, B.col_b, C.col_c
FROM A_Tbl AS A
INNER JOIN B_Tbl AS B ON A.col_a = B.col_b
INNER JOIN C_Tbl AS C ON A.col_a = C.col_c
3개 이상의 테이블을 사용할 때 B_Tbl와 C_Tbl간 결합 조건이 존재하지 않을 경우 결합 조건이 없는 테이블들에 대해 크로스 결합이 수행되는 경우가 있습니다.
이는 옵티마이저가 B_Tbl와 C_Tbl 두 테이블의 크기가 충분히 작아 상대적으로 큰 테이블인 A_Tbl에 두 번 결합하는 것보다는 작은 테이블들끼리 결합함으로써 횟수를 1회로 줄이는 것이 합리적이라고 판단했기 때문입니다.
이는 거래 명세 등의 큰 트랜잭션 테이블과 고객 또는 달력 등의 작은 마스터 테이블을 결합할 때 자주 나타나는 패턴이지만 종종 크기가 큰 테이블끼리 크로스 결합이 선택되는 경우가 발생합니다. 레코드 수가 변동된 이후 옵티마이저가 이전에 저장된 정보를 바탕으로 같은 실행 계획을 선택해버리는 경우가 있기 때문입니다.
정리
결합은 여러 개의 알고리즘을 선택할 수 있기 때문에 실행 계획 변동이 일어나기 쉽다. 따라서 SQL 성능의 변동 위험을 줄이려면 가급적 결합을 피해야 한다.
결합 대상 레코드 수의 관점에서 최적의 결합 알고리즘을 선택하는 경우의 수는 다음과 같다.
1) 소규모-소규모 결합 대상 테이블이 작은 경우에는 어떤 알고리즘을 선택해도 성능 차이가 크지 않다
2) 소규모-대규모 소규모 테이블을 구동 테이블로 하는 Nested loops를 사용한다. 이 때 내부 테이블의 결합 키 필드에 인덱스가 존재해야 하며, 내부 테이블의 결합 대상 레코드 수가 너무 많다면 구동 테이블과 내부 테이블을 교체하거나 해시 사용을 고려한다.
3) 대규모-대규모 해시를 사용하되 결합 대상 테이블이 결합 키로 정렬되어 있다면 sort merge를 사용한다.
위 내용은 <SQL 레벨업 DB 성능 최적화를 위한 SQL 실전 가이드>을 참고하여 작성한 내용입니다
댓글