들어가며

SQL 성능 튜닝을 이야기할 때 빠질 수 없는 주제가 바로 조인과 조인 알고리즘이다. 대부분의 실무 쿼리는 하나 이상의 테이블을 조합하여 원하는 데이터를 추출하며, 이 과정에서 어떤 방식으로 조인이 수행되는지가 전체 성능에 큰 영향을 미친다. 이 글에서는 조인의 기본 개념부터, 이를 실제로 수행하는 다양한 조인 알고리즘들의 동작 원리와 각각의 장단점을 살펴보려고 한다.

조인

조인에는 여러 연산들이 있음. 그 중에서도 기능적으로 분류하자면, 크로스 조인, 내부 조인, 외부 조인으로 크게 나누어볼 수 있음. 하나씩 조인들 종류에 대해서 알아본다.

크로스 조인 (CROSS JOIN)

크로스 조인은 잘 사용되진 않지만, 조인을 이해하는데 가장 기본이 되는 조인. 사실 크로스 조인은 두 테이블의 곱을 의미함. 사원 테이블에 행이 2개 있고, 부서 테이블에 행이 2개가 있다면, 두 테이블을 크로스 조인 후 나오는 결과 행의 수는 2 * 2 = 4개가 됨. 수학에서 데카르트 곱이라고 불리는 연산에 해당된다. 2 테이블에서 가능한 모든 조합을 구하는 연산인 셈.

A = {a1, a2}, B = {b1, b2}

(a1, b1)
(a1, b2)
(a2, b1)
(a2, b2)

사실 크로스 조인은 이런 모든 조합을 구하는 결과가 필요한 경우가 잘 없기도하고, 조인 연산의 비용이 매우 큰 연산이기 때문에 잘 사용되지 않는다. 결합 조건을 따로 설정하지 않는 경우, DBMS는 테이블의 모든 조합을 만드므로 테이블별로 결합 조건을 잘 명시하는게 중요하다.

SELECT *  
FROM Employees, Departments; # 결합 조건 누락

SELECT *  
FROM Employees  
INNER JOIN Departments; # 결합 조건 누락

내부 조인 (INNER JOIN)

내부 조인은 가장 많이 사용되는 조인. 내부라는 이름이 붙은 이유는 ‘크로스 조인의 부분집합’이라는 의미로 쓰인다고 한다. 물론 성능 상의 문제로 크로스 결합을 수행한 후 결합조건으로 필터링을 하지는 않는다. 실제로는 결합 대상을 최대한 축소하는 방향으로 구현된다고 함.

A = {a1, a2}, B = {b1, b2}

(a1, b1)
(a1, b2) // 내부 조인 결과
(a2, b1)
(a2, b2) // 내부 조인 결과

내 부조인으로 나올 수 있는 결과들은 크로스 조인으로 발생하는 모든 조합 안에서 나올 수 있으므로 크로스 조인의 부분집합이라고 불릴 수 있다.

내부조인은 다음과 같이 결합 조건을 ON절로 표현할 수 있다.

SELECT e.emp_id, e.emp_name, e.dept_id, d.dep_name  
FROM Employees e  
         INNER JOIN Departments d  
                    ON e.dept_id = d.dep_id;

내부 조인은 상관관계 서브쿼리를 통해 동일한 결과를 내는 경우가 많음. 상관관계 서브쿼리(correlated subquery)란 “상위 쿼리(바깥 쿼리)의 컬럼을 서브쿼리(안쪽 쿼리)에서 참조하는 서브쿼리” 를 말한다. 상위쿼리의 행마다 다르게 실행되는 쿼리가 된다.

SELECT E.emp_id,  
       E.emp_name,  
       E.dept_id,  
       (SELECT D.dep_name  
        FROM Departments D  
        WHERE E.dept_id = D.dept_id) AS dep_name  
FROM Employees E;

위 쿼리는 앞서 내부 조인을 사용한 쿼리 결과와 동일하다. 이 쿼리가 내부 조인 쿼리와 같을 수 있는 이유는 논리적으로 같은 결과를 얻을 수 있기 때문이다. 위에서는 상관관계 서브쿼리의 결과값이 단 하나인 스칼라 서브쿼리로(Department의 기본키를 조건으로 사용 중) 동작하고, 논리적으로 동일한 비교를 수행하고 있기 때문이다.

만일 같은 결과를 낼 수 있을때는 내부 조인을 사용하는 것이 성능상의 이점이 있음. 상관관계 서브 쿼리는 상위 쿼리의 수만큼 서브쿼리가 실행되기 때문에 비용이 높기 때문이다.

