[DB] (2) 조인 알고리즘과 수행 과정

다양한 조인 알고리즘

SQL에서 조인을 수행할 때 다양한 알고리즘이 사용된다. 각각의 알고리즘은 데이터의 양, 인덱스 존재 여부, 조인 조건 등에 따라 성능이 다르게 나타날 수 있다. 지금까지는 조인 알고리즘을 선택하고 사용하지 않았는데, 과연 어떻게 알고리즘을 선택하게 되는 것일까?

그것은 쿼리를 실행할 때, 데이터베이스 관리 시스템(DBMS)이 내부적으로 선택하고 적용하는 방식을 활용하기 때문이다. 덕분에 사용자는 쿼리를 작성할 때, 조인 알고리즘을 직접 선택하지 않아도, 쿼리의 작성 방식이나 인덱스, 데이터 구조 등에 따라 자동적으로 DBMS가 최적의 알고리즘을 선택해준다.

DBMS는 대표적으로 세 가지 조인 알고리즘을 사용한다.

1. Nested Loop Join(NL Join)
2. Sort Merge Join
3. Hash Join

이번 글에서는 대표적인 세 가지 조인 알고리즘의 개념과 특징을 살펴본 후, 이들 간의 차이점에 대해 알아보고자 한다.

Nested Loop Join(NL Join)

Nested Loop Join은 선행 테이블(Driving Table)의 데이터를 하나씩 엑세스하면서, 각 값을 후행 테이블(Lookup Table)과 조인하는 방식을 사용한다.

조인을 수행하는 과정은 아래 그림으로 설명할 수 있다.

Nested Loop Join 수행방식

순서	수행방식	설명
1	선행 테이블 엑세스	선행 테이블에서 첫 번째 데이터를 엑세스
2	후행 테이블 엑세스	선행 테이블에서 엑세스한 값이 후행 테이블(인덱스)에 존재하는지 확인
3	데이터 추출	후행 테이블에 조인 키가 존재하면 해당 행을 추출

이 과정에서, Nested Loop Join은 세 가지 특징을 볼 수 있다.

1. 랜덤 엑세스 방식
   데이터가 후행 테이블에 존재하는지 확인하는 과정이 랜덤 엑세스 방식이기 때문에, 대량의 데이터를 조인할 때 비효율적이라는 특징을 가진다.
2. 부분 범위 처리
   1번과 같은 특징 때문에, 부분 범위처리가 가능한 상황에서 응답 속도가 조금 개선된다. 따라서, 작은 테이블이나 적은 데이터셋에서 성능이 뛰어나다.
3. 인덱스 구성
   조인하는 테이블의 조인 조건에 인덱스가 설정되어 있다면, 내부적으로 DBMS는 이 방식을 선택할 가능성이 높다.

Sort Merge Join

Sort Merge Join은 두 테이블을 조인하는 컬럼을 기준으로 데이터를 정렬한 후 조인을 수행하는 방식을 사용한다. 위의 방식과는 가장 큰 차이점은 정렬이 되어 있기 때문에 인덱스 유무에 영향을 받지 않기 떄문에, Nested Loop Join 방식이 비효율적일 경우 사용한다는 특징이 있다. 또한, 넓은 범위의 데이터를 처리하는데 유용하지만 메모리가 부족한 경우에는 메모리가 아닌 디스크에서 정렬을 수행하므로 성능 저하가 발생할 수 있다.

조인을 수행하는 과정은 아래 그림으로 설명할 수 있다.

Sort Merge Join 수행방식

순서	수행방식	설명
1	Sort 단계	두 테이블을 조인 컬럼을 기준으로 정렬
2	Merge 단계	정렬된 두 테이블을 서로 병합

이 과정에서, Sort Merge Join은 네 가지 특징을 볼 수 있다.

1. 정렬(SORT)
   선행 테이블과 후행 테이블을 조인 컬럼 기준으로 정렬을 진행한다.
2. 부분 범위처리
   선행 테이블이 미리 정렬된 상태에서는 부분적으로 부분 범위처리가 가능하다.
3. 집합의 크기
   두 테이블을 정렬한 후에 조인하기 때문에, 테이블의 크기가 성능에 미치는 영향이 크다. 너무 많은 데이터가 담긴 테이블을 정렬하는 과정은 오버헤드가 많이 발생하기 때문이다.
4. 스캔 방식
   Merge 단계에서, 랜덤 엑세스 방식을 사용하지 않는다. 단, Sort 단계에서는 랜덤 엑세스가 부분적으로 발생한다.

Hash Join

Hash Join은 해시 함수를 활용하여 조인하는 두 테이블의 컬럼값이 동일한 해시값을 갖는 데이터를 조인하는 방법을 사용한다. Sort Merge Join과 마찬가지로 조인 컬럼에 인덱스가 존재하지 않더라도 사용할 수 있는 조인 기법이다. Sort Merge Join 방식을 사용하기에 두 테이블의 크기가 너무 클 때, 정렬 부하가 심하기에 해당 방법을 활용한다. 하지만, 범위로 찾을 수 있는 다른 두 가지 방법과는 다르게 동등 조인(=)에서만 사용할 수 있는 제약이 있다.

조인을 수행하는 과정은 아래 그림으로 설명할 수 있다.

Hash Join 수행방식

순서	수행방식	설명
1	선행 테이블 필터링	선행 테이블에서 주어진 조건을 만족하는 데이터를 필터링
2	선행 테이블 해싱	선행 테이블의 조인 키를 기준으로 해시 함수를 적용해서 해시 테이블을 생성
3	후행 테이블 필터링	후행 테이블에서 주어진 조건을 만족하는 데이터를 필터링
4	후행 테이블 해싱	후행 테이블의 조인 키를 기준으로 해시 함수를 적용해서 선행 테이블의 해시값과 같은 값을 반환하는 해시 버킷을 탐색

이 과정에서, Hash Join은 두 가지 특징을 볼 수 있다.

1. 대용량 테이블
   수행 빈도가 낮고 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 조인하는 과정에서 사용하면 효율적이다.
2. 해시 테이블
   선행 테이블을 이용해서 해시 테이블을 생성한 후, 후행 테이블의 조인 컬럼 값을 해시 테이블에서 O(1)의 시간 복잡도로 찾을 수 있기 떄문에 다른 두 가지 방법처럼 랜덤 엑세스 부하가 발생하거나 정렬하는 과정에서 부하가 발생하지 않는다.

정리

조인 방식에 따라 조건, 사용환경, 장점, 단점 등 차이가 존재한다. Nest Loop Join은 부분 범위 최적화에 유리하고, 조인 테이블에 인덱스가 있는 환경에서 사용하면 좋다. Sort Merge Join은 대용량 테이블 조인에 유리하고, 전체 범위를 최적화하는 환경에서 사용하면 좋다. 마지막으로, Hash Join은 대용량 테이블 중 등치 조건에 대해서 사용하는 것이 좋다.

결론적으로, 조인 방식은 DBMS에 의해 자동적으로 선택되지만, 이를 이해하는 과정에서 쿼리와 데이터 구조를 최적화하여 성능을 크게 향상시킬 수 있다는 점을 알 수 있었다.