6장 결합
기능적 관점으로 구분하는 결합의 종류
SQL에는 결합 연산이 다음과 같이 존재합니다.
결과의 형태에 따른 구분
- 크로스 결합
- 내부 결합
- 외부 결합
등호 사용 여부에 따른 구분
- 등가 결합
- 비등가 결합
기타
- 자연 결합
- 자기 결합(필자에 의하면 굳이 결합 카테고리로 구분할 필요가 없다고 합니다.)
자연 결합은 굳이 사용하지 않아도 된다.
필자에 의하면, 자연 결합은 여러 단점이 있어 내부 결합을 사용할 것을 추천하고 있습니다.
필자가 밝힌 단점은 다음과 같습니다.
등가 결합은 짧게 쓸 수 있지만 내부 결합에 비해 엄청 짧지 않다.필드 이름이 다르거나 자료형이 다르면 적용할 수 없어 확장성이 떨어진다.결합 조건을 한번에 알기 어려워 가독성이 떨어진다.
자연 결합과 내부 결합의 중간 형태인 USING 구라는 것이 존재합니다.
결합식에서 사용하는 필드 이름을 명시적으로 나타내기 때문에 가독성이 자연 결합보다 띄어난 장점이 있습니다.
다만, 등가 표현밖에 못하는 점과 필드 이름이 다른 경우에는 사용하지 못하는 점 등의 기능적 제한으로 인해 결국 내부 결합을 추천하고 있습니다.
[크로스 결합 - 모든 결합의 모체]
크로스 결합은 실무에서는 거의 활용하지 않지만, 이를 먼저 배우면 결합이라는 연산을 이해하기 쉬워지므로 먼저 살펴보겠습니다.
크로스 결합이 어떻게 작동하는지 확인해보자
다음과 같은 사원 테이블과 부서 테이블이 존재합니다.
(각각 사원 ID와 부서 ID를 PK로 가집니다.)
Employees
emp_id(사원 ID) emp_name(사원 이름) dept_id(부서 ID)
001 | 하린 | 10 |
002 | 한마루 | 11 |
003 | 사라 | 11 |
004 | 중민 | 12 |
005 | 웅식 | 12 |
006 | 주아 | 12 |
Department
dept_id(부서 ID) dept_name(부서 이름)
10 | 총무 |
11 | 인사 |
12 | 개발 |
13 | 영업 |
위의 두 테이블을 크로스 결합하는 쿼리는 다음과 같습니다.
SELECT *
FROM Employees
CROSS JOIN Department;
쿼리를 실행하면 레코드 수가 24개가 나옵니다.
이는 크로스 결합이 수학에서 데카르트 곱이라고 불리는 연산으로, 2개 테이블의 레코드에서 가능한 모든 조합을 구하는 연산이기 때문입니다.
크로스 결합을 실무에서 사용하지 않는 이유는?
실무에서 사용하지 않는 이유는 다음 2가지입니다.
- 이러한 결과가 필요한 경우가 없다.
- 비용이 매우 많이 드는 연산이다.
실수로 사용한 크로스 결합
위에서 나온 것과 같이 크로스 결합은 피해야 하는 연산입니다.
하지만 아래 쿼리와 같이 결합 조건을 적지 않았을 때 크로스 결합이 일어나게 됩니다.
SELECT *
FROM Employee, Department;
이와 같은 실수를 막기 위해서는 ‘표준 SQL에 맞게 결합 구문을 작성’하는 것이 좋습니다.
INNER JOIN과 같은 표준 SQL 구문에서는 결합 조건이 없으면 구문 오류가 발생합니다.
따라서 DBMS가 실행을 거부하므로 실수를 미연에 방지할 수 있습니다.
[내부 결합] - 왜 ‘내부’라는 말을 사용할까?
내부 결합은 가장 많이 사용되는 조합입니다.
이를 알아보기 위해 어떻게 동작하는지 살펴보겠습니다.
내부 결합이 어떻게 작동하는지 확인해보자
위의 두 테이블을 예시로 사용하겠습니다.
사원 이름과 부서 이름을 모두 살펴보기 위해서는 두 테이블을 모두 참조해야 합니다.
다음과 같이 쿼리를 작성할 수 있습니다.
SELECT E.emp_id, E.emp_name, D.dept_id, D.dept_name
FROM Employees E INNER JOIN Department D
on E.dept_id = D.dept_id;
위 쿼리를 실행하면 크로스 결합의 쿼리의 부분 집합임을 알 수 있습니다.
이것이 내부 결합에서 ‘내부’라는 용어를 사용하는 이유입니다.
(여기서 내부는 ‘데카르트 곱의 부분 집합’이라는 의미입니다.)
내부 결합과 같은 기능을 하는 상관 서브쿼리
내부 결합은 기능적으로 상관 서브쿼리를 사용해 대체할 수 있는 경우가 많습니다.
바로 위의 쿼리를 상관 서브쿼리로 대체하면 다음과 같습니다.
SELECT E.emp_id, E.emp_name, E.dept_id,
(SELECT D.dept_name
FROM Department D
WHERE E.dept_id = D.dept_id) AS dept_name
FROM Employees E;
위 쿼리를 실행하면 같은 결과가 나옵니다.
그럼 둘 중 어떤 방법이 더 좋을까요?
기본적으로 결합을 사용하는 것이 좋습니다.
상관 서브쿼리를 스칼라 서브쿼리로 사용하면 결과 레코드 수만큼 상관 서브쿼리를 실행해 비용이 높아집니다.
(스칼라 서브쿼리: 리턴 값이 단일값인 쿼리)
[외부 결합 - 왜 ‘외부’라는 말을 사용할까?]
외부 결합이 어떻게 작동하는지 확인해보자
외부 결합은 다음과 같이 3가지 종류가 있습니다.
- 왼쪽 외부 결합
- 오른쪽 외부 결합
- 완전 외부 결합
왼쪽 외부 결합과 오른쪽 외부 결합은 실질적으로 같은 기능을 가집니다.
예시로 두 코드를 실행하면 같은 결과가 나타납니다.
-- 왼쪽 외부 결합(왼쪽 테이블이 마스터)
SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name
FROM Department D LEFT OUTER JOIN Employees E
on D.dept_id = E.dept_id;
-- 오른쪽 외부 결합(오른쪽 테이블이 마스터)
SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name
FROM Employees E RIGHT OUTER JOIN Department D
on E.dept_id = D.dept_id;
emp_id | emp_name | dept_id | dept_name |
001 | 하린 | 10 | 총무 |
002 | 한마루 | 11 | 인사 |
003 | 사라 | 11 | 인사 |
004 | 중민 | 12 | 개발 |
005 | 웅식 | 12 | 개발 |
006 | 주아 | 12 | 개발 |
NULL | NULL | 13 | 영업 |
실행 결과의 마지막 레코드를 보면 알 수 있듯이, 마스터 테이블 쪽에만 존재하는 키가 있을 경우네 해당 키를 제거하지 않고 결과를 보존합니다.
[외부 결합과 내부 결합의 차이]
외부 결합에서는 크로스 결합의 결과에 없던 레코드가 나옵니다.
이 레코드가 외부 결합에서의 ‘외부’의 의미입니다.
외부 결합은 마스터 테이블의 정보를 모두 보존하고자 NULL을 생성하지만, 크로스 결합과 내부 결합은 NULL을 생성하지 않습니다.
[자기 결합 - ‘자기’란 누구일까?]
자기 결합 연산은 자기 자신과 결합하는 연산입니다.
자기 결합을 수행하는 경우에는 같은 테이블에 다른 별칭을 붙여 다른 테이블인 것 처럼 다룹니다.
필자의 말에 따르면, 이처럼 물리적으로는 같은 테이블이지만 논리적으로 서로 다른 2개의 테이블을 결합하는 것과 같기 때문에 따로 분류는 안한다고 합니다.
결합 알고리즘과 성능
지금까지는 결합의 종류에 대해 알아봤습니다.
그렇다면 결합을 수행할 때 내부적으로는 어떻게 실행되는 걸까요?
옵티마이저는 결합을 수행할 때 다음 3가지 알고리즘 중 하나를 선택합니다.
- Nested Loops
- Hash
- Sort Merge
데이터의 크기와 결합 키의 분산을 통해 옵티마이저는 알고리즘을 선택합니다.
위의 3개의 알고리즘은 대부분의 DBMS에서 지원하지만, 제가 주로 사용하는 MySQL에서는 Nested Loops만 지원한다고 합니다.
[Nested Loops]
Nested Loops가 어떻게 작동하는지 알아보자
해당 알고리즘은 중첩 반복을 사용하는 알고리즘입니다.
이를 나타내면 다음과 같습니다.
Table_A(결합 대상 테이블) → 구동 테이블(driving table) 또는 외부 테이블(outer table)이라고 부릅니다.
Table_B → 내부 테이블(inner table)이라고 부릅니다.
위의 그림을 구체적으로 설명하면
- 결합 대상 테이블(Table_A)에서 레코드를 하나씩 반복하며 스캔합니다.
- 구동 테이블의 레코드 하나마다 내부 테이블의 레코드를 하나씩 스캔하며 결합 조건에 맞으면 리턴합니다.
- 이러한 작동을 구동 테이블의 모든 레코드에 반복합니다.
Nested Loops는 다음과 같은 특징이 존재합니다.
- Nested Loops의 실행 시간은 각 테이블의 결합 대상 레코드 수의 곱에 비례한다.실행 시간은 바로 R(A)*R(B)에 비례합니다.
- Table_A, Table_B의 결합 대상 레코드 수를 각각 R(A), R(B)라고 하면, 접근되는 레코드 수는 R(A)*R(B)가 됩니다.
- 한 번의 단계에서 처리하는 레코드 수가 적어 다른 알고리즘에 비해 메모리 소비가 적다.
- 모든 DBMS에서 지원한다.
첫 번째 특징을 보면 어떤 테이블을 구동 테이블로 사용해도 성능이 비슷한 것으로 보입니다.
(R(A)*R(B) vs R(B)*R(A))
하지만, 실제로는 어떤 테이블을 구동 테이블로 선택하는지가 성능에 중요한 요인입니다.
구동 테이블이 작을수록 Nested Loops의 성능이 좋아집니다.
구동 테이블로 어떤 테이블을 선택해야 할까?
앞에서 언급했던 것 처럼, 구동 테이블로는 작은 테이블로 선택해야 합니다.
여기서 주의해야 할 점은 이 말에 전제 조건이 존재한다는 것입니다.
내부 테이블에 결합 키 필드에 인덱스 존재
내부 테이블의 결합 키 필드에 인덱스가 존재하면, 해당 인덱스를 통해 내부 테이블을 완전히 순환하지 않아도 됩니다.
모든 레코드를 살피지 않아도 되기 때문에 성능의 개선이 있는 것입니다.
아래 코드의 경우 내부 테이블인 Department의 PK를 결합 키로 사용하고 있습니다.
(PK로 설정하면 자동으로 인덱스가 생성되므로 인덱스가 사용되는 것과 같습니다.)
SELECT E.emp_id, E.emp_name, D.dept_id, D.dept_name
FROM Employees E INNER JOIN Department D
on E.dept_id = D.dept_id;
실제 실행 계획을 보면 다음과 같습니다.
인덱스를 통해 내부 테이블을 조회하는 것을 볼 수 있습니다.
하지만 내부 테이블의 결합 키에 인덱스가 사용되지 않으면 구동 테이블이 작은 것이 아무런 장점이 되지 않습니다.
(내부 테이블을 여러 번 접근하기 때문에 데이터 버퍼에 내부 테이블을 모두 올릴 수 있으면 구동 테이블이 작은 경우가 유리할 수 있습니다.)
결합 키가 테이블 내에서 유일한지 여부에 따른 차이를 살펴보겠습니다.
결합 키에 인덱스가 적용되어 있다고 가정하겠습니다.
이 경우 결합 키가 테이블에서 유일하고 등치 결합(’=’)이라고 하면 내부 테이블의 반복을 완전히 생략할 수 있습니다.
내부 테이블의 데이터가 아무리 많아도 접근하는 레코드가 하나이므로 굉장히 효율적입니다.
MySQL에서는 위에서 살펴본 실행 계획과 같이 type에 ‘eq_ref’라고 표시됩니다.
(책에서 Oracle은 ‘INDEX UNIQUE SCAN’이라고 나온다고 합니다.)
반면, 유일하지 않은 경우는 인덱스를 통해 접근하더라도 여러 개의 레코드가 히트될 수 있습니다.
이 경우는 히트된 여러 레코드에 반복을 적용해야 합니다.
실행 계획은 MySQL에서는 type에 ‘ref’라고 나옵니다.
(Oracle은 실행 계획에 ‘INDEX RANGE SCAN’이라고 나온다고 합니다.)
조금 정리하자면, 결국 Nested Loops의 성능을 올리기 위해서는 다음 원칙을 지켜야 합니다.
구동 테이블이 작은 Nested Loops + 내부 테이블의 결합 키에 인덱스
따라서 이를 고려해 초기 단계부터 물리 ER 모델과 인덱스 설정에 주의해야 합니다.
Nested Loops의 단점에 대해 알아보자
Nested Loops의 원칙을 잘 치켜도 응답 시간이 기대한 만큼 안나올 수도 있습니다.
보통 이 경우는 결합 키로 내부 테이블을 접근할 때 히트되는 레코드가 너무 많기 때문입니다.
예를 들어 점포 테이블과 점포에서 받은 주문 테이블이 있다고 할 때, 점포에서 여러 주문을 받으므로 점포 테이블이 더 작을 것입니다.
따라서 점포 테이블을 구동 테이블로 하고 점포 ID를 결합 키로 사용하는 것이 좋아보입니다.
하지만 1개의 점포 ID에 수백만 건, 수천만 건의 레코드가 히트되면 내부 테이블의 반복 횟수가 많아져 성능이 낮아집니다.
또한, 점포에 따라 주문량의 차이가 존재할 수 있습니다.
이에 따라 주문량이 적은 점포를 처리할 때는 빠르게 처리되지만, 주문량이 많은 점포를 처리할 때는 느리게 처리될 것입니다.
SQL의 구조가 같음에도 외부의 매개변수에 따라 성능이 균등하지 않게 나옵니다.
이러한 상황을 해결하는 방법은 2가지가 있습니다.
- 구동 테이블을 큰 테이블로 선택한다.
- 다른 알고리즘을 사용한다.
첫 번째 방법은 점포에 따른 성능이 극단적으로 저하되는 것을 막을 수 있어 만약 주문 테이블의 접근 비용이 현실적이라면 효과적인 방법입니다.
[Hash]
Hash 알고리즘의 작동 방법
해시 결합은 다음과 같이 동작합니다.
- 작은 테이블을 스캔하여 결합 키를 해시 함수를 통해 해시 값으로 변환한다.
- 다른 테이블(비교적 큰 테이블)을 스캔하고 해당 테이블의 결합 키가 해시값에 존재하는지 확인한다.
작은 테이블의 결합 키로 해시 함수를 만드는 이유는 무엇일까요?
결합 키의 해시 테이블은 DBMS의 워킹 메모리에 저장되는데 이 때 조금이라도 작게 만드는 것이 효율적이기 때문입니다.
물론 Hash 알고리즘의 경우 Nested Loops 알고리즘에 비해 극단적으로 테이블의 크기가 차이나진 않습니다.
차이가 많이 나는 경우는 Nested Loops 알고리즘을 사용하면 되기 때문입니다.
Hash의 특징 및 유용한 경우
이와 같이 동작하는 Hash 함수의 주요 특징은 다음과 같습니다.
- 해시 테이블을 유지해야 하므로 Nested Loops에 비해 메모리를 크게 소모한다.
- 메모리가 부족하면 저장소를 사용함에 따라 지연이 발생한다.
- 출력되는 해시값은 입력값의 순서를 알지 못하므로, 동치 결합에만 사용할 수 있다.
위의 특징에 안좋은 점만 살펴본 것 같은데요. 유용한 경우는 언제일까요?
- Nested Loops에서 상대적으로 충분히 작은 테이블이 존재하지 않은 경우
- Nested Loops에서 상대적으로 충분히 작은 테이블이 있지만, 내부 테이블에서 히트되는 레코드 수가 많은 경우
- Nested Loops의 내부 테이블에 인덱스가 없거나 추가할 수 없는 경우
유용한 경우를 종합하면 Nested Loops를 사용하기 어려운 경우에 차선책으로 Hash를 사용한다는 의미입니다.
Hash를 사용할 때 고려해야 하는 Trade-Off가 존재합니다.
- Hash의 2번째 특징으로 인해 동시 실행성이 높은 OLTP 처리를 할 때 Hash가 사용되면 메모리가 부족해져 지연이 발생할 수 있습니다.
- 따라서 OLTP 처리를 할 때는 Hash를 지양하고, 동시 처리가 적은 야간 배치나 BI/DWH와 같은 시스템에 사용하는 것이 좋습니다.
- 양쪽 테이블의 레코드를 모두 읽어야 하므로 테이블 풀 스캔이 사용되는 경우가 많습니다.
- 따라서 테이블의 규모가 굉장히 크다면, 풀 스캔에 걸리는 시간을 고려해야 합니다.
[Sort Merge]
Sort Merge는 Nested Loops가 비효율적일 때 고려해볼 수 있는 다른 방법입니다.
결합 대상 테이블들을 각각 결합 키로 정렬하고, 일치하는 결합 키를 찾으면 결합하는 방식으로 동작합니다.
Sort Merge의 특징 및 유용한 경우
이 알고리즘의 특징은 다음과 같습니다.
- 정렬을 위해 메모리가 Nested Loops에 비해 많이 소비됩니다.
- Hash는 한쪽 테이블에 대해서만 해시 테이블을 만들면 되므로 Hash보다 많은 메모리를 사용하기도 합니다. (물론 해시 테이블이 커서 더 적게 메모리를 사용하는 경우도 있습니다.)
- Hash와 마찬가지로 메모리 부족으로 인해 디스크를 사용해 지연이 발생할 수 있습니다.
- Hash와 다르게 동치 결합뿐만 아니라 부등호(<, >, ≤, ≥)를 사용한 결합에도 사용할 수 있습니다.
- 부정조건(<>) 결합에서는 사용할 수 없습니다.
- 테이블이 결합 키로 정렬되어 있다면 정렬을 생략할 수 있습니다.
- 테이블을 정렬하므로 한쪽 테이블을 모두 스캔한 시점에서 결합을 완료할 수 있습니다.
이 알고리즘이 유용한 경우는 언제일까요?
Sort Merge는 결합 대상의 레코드 수가 많아도 나쁘지 않은 방법입니다.
하지만 테이블 정렬을 위해 많은 시간과 리소스가 필요할 가능성이 있습니다.
따라서 테이블 정렬을 생략할 수 있는 경우에만 고려해볼만 합니다.
[의도하지 않은 크로스 결합]
표준 SQL문을 통해 크로스 결합을 방지하더라도 의도치 않게 크로스 결합이 발생하는 경우가 있습니다.
삼각 결합 패턴에서 발생하는데요 예시와 함께 살펴보겠습니다.
SELECT A.col_a, B.col_b, C.col_c
FROM A
INNER JOIN B ON A.col_a = B.col_b
INNER JOIN C ON A.col_a = C.col_c;
위의 쿼리에서는 테이블 B, C 사이의 결합 조건이 존재하지 않습니다.
B와 C를 먼저 결합하고 그 결과를 A와 결합할 때 B와 C는 결합 조건이 없으므로 크로스 결합을 진행합니다.
왜 이와 같은 순서로 결합하여 크로스 결합을 발생시킬까요?
상황에 따라 다르겠지만 옵티마이저가 B와 C의 크기가 작다고 평가해 크로스 결합을 선택했을 수 있습니다.
큰 테이블(A)에 두 번 결합하는 것보다 먼저 작은 테이블들끼리 결합하고 이후 큰 테이블과 결합하는 것이 더 합리적이기 때문입니다.
위와 같은 경우가 항상 좋은 것은 아닙니다. 비교적 큰 테이블끼리 크로스 결합이 되거나 검색 조건으로 히트되는 레코드 수가 변할 때가 좋지 않은 예입니다.
두번째 경우를 더 설명하면, 일단 레코드 수를 꽤 압축할 수 있는 입력이 들어왔을 때 옵티마이저가 크로스 결합을 선택하고 이를 저장합니다.
그런데 만약 이후에 레코드 수를 압축할 수 없는 입력이 들어왔을 때도 저장된 정보를 바탕으로 크로스 결합을 선택할 수 있습니다.
의도치 않은 크로스 결합을 회피하는 방법
위와 같이 의도하지 않은 크로스 결합이 성능에 않좋은 경우가 있습니다. 이를 어떻게 회피해야 할까요?
바로 결합 조건이 존재하지 않는 테이블 사이에 불필요한 결합 조건을 추가해주는 것입니다.
(결합 조건을 설정해도 결과에 아무런 영향을 주지 않는 경우에만 사용할 수 있습니다.)
결합이 느리다면?
[상황에 따른 최적의 결합 알고리즘]
위에서 살펴본 3가지의 알고리즘의 장단점을 정리하면 다음과 같습니다.
이름 | 장점 | 단점 |
Nested Loops | - ‘작은 구동 테이블’ + ‘내부 테이블의 인덱스’라는 조건이 있으면 굉장히 빠르다. - 메모리 또는 디스크 소비가 적으므로 OLTP에 적합하다. - 비등가 결합에서도 사용 가능하다. |
- 대규모 테이블들의 결합에는 부적합하다. - 내부 테이블의 인덱스가 사용되지 않거나, 내부 테이블의 선택률이 높으면 느리다. |
Hash | - 대규모 테이블들을 결합할 때 적합하다. | - 메모리 소비량이 큰 OLTP에는 부적합하다. - 메모리 부족이 일어나면 지연이 발생한다. - 등가 결합에만 사용 가능하다. |
Sort Merge | - 대규모 테이블들을 결합할 때 적합하다. - 비등가 결합에서도 사용 가능하다. |
- 메모리 소비량이 큰 OLTP에는 부적합하다. - 메모리 부족이 일어나면 지연이 발생한다. - 데이터가 정렬되어 있지 않으면 비효율적이다. |
옵티마이저는 위의 장단점을 살펴 알고리즘을 선택하지만, 통계 정보가 오래되는 등의 이유로 항상 최적의 알고리즘을 선택하는 것은 아닙니다.
보통 레코드 수 관점에서 보면 일단 Nested Loops를 사용하고 대규모 테이블 사이의 결합에는 Hash를 고려하는 것이 책에서 추천되고 있습니다.
[실행 계획 제어]
그렇다면 위에서 추천한 대로 사용자가 실행 계획을 제어할 수 있을까요?
각 DBMS 별로 힌트 구를 통해 실행 계획을 지정할 수 있습니다.
하지만 데이터양과 카디널리티는 계속 바뀌기 때문에 항상 정답인 실행 계획은 존재하지 않습니다.
실제 이러한 변화에 대응하기 위해 비용 기반의 동적 실행 계획이 나온 것입니다.
따라서 사용자가 실행 계획을 제어할 때는 이러한 위험을 충분히 검토하고, 시스템의 미래 상황도 예측해서 적절한 실행 계획을 선택해야 합니다.
[흔들리는 실행 계획]
사용자가 실행 계획을 선택하는 경우 이외에도 옵티마이저가 최적의 실행 계획을 선택하지 못하는 경우도 있습니다.
이러한 대표적인 예로는 장기적인 운용 중에 실행 계획이 안좋은 방향으로 변화해버리는 것이 있습니다.
데이터양의 증가 등으로 통계 정보가 변했을 때, 일정한 역치를 넘으면 옵티마이저가 실행 계획을 변화시키면서 문제가 발생합니다.
이는 사전에 예측하기가 어렵고 돌발적인 지연을 가져오므로 매우 골치 아픈 문제입니다.
이런 상황은 우리가 앞에서 계속 살펴본 결합에서 쉽게 일어납니다.
결합은 여러 개의 알고리즘을 선택할 수 있으므로 알고리즘이 변함에 따라 성능이 변하는 것입니다.
결론적으로는 SQL 성능의 변동 위험을 줄이려면 되도록 결합을 피해야 합니다.
궁금한 점
책에서 소개한 대로 MySQL 8버전에도 Nested Loops만 지원할까?
MySQL :: MySQL 8.0 Reference Manual :: 8.2.1.4 Hash Join Optimization
8.2.1.4 Hash Join Optimization By default, MySQL (8.0.18 and later) employs hash joins whenever possible. It is possible to control whether hash joins are employed using one of the BNL and NO_BNL optimizer hints, or by setting block_nested_loop=on or bloc
dev.mysql.com