외부조인(OUTER JOIN)

외부조인은 내부 조인처럼 ‘크로스 조인의 부분집합’ 임이 성립하지 않는다. 외부 조인의 결과는 크로스 조인으로 나올 수 있는 조합이 없을 수도 있기 때문이다.

A = {a1, a2}, B = {b1, b2}

(a1, b1)
(a1, NULL) // A 단독 행. 크로스 조인에 없는 결과.

외부조인은 방식에 따라 총 3가지 종류로 나뉨.

  • 왼쪽 내부 조인 (오른쪽과 동일)
  • 오른쪽 외부 조인 (왼쪽과 동일)
  • 완전 외부 조인

사실 이 중에서 왼쪽/오론쪽 외부 조인은 같은 역할을 하고, 마스터(조인 기준)가 되는 테이블의 위치에 따라서 부르는 방법의 차이가 있을 뿐이다. 마스터 테이블을 기준으로 행들이 조인되며, 결합조건에 맞는 행이 없더라도 마스터 행의 정보들은 결과로 보존되는 것이 외부 조인이다. 마스터 테이블의 행이 모두 보존되어야하므로, 결합조건에 맞지 않는 상대 테이블의 컬럼들은 NULL 로 표시되는 것이다.

자연 조인 (NATURAL JOIN)

이외에도 자연 조인 (NATURAL JOIN)이 있음. 자연 조인은 표준 SQL에 있지만, 사실 내부조인과 다르지 않음. 조인하는 조건을 별도로 기술하지 않고, 암묵적으로(ON없이 자동으로 조인 조건) 같은 이름의 필드끼리 등호로 결합됨.

SELECT *
FROM Employee
NATURAL JOIN Departments;

편리할 것 같지만, 명시적으로 조인 조건을 설정하는 것이 좋음. 그 이유는 편리하다고 쓰긴했지만, 조인 조건을 쓰는 것이 그리 양이 많지도 않아 그다지 번거롭지 않고(장점이 그리 크지 않음), 가독성이 많이 떨어지는 구문이기 때문이다. 그리고 의도하지 않은 동일 필드끼리 조인될 수 있기 때문에 예상치 못한 결과가 나올 수도 있기 때문. 이를 조금 더 가독성이 높게 작성하려면 USING 구를 이용하면 됨.

SELECT *
FROM Employees INNER JOIN Departments
	USING(dept_id);

하지만, 이는 등가 조건만 표현(=)만 가능하고 테이블의 필드 이름이 같을때만 사용이 가능하다. 확장성이 높지는 않다.

자연조인은 얼마든지 내부조인으로 기술이 가능하니, 최대한 명시적으로 작성해주는 것이 좋음.

SELECT * 
FROM Employee E INNER JOIN Department D
	ON E.dept_id = D.dept_id;

조인 알고리즘.

SQL에서 조인 연산이 수행될때 내부적으로 선택되는 알고리즘들을 알아봄.

옵티마이저가 선택 가능한 조인 알고리즘은 크게 3가지가 존재함.

  • Nested Loop Join
  • Hash Join
  • Sort Merge Join

이 중에서 조인 연산이 어떤 알고리즘을 택할 것인지는 데이터의 크기나, 통계, 인덱스, 조인 조건 키의 분산 등 요인들에 따라 달라진다고 함. 이 중에서는 Nested Loop Join 알고리즘이 조인 알고리즘 중 가장 기본이 되는 알고리즘이며, MySQL의 경우에는 Nested Loop Join 알고리즘 혹은 이를 변형한 알고리즘을 사용한다고 함.

Nested Loop Join

이름 그대로 중첩 반복을 사용하는 알고리즘을 의미함. 이중 반복문을 연상하면 된다. 이 알고리즘은 매우 단순하지만, 많이 사용되는 알고리즘이고, 조인 성능에서 중요한 역할을 하는 알고리즘이다.

SELECT *
FROM employees e
JOIN departments d ON e.dept_id = d.id;

두 개의 테이블을 조인하는 상황에서 동작 방식은 다음과 같음.

  1. Employees 에서 레코드를 하나씩 스캔해나감.
  2. Employees의 레코드 하나하나 마다 Departments의 레코드를 하나씩 확인하며 결합조건에 맞는지 확인.
  3. 만약 결합 조건에 해당된다면 (e.dept_id = d.id) 이를 반환한다.
  4. 위 동작(1~3)를 Employees 테이블의 모든 레코드에 반복함.

