SQL 레벨업 - 6장 결합 (2/3)

2018-12-03

19강 결합 알고리즘과 성능

SQL에서 결합 연산을 수행할 대 내부적으로 선택되는 알고리즘은 크게 3가지가 있다.

  1. Nested Loops
  2. Hash
  3. Sort Merge

옵티마이저가 어떤 알고리즘을 선택할지는 데이터 크기 또는 결합 키의 분산이라는 요인에 의존한다.

세가지 알고리즘은 대부분의 DBMS가 지원하지만, MySQL은 Nested Loops 와 그 파생 버전만 지원하고 Hash 또는 Sort Merge를 지원하지 않는다.

1. Nested Loop

  • Nested Loops의 작동

SQL에서 결합은 한 번에 두 개의 테이블만 결합하므로 본질적으로는 이중 반복과 같은 의미이다.

  • Nested Loops의 특징
    1. Table_A, Table_B 의 결합 대상 레코드를 R(A), R(B)라고 하면 접근하는 레코드 수는 R(A) * R(B) 가 된다. 그러므로 실행 시간은 레코드 수에 비례하게 된다.
    2. 한 번의 단계에서 처리하는 레코드 수가 적으므로 Hash 또는 Sort Merge에 비해 메모리 소비가 적다.
    3. 모든 DBMS에서 지원한다.

구동 테이블이 작을수록 Nested Loops의 성능은 좋아진다. 중요한점은 이중 반복의 외측가 내측의 반복 처리가 비대칭이라는 점이다.

  • 구동 테이블의 중요성

구동 테이블이 어떤 테이블이 되더라도 결과적으로 접근하는 레코드 수는 R(A) * R(B) 가 된다. 구동 테이블이 작건 크건 결합 비용에는 차이가 없어 보이지만, ‘구동 테이블을 작게’라는 격언에는 암뭊겅니 전제가 포함된다.

내부 테이블의 결합 키 필드에 인덱스가 존재

내부 테이블의 결합 키 필드에 인덱스가 존재한다면, 해당 인덱스를 통해 DBMS는 내부 테이블을 완전히 순환하지 않아도 된다.

다시 말하면 내부 테이블의 반복을 어느정도 건너 뛸 수 있다.

-- 내부 테이블의 결합 키 인덱스 사용(department_pkey, PK_DEP)
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;

-- 내부 테이블 인덱스가 사용되는 Nested Loops
Nested Loop(cost= ~)
	-> Seq Scan on employees e
	-> Index Scan using departments_pkey on departments d
		Index Cond:(dept_id = e.dept_id)

-- 내부 테이블의 인덱스가 사용되지 않은 Nested Loops
Nested Loop(cost ~)
	Join Filter: (e.dept_id = d.dept_id)
		-> Seq Scan on departments d (cost ~)
		-> Materialize (cost ~)
			-> Seq Scan on employees e (cst ~)

‘구동 테이블이 작은 Nested Loop’ + ‘내부 테이블의 결합 키에 인덱스’ 라는 조합은 SQL 튜닝의 기본이다. 결합이 느리다면 절반 정도는 이런 조합으로 개선이 가능하다. 반대로 물리 ER 모델과 인덱스를 설정할때, 어떤 테이블을 내부 테이블로하고, 어떤 결합 키에 인덱스를 작성해야 하는지를 초기 단계부터 고민해야 한다.

  • Nested Loops 의 단점

여러가지 방법으로 인덱스를 사용해 반복을 생략할 수 있다 해도, 결국 절대적인 양이 너무 많으면 반복이 많이 일어나게 된다. 즉, 지연이 일어나게 된다.

예를 들면 쇼핑몰 리스트 테이블과 상품 테이블이 있다고 가정하자. 당연하게 더 작은 테이블인 쇼핑몰 리스트 테이블을 구동 테이블로 정해도 결국 데이터가 많으면 느려지게 된다.

이 문제에 대처하는 방법은 두 가지다. 첫 번째는 구동 테이블로 큰 테이블을 선택하는 역설적인 방법이다. 이 방법은 내부 테이블에 대한 상품 리스트 테이블의 접근이 기본 키 (쇼핑몰 ID)로 수행되므로, 항상 하나의 레코드로 접근하는 것이 보장된다. 따라서 쇼핑몰에 따른 성능 비균등 문제를 해결해서, 극단적 성능 저하 문제를 막을 수 있다.

두 번째 해결 방법은 Hash를 사용하는 것이다.

2. Hash

  • Hash 의 작동

