[DB] - 결합 알고리즘과 성능 (6장)

[Irisation23]

0. 결합 알고리즘과 성능

이번 정리는 결합 연산에 사용되는 알고리즘에 포커싱한다.

옵티마이저가 결합 연산의 알고리즘을 선택하며 크게 3종류이며 아래와 같다.

• Nested Loops
• Hash
• Sort Merge

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

1. Nested Loops

1.1 Nested Loops의 작동

네이밍 그대로 중첩 반복을 사용하는 알고리즘이다.
SQL에서 결합은 한 번에 두 개의 테이블만 결합하므로 본질적으로 이중 반복과 같은 의미이다.

1.2 Nested Loops의 동작 원리

1. 결합 대상 테이블에서 레코드를 하나씩 반복해가며 스캔한다.

이 테이블을 구동 테이블(driving table) 또는 외부 테이블(outer table)이라 부른다.
다른 테이블은 내부 테이블(inner table)이라 부른다.

2. 구동 테이블의 레코드 하나마다 내부 테이블의 레코드를 하나씩 스캔해서 결합 조건에 맞으면 리턴한다.
3. 구동 테이블의 모든 레코드에 반복한다.

1.3 Nested Loops의 특징

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

구동 테이블이 작을수록 Nested Loops의 성능이 좋아진다.

이중 반복의 외측과 내측의 반복 처리가 비대칭이라는 점에 주목해야한다.

1.4 구동 테이블의 중요성

위에서 말했던 구동 테이블이 작을수록 Nested Loops의 성능이 좋아진다.

왜 그럴까?

위의 말은 암묵적인 전제가 있다. 바로

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

내부 테이블의 결합 키 필드에 인덱스가 존재한다면, 해당 인덱스를 통해 DBMS는 내부 테이블을 완전히 순화하지 않아도 된다.
달리 말하면 내부 테이블의 반복을 어느 정도 건너뛸 수 있게 된다.

'구동 테이블이 작은 Nested Loops' + '내부 테이블의 결합 키에 인덱스' 라는 조합은 SQL 튜닝의 기본 중에 기본이다.

하지만 반대로 말하면 물리 ER 모델과 인덱스를 설정할 때, 어떤 테이블을 내부 테이블로 하고, 어떤 결합 키에 인덱스를 작성해야 하는지를 초기 단계 부터 고민해야 한다는 뜻이다.

1.5 Nested Loops의 단점

'구동 테이블이 작은 Nested Loops' + '내부 테이블의 결합 키에 인덱스' 조합만 있다면 성능이 충분하다고 생각할 수있다.
하지만 기대만큼 성능을 개선시키지 못할 수 있는데 그 이유는 결합 키로 내부 테이블에 접근할 때 히트되는 레코드가 너무 많을 때이다.

한개의 테이블ID에 수 많은 레코드가 히트된다면 내부 테이블에 대해 반복 횟수가 많아져 Nested Loops의 성능이 낮아진다.

이 문제에 대처하는 방법은 두 가지이다.

1. 구동 테이블로 큰 테이블을 선택하는 역설적인 방법이다. 이렇게 하면 내부 테이블에 대한 구동 테이블의 접근이 기본 키로 수행되므로, 항상 하나의 레코드로 접근하는 것이 보장된다.
2. 해시의 사용이다.

2. Hash

2.1 Hash의 작동

Hash는 입력에 대해 어느 정도 유일성과 균일성을 가진 값을 출력하는 함수를 해시라고 한다.
해시 결합은 일단 작은 테이블을 스캔하고, 결합 키에 해시 함수를 적용해서 해시값으로 변환한다.
이어서 다른 테이블(큰 테이블)을 스캔하고, 결합 키가 해시값에 존재하는지를 확인하는 방법으로 결합을 수행한다.

작은 테이블에서 해시 테이블을 만드는 이유는, 해시 테이블은 DBMS의 워킹 메모리에 저장되므로 작은 것이 효율적이기 때문이다.

2.2 Hash의 특징

Hash의 주요 특징은 다음과 같다.

• 결합 테이블로부터 해시 테이블을 만들어서 활용하므로, Nested Loops에 비해 메모리를 크게 소모한다.
• 메모리가 부족하면 저장소를 사용하므로 지연이 발생한다.
• 출력되는 해시값은 입력값의 순서를 알지 못하므로, 등치 결합에만 사용할 수 있다.

2.3 Hash가 유용한 경우

• Nested Loops에서 적절한 구동 테이블(상대적으로 충분히 작은 테이블)이 존재하지 않는 경우
• 앞서 Nested Loops의 단점에서 본 것처럼 구동 테이블로 사용할만한 작은 테이블은 있지만, 내부 테이블에서 히트되는 레코드 수가 너무 많은 경우
• Nested Loops의 내부 테이블에 인덱스가 존재하지 않는 경우

Nested Loops가 효율적으로 작동하지 않는 경우의 차선책이 Hash이다.

2.4 Hash 사용 시 주의해야 할 점

1. Nested Loops에 비해 소비하는 메모리 양이 많다.(초기 테이블을 만들어야 하기 때문)
2. 동시 실행성이 높은 OLTP(대부분의 웹 애플리케이션 웹 브라우저는 해당) Hash 사용 주의

• 해당 작업 외에 야간 배치 또는 BI/DWH 같은 시스템에서 많이 이용한다.

3. 테이블 풀 스캔이 기본 작동 방식이기 때문에 테이블 규모가 크다면, 풀 스캔 시간을 고려해야한다.

---

3. Sort Merge

3.1 Sort Merge의 작동

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

3.2 Sort Merge의 특징

• 대상 테이블을 모두 정렬해야 하므로 Nested Loops 보다 많은 메모리를 소비한다.
• Hash와 비교 시 규모에 따라 다르지만, Hash는 한쪽 테이블에 대해서만 해시 테이블을 만들므로 Hash보다 많은 메모리를 사용할 수 있다.
• 메모리 부족으로 TEMP 탈락이 발생하면 I/O 비용이 늘어나고 지연이 발생할 위험이 있다.
• Hash와 다르게 동치 결합뿐만 아니라 부등호(<, > <= , >= ) 를 사용한 결합에 사용할 수있다.
  • 주의점으로는 <> 부정 조건에서는 불가능하다.
• 테이블을 정렬하므로 한쪽 테이블을 모두 스캔한 시점에 결합을 완료할 수 있다.

3.3 Sort Merge가 유효한 경우

테이블 정렬을 생략할 수 있는 (상당히 예외적인) 경우에 고려해볼 만하지만, 그 이외에는 Nested Loops와 Hash를 우선적으로 고려해야한다.