이때 결합 대상이 되는 Employees 테이블을 구동 테이블 혹은 외부 테이블이라고 부름. (driving table, outer table) 이에 대응되는 Departments 테이블을 내부 테이블이라고 부름 (inner table)

사실 중첩-방복 조인 알고리즘은 동작방식이 그리 복잡하지는 않음. Employees, Departments 테이블의 결합 대상 레코드를 각각 R(E), R(D)라고 할때, 중첩-반복 조인 알고리즘의 실행을 위해 접근하는 레코드의 수는 R(E) * R(B)가 됨. 즉, 중첩-반복 조인 알고리즘의 수행 시간은 각 테이블의 레코드 수의 곱과 비례함.

여기서 한 가지 주의해야할 것은 어떤 테이블이 구동 테이블로 선택하는지에 따라서 성능에 차이가 발생함. 구동 테이블이 작을수록(검색 조건으로 압축된 레코드의 수가) Nested Loops의 성능이 좋아짐.

🤔 그런데 아까 두 테이블의 레코드 수의 곱만큼 수행시간이 걸린다고 했는데, 그러면 어떤 테이블이 구동 테이블이 되든 상관 없는 것 아닌가? 왜 성능 차이가 나는거지?

결론부터 말하자먼, 외부 테이블과 내부 테이블의 반복처리가 비대칭적일 수 있기 때문이다.

내부 테이블의 조인 조건 키에 인덱스가 존재할 때,

SELECT *
FROM employees e
JOIN departments d ON e.dept_id = d.id;

즉, Departments의 id에 인덱스가 걸려있을때를 의미한다. 조인을 수행할때, 인덱스를 통해 내부 테이블(Departments)의 레코드를 전부 탐색하지 않을 수 있게 된다. 즉, 조인을 수행할 때 내부 테이블(Departments)의 접근을 어느정도 뛰어넘을 수 있다는 의미이다.

극단적인 예시로, 드라이빙 테이블 레코드에 대응되는 레코드가 내부 테이블에 유일(단 한개 존재)하고, 이를 내부 테이블의 인덱스를 통해 찾을 수 있는 경우에는 내부 테이블을 모두 탐색하지 않아도 된다. 이 경우 R(E) * 2 만큼만 접근하면 된다.

정리하면, 내부 테이블을 풀 스캔이 아닌, 인덱스를 통해 접근을 최소화한다면, 앞선 R(E) * R(D) 만큼 수행되지 않을 수 있다는 의미이다.

쿼리 분석의 결과 드라이빙 테이블(Employees)의 경우 전체 반복 1회에 내부 테이블(Departments) 의 경우 PK를 사용해 커버링 인덱스로 단 한개의 레코드에만 접근한 것을 알 수 있다.

-> Nested loop inner join  (cost=2.95 rows=6) (actual time=0.139..0.15 rows=6 loops=1)  
    -> Filter: (E.dept_id is not null)  (cost=0.85 rows=6) (actual time=0.102..0.107 rows=6 loops=1)  
        -> Table scan on E  (cost=0.85 rows=6) (actual time=0.101..0.105 rows=6 loops=1)  
    -> Single-row covering index lookup on D using PRIMARY (dep_id=E.dept_id)  (cost=0.267 rows=1) (actual time=0.00251..0.00255 rows=1 loops=6)

즉, 내부 테이블이 몇천건이 있다고 하더라도, 단 하나의 레코드에만 접근하면 된다는 의미이다. 단, 이러한 경우는 앞서 말했던 것처럼 내부 테이블의 조인 조건 키(여기선 id)가 유일하고 인덱스를 통해 빠르게 찾을 수 있는 경우에만 내부 반복의 생략이 가능하다.

(그림, 내부 테이블의 반복을 얼마나 생략 가능?)

만일 조인 조건 키가 내부 테이블에서 유일하지 않은 경우라면, 여러 개의 레코드가 내부 테이블에서 탐색될 수 있기 때문에 인덱스가 존재하더라도 내부 반복은 발생한다.

결론은 인덱스를 통해, 내부 테이블의 탐색 범위가 매우 작아질 수 있다는 게 핵심이다.

그렇기 때문에 “크기가 작은 구동테이블” & “내부 테이블의 조인조건 키에 인덱스” 의 조합이 조인 튜닝의 기본이 된다. 이러한 내부 동작 원리를 알면 어떤 테이블을 내부 테이블로 사용할 것이며, 어떤 조인 조건 키에 인덱스를 사용할지 고민해볼 수 있음.

단점.

그럼에도 내부 테이블의 탐색 범위가 압도적으로 많다면 (인덱스 적용에도) 성능이 안좋을 수 있음.