해시 결합은 작은 테이블을 스캔하고, 결합 키에 해시 함수를 적용해서 해시값으로 변환한다. 이어서 큰 테이블을 스캔하고, 결합 키가 해시값에 존재 하는지를 확인하는 방법으로 결합을 수행한다. 작은 테이블에서 해시 테이블을 만드는 이유는 , 해시 테이블은 DBMS의 워킹 메모리에 저장되므로 조금이라도 작은 것이 효율적이기 때문이다.

  • Hash 의 특징
    1. 결합 테이블로부터 해시 테이블을 만들어서 활용하므로, Nested Loops에 비해 메모리를 크게 소모한다.
    2. 메모리가 부족하면 저장소를 사용하므로 지연이 발생한다.
    3. 출력되는 해시값은 입력값의 순서를 알지 못하므로, 등치 결합에만 사용할 수 있다.
  • Hash 가 유용한 경우
    1. Nested Loops에서 적절한 구동 테이블이 존재하지 않는 경우
    2. 구동 테이블로 사용할만한 작은 테이블은 있지만, 내부 테이블에서 히트되는 레코드가 너무 많은 경우
    3. Nested Loop 내부 테이블에 인덱스가 존재하지 않는(또는 추가할 수 없는) 경우

즉, Nested Loops가 효율적으로 작동하지 않는경우 Hash가 차선책으로 유용하다.

  • Hash를 사용할때 고려해야하는 트레이드오프

초기에 해시 테이블을 만들어야 하므로, Nested Loops에 비해 메모리를 많이 사용한다. 그리고 Hash 결합은 반드시 양쪽 테이블의 레코드를 전부 읽어야 하므로, 테이블 풀 스캔이 사용되는 경우가 많다. 풀 스캔에 걸리는 시간도 고려 해야한다.

3. Sort Merge

  • Sort Merge 의 작동

Nested Loops가 비효율적인 경우, Hash 외에 다른 선택지로 Sort Merge가 존재한다. 간단하게 Merge 또는 Merge Join으로 불린다.

Sort Merge는 결합 대상 테이블들을 각각 결합 키로 정렬하고, 일치하는 결합 키를 찾으면 결합한다.

  • Sort Merge 의 특징
    1. 대상 테이블을 모두 정렬해야 하므로 Nested Loops보다 많은 메모리를 소비한다. 메모리 부족으로 TEMP 탈락이 발생하게 되면 I/O 비용이 늘어나고 지연 발생 위험이 있다.(Hash와 마찬가지)
    2. Hash와 다르게 동치 결합뿐만 아니라 부등호를 사용한 결합에도 사용 가능하다. (부정 조건은 안됨)
    3. 원리적으로 테이블이 결합 키로 정렬되어 있다면 정렬을 생략 가능하다.
    4. 테이블을 정렬하므로 한쪽 테이블을 모두 스캔한 지점에 결합을 완료할 수 있다.
  • Sort Merge 가 유효한 경우

Sort Merge 결합 자체에 걸리는 시간은 결합 대상 레코드 수가 많더라도 나쁘지 않은 편이지만, 테이블 정렬에 많은 시간과 리소스를 요구할 가능성이 있다. 따라서 테이블 정렬을 생략할 수 있는 경우에 고려해볼만 하다. ( 고려하지마라 정렬 생략 불가능하다. )

4. 의도하지 않은 크로스 결합

의도하지 않게 크로스 결합이 나타나는 경우가 있다. ‘삼각 결합’이라 부르는 패턴이다.

SELECT A.col_a, B.col_b, C.col_c
	FROM Table_A A
    	INNER JOIN Table_B B
    		ON A.col_a = B.col_b
    	INNER JOIN Table_C C
    		ON A.col_a = C.col_c;

이 쿼리는 Table_A, Table_B, Table_C 3개의 테이블을 결합한다. 결합 조건은 ‘Table_A - Table_B’ 과 ‘Table_A - Table_C’ 에만 존재한다. ‘Table_B - Table_C’ 에는 결합 조건이 존재하지 않는다는 점이 포인트!

이런 경우 4가지 형태의 실행 계획이 나올 수 있다.

  • Table_A를 구동 테이블로 Table_B와 결합하고 그 결과를 Table_C 와 결합
  • Table_A를 구동 테이블로 Table_C와 결합하고 그 결과를 Table_B 와 결합
  • Table_B를 구동 테이블로 Table_A와 결합하고 그 결과를 Table_C 와 결합
  • Table_C를 구동 테이블로 Table_A와 결합하고 그 결과를 Table_B 와 결합

Nested Loops가 선택되는 경우 특별히 문제 될게 없지만 크로스 결합이 선택되는 경우가 있다.

회피하기 위해서는 결합 조건이 존재하지 않는 테이블 사이에 불필요한 결합 조건을 추가해주는 방법이 있다.