서론
지금까지 학습했던 Join 쿼리는 inner join, outer join, cross join, self join 같이, 쿼리문에 명시하는 정보가 전부였다.
그러나 이는 논리적 조인만을 이야기하는 것으로, 실제로 DB가 이 조인 쿼리를 어떻게 물리적으로 조인해오는지는 다른 관점에서 보아야 한다.
즉, 우리가 조인 쿼리를 튜닝하여 성능을 개선한다는 것은, 정확히는 쿼리문만을 보고는 이야기할 수 없다.
쿼리문만을 보고 튜닝한다는 것은 말이 안된다. 성능 개선 튜닝을 하려면 실행 환경을 꼭 보아야 한다.
물리적 조인
Nested Loop Join
동작 방식
가장 단순한 이중 루프이다. 외부 테이블이 작고, 내부 테이블에 좋은 인덱스가 있을 때 빛을 본다.
외부 테이블의 각 행마다 내부 테이블을 반복적으로 탐색해, 조인 조건을 만족하는 행을 찾는 방식으로 동작한다.
유리한 환경
단일 코어 클럭이 높을 때 유리하다.
Nested Loop Join의 핵심 동작은 외부 테이블 행 하나당 내부 테이블의 인덱스 트리 (B+Tree)를 따라 내려가 일치하는 행을 찾는 것이다.
이때, 반복문 특성상 i번째 row 작업이 끝나야 i+1번째 row 작업이 가능한데, 즉 이는 순차적 의존성을 띄고 있다고 말할 수 있다.
병렬화는 여러 작업이 서로 독립적이며 동시에 실행 가능해야 유리하다.
그러나 Nested Loop Join은 순차적 의존성을 띄므로, 성능 향상을 위하여 병렬화하는 것이 어렵다.
따라서 단일 CPU 코어에서만 동작하게 되므로, 해당 CPU 클럭이 높아야 Nested Loop Join의 성능 향상에 유리하다.
Hash Join
동작 방식
작은 쪽 테이블(Build 테이블)을 읽어 조인 키를 해시 함수로 변환해 메모리에 해시 테이블을 만든다.
이후, 큰 쪽 테이블(Probe 테이블)을 스캔하면서 각 행의 조인 키를 해싱하여 해시 테이블에서 일치하는 버킷을 찾아 매칭한다.
유리한 환경
메모리가 클수록 유리하다.
Hash Join은 Build 단계에서 작은 쪽 테이블을 읽어 해시 테이블을 만든다고 했다.
이때 해시 테이블이 전부 RAM에 올라갈 수 있으면, RAM에 접근하는 속도는 디스크 접근에 비해 훨씬 빠르므로 Probe 단계도 빠르게 끝낼 수 있다.
즉, Hash Join이 빠르다는 전제는 메모리 안에서 O(1) 이라는 해시 함수의 시간 복잡도를 누린다는 것을 전제로 한다.
만약 해시 테이블이 RAM 용량을 초과하여 디스크로 밀려난다면, Hash Join의 성능이 I/O에 크게 의존하게 된다.
데이터가 연속적이지 않는 해시 구조 특성상, 특정 해시 버킷을 찾으려면 디스크로 밀려난 해시 테이블도 매번 찾아야 한다.
원래는 디스크 I/O에 의존하지 않아 빠른데도, 메모리가 부족하다는 이유로 성능에 치명적인 I/O 대기 시간이 생긴다는 것이다.
따라서 Hash Join은 해시 테이블이 들어갈 만큼 메모리가 충분이 커야 성능 향상에 유리하다.
Sort Merge Join
동작 방식
먼저, 두 테이블을 조인 키 기준으로 정렬한다.
이후, 정렬된 두 테이블에 포인터를 두고 양쪽을 동시에 한번씩 훑으면서(투 포인터) 키를 비교해 매칭한다.
두 테이블이 정렬되어 있기 때문에 한쪽이 작으면 그쪽을 전진시키는 방식으로 한번의 스캔으로 끝낼 수 있다.
유리한 환경
CPU 코어가 많을수록 유리하다.
Sort Merge Join에서 실제로 비용이 큰 단계는 Sort 단계이다.
이때, Sort는 병렬화가 잘 되는 작업이다.
예를 들어, 데이터를 여러 조각으로 나누고, 각 조각을 각 코어가 독립적으로 정렬해보자.
그러면, 정렬을 마무리할 때는 각 조각에서 가장 작은 값을 뽑아오면서 하나의 정렬된 데이터를 만들 수 있다.
즉, Nested Loop Join과 달리 각 조각 정렬 작업이 순차적 의존성을 띄지 않기 때문에, 병렬화했을때 이점이 크다.
따라서 Sort Merge Join은 성능 향상을 위해 병렬화가 가능하고, 때문에 CPU 코어가 많을수록 유리하다.