내부 테이블의 선택률이 높은 경우가 그 예시. 조인 조건에 해당되는 내부 테이블 레코드가 많은 경우를 의미한다. 거의 풀스캔과 다를 바가 없는 경우 SQL의 구조가 같지만, 외부의 파라미터에 따라 성능이 천차 만별이 될 수 있다. 최종적으로 SQL의 성능은 처리하는 양에 의존하기 때문임.

이를 해결하는 방법은 2가지가 있음.

드라이빙 테이블을 큰 테이블로 변경하는 방법이 있다. 역설적이지만, 오히려 내부 테이블의 선택률이 줄어들어 성능이 향상될 가능성이 있다. 하지만 이 역시도, 드라이빙 테이블의 탐색범위가 현실적이어야 한다.

두번째로는 해시 조인 알고리즘을 사용하는 방식이 존재한다.

Hash Join

해시 조인은 해시 함수를 사용하는 조인 알고리즘이다. 해시 조인 알고리즘은 조인 조건 키에 해시 함수를 적용해서, 별도의 해시 테이블을 만들어 매칭하는 방식으로 조인을 수행한다.

SELECT *
FROM employees e
	JOIN departments d 
		ON e.dept_id = d.id;

마찬가지로 위의 두 테이블을 조인하는 상황에서 동작방식은 다음과 같음. 크게 Build Phase와 Probe Phase로 나뉜다.

(그림. 해시조인 단계)

  1. Build Phase에서는 해시 테이블을 만들 테이블을 선정하고 해시 테이블을 만든다.
    1. 이때 해시 테이블로 지정되는 테이블을 build input이 된다. 테이블의 크기가 작은 테이블을 build input으로 선정한다. 그 이유는 해시 테이블이 DBMS의 워킹 메모리에 저장되는데, 이때 작을수록 효율적이기 때문이다.
  2. 만일 departments가 작다고 판단되면 이 테이블의 조인 조건(dep_id)을 기준으로 해시 테이블을 생성함.
  3. Probe Phash에서는 employees를 순회하며 e.dept_id를 해시 키로 활용해 해시테이블에서 빠르게 매칭한다.
  4. 매칭이 완료된 레코드를 결합해서 최종 결과 세트를 생성한다.

🤔 왜 해시 조인이 중첩-반복 조인 알고리즘이 해결하지 못한 테이터 양 문제를 해결할 수 있을까?

그 이유는 데이터 매칭에 걸리는 시간이 O(1)로 접근이 가능하기 때문이다. 이는 해시 방식의 가장 큰 장점을 활용한 것이다. 따라서 Probe Phase에서 매칭하는 과정에서는 Probe Input 테이블을 한번씩만 탐색하면 된다. 결과적으로 조인에 필요한 접근 레코드 수는 R(E) + R(D) 만큼이 된다. 앞서 (인덱스가 없는 경우) 중첩-반복 조인 알고리즘인 R(E) * R(D)에 비하면 같은 크기의 테이블 수에서는 빠른 조인 속도를 보장해준다는 것을 알 수 있다.

이러한 성능 향상 덕분인지, 꽤나 최근(?)인 MySQL 8.0.18 버전부터는 옵티마이저가 Hash Join 알고리즘을 선택할 수 있도록 지원한다고 한다. 이전까지 MySQL에서는 중첩-반복 조인 알고리즘과 그 파생 알고리즘이 유일했다. 현재는 옵티마이저가 선택할 수 있는 조건들이 제한적으로 동작하는 듯하다.

다음은 MySQL 블로그 아카이브 글 ‘Hash Join in MySQL 8’ 내용의 일부이다. 해시 조인과 중첩-반복 조인 알고리즘 방식의 벤치마크 수행 결과이며 대부분의 쿼리에서 압도적인 성능 향상을 보이는 것을 확인했다고 한다.

언제 Hash Join 알고리즘이 필요할까?

앞서 살펴본 동작방식과 특징으로 인해 Hash Join은 주로 대규모 데이터를 조인하는 상황에서 빛을 본다.

조금 더 구체적인 상황으로는 중첩-반복 조인 알고리즘 방식에서 내부테이블에 사용할 인덱스가 없거나, 사용하지 못하는 경우 Hash Join 알고리즘이 유용할 수 있다.

단점

모든 기술이 그렇듯 Hash Join 알고리즘도 단점이 존재한다.

첫번째는 해시 테이블을 생성하기 때문에 Nested-Loop 조인 방식보다 메모리를 많이 사용한다는 점이다. 이때 추가적으로 발생할 수 있는 성능 문제는 Spill이 발생하는 순간이다. 생성하려는 해시 테이블의 크기가 해시 테이블이 임시 저장되는 워킹 메모리의 크기보다 훨씬 큰 경우 디스크 공간을 임시공간으로 같이 사용하게 되는데 이를 Spill이 발생한다고 한다. 이 경우에 추가적인 디스크 I/O 발생으로 성능 저하가 발생할 수 있다고 한다.

또한 내부 동작방식이 해시 값이 일치하는지를 찾는 방식으로 이루어지다보니 등치 결합(=)에만 사용이 될 수 있다는 제약점이 존재한다.

Build Input으로 사용되는 테이블의 조인 키의 카니널리티(유일성)이 낮은 경우에 성능 문제가 발생할 수 있다.

조인 알고리즘 정리

앞에서 살펴본 중첩-반복 조인, 해시 조인 알고리즘외에도 여러 알고리즘이 있지만 본 글에서는 두 알고리즘만 간단하게 살펴봤다. 두 알고리즘을 정리해보면 다음과 같다.

조인 알고리즘 장점 단점
Nested Loop Join - 작은 드라이빙 테이블 + 내부 테이블 인덱스 조합의 경우 속도가 빠름.
- 메모리 사용량이 크지 않아 OLTP 에 적합.		 - 대규모 테이블의 조인에는 그리 적합하지 않음.
- 내부테이블의 인덱스를 사용할 수 없는 경우 & 선택률이 높은 경우 느림.
Hash Join - 대규모 데이터이면서 인덱스를 사용할 수 없는 경우 유용 - 메모리 소비가 많음.
- 메모리 부족 현상이 발생할 경우 성능 저하가 있음.

조인 알고리즘을 선택하는 것은 주로 옵티마이저가 테이블의 통계정보, 조건들을 살피면서 위 알고리즘들을 선택한다. 하지만 옵티마이저가 항상 완벽한 선택을 하는 것이 아니기 때문에 항상 최적 튜닝의 여지가 존재하는 듯하다.

조인 실행계획

그러면 사용자가 직접 실행계획을 지정할 수 있을까? 원칙적으로는 옵티마이저가 이를 선택하도록 되어있지만, 힌트 정보를 활용해서 옵티마이저에게 원하는 알고리즘을 선택하게 할 수 있다.

하지만, 실행 계획을 사용자가 제어할때 발생할 수 있는 위험성들도 존재한다. 데이터베이스의 테이블에 대한 정보는 항상 변경된다. 데이터가 추가되고 삭제되고 수정될때마다, 테이블이 가지고 있는 통계정보도 달라지고 그에 따라 최적인 쿼리 실행 전략이 시시각각 변화한다. 이러한 이유로 데이터 상황에 맞게 판단할 수 있도록 대부분의 DBMS는 비용기반의 옵티마이저를 사용하고 있다. 통계 기반으로 실행 비용이 가장 적은(빠른) 실행 계획을 선택할 수 있도록 설계되었다.

그렇기 때문에 사용자가 실행계획을 직접 제어(고정)하는 방식은 어쩌면 이러한 설계 원칙에는 조금 반하는 것일 수도 있다. 이전에는 적절했던 계획이 데이터 변경에 따른 이후 시점에서는 좋지않은 결과를 낼 수도 있기 때문이다. 추가로 실행 계획 제어를 위한 관리 비용이 늘어날 수도 있는 선택지가 될 수 있다. 따라서 사용자도 이런 단점을 인지하고 성능 테스트를 통해 장단점을 고려해봐야한다.

또 잘 실행되던 쿼리가 시간의 경과에 따라 슬로쿼리를 급작스럽게 발생시킬 수도 있는데, 이는 옵티마이저가 테이블의 통계정보의 변화를 감지해 실행계획을 최적화 판단에 따라 실행 계획을 변경했을 때 발생할 수 있다. 특히 조인은 실행 계획에서 다양한 알고리즘(NL, Merge, Hash 등) 중 선택되므로 변동 가능성이 높다.

마무리하며

SQL의 조인, 그리고 다양한 조인 알고리즘의 동작 방식과 장단점을 살펴보았다. 이를 정리하며 느낀 것은, DBMS의 쿼리 성능 튜닝은 결국 옵티마이저의 한계에서 비롯된다는 점이다. 따라서 매 상황에서 최적의 실행 계획을 판단/유도하기 위해서는, DBMS 내부 동작 원리에 대한 일정 수준의 이해가 필수적임을 다시금 깨달았다.