콜백 지옥에 이은 join 지옥

필요한 형태의 데이터를 불러오기 위해 불가피하게 여러 테이블을 join 해야 하는 경우가 있다. 예를 들어 3개의 테이블을 join 하여 조회할 때 3개의 테이블에 포함된 모든 데이터를 조회해야 한다. 즉, join을 하는 수가 많아질 경우 더 많은 데이터를 조회해야 한다는 의미이다. 이는 속도의 저하를 불러온다.

 

Join Algorithm

 

join은 데이터 베이스에서 두 개 이상의 테이블을 엮어서 관련된 데이터를 가져오는 작업을 수행하는 SQL 구문이다. 여러 테이블에 한 번에 접근할 수 없으므로 어떤 테이블부터 접근할지 결정하는 방법이 존재한다. 그 방법이 바로 Join Algorithm이다. MySQL에는 Nested loop join, Block nested loop join, Batched key access join 그리고 Nested loop join 등이 있다.

 

DBMS마다 알고리즘이 다르다. Oracle은 Nested loop join, Hash Join 그리고 Sort Merge Join 알고리즘을 제공한다. 이중 어떠한 알고리즘을 선택할지는 옵티마이저가 결정한다.

 

자세히 설명하기 전에 미리 알고 있어야 하는 개념이 있다. 테이블에 접근하는 순서에 따라 이를 부르는 명칭이 있다. 먼저 접근하는 테이블을 드라이빙 테이블(outer table), 다음에 접근하는 테이블이 드리븐 테이블(inner table)이다.

 

SELECT User.user_id, User.name, Order.product_id
FROM User
JOIN Order
ON User.user_id = Order.user_id
WHERE User.user_id IN (1, 10)

 

위와 같이 사용자의 아이디, 이름, 사용자가 주문한 상품의 아이디를 가져오는 쿼리가 있다. 이때 조건절에 User 테이블이 있으므로 이 테이블의 데이터에 먼저 접근한다. 1에서 10번 사이의 아이디를 가진 사용자를 먼저 찾고 그 결과에 기반하여 해당 사용자의 주문 건의 상품들에 접근한다. 드라이빙 테이블은 User, 드리븐 테이블은 Order가 된다. 즉, 드라이빙 테이블의 결과 크기가 작을수록, join 조건절의 열이 인덱스이면 좋다.

 

Nested loop join

마치 for loop 같은 중첩 반복 방식이다. 만약 인덱스도 걸려있지 않고, 기본 키도 없는 상황이라고 할 때 Nested loop join은 모든 열에 접근하려고 든다.

 

Nested loop join

 

User 테이블에서 아이디 1에 해당하는 사용자를 찾기 위해 데이터 10건에 접근하고, 아이디 1과 동일한 데이터를 가졌는지 보려고 Order 테이블의 100건에 접근한다. 이후 과정도 마찬가지이다. 즉, 한 아이디에 해당하는 데이터에 조회하기 위해서만 110건(10 + 100)의 접근이 발생한다. 위 상황에서는 대략 1100건의 접근이 수행된다.

 

만약 같은 알고리즘에서 인덱스를 사용하면 어떻게 변화할까. 사용자 아이디에 인덱스가 걸려있다고 하면 다음과 같이 변화한다. 

 

Nested loop join with index

 

user_id에 인덱스가 걸리면 아이디 1에 대한 접근 1건, 해당 아이디에 대한 주문 건을 찾기 위한 접근 3번 총 4번의 접근이 발생한다. 마찬가지로 아이디 2에 대한 접근은 총 3번이다. 정확하게는 인덱스 스캔 과정도 접근에 포함되어야 하지만 join 메커니즘을 간단히 설명하고자 생략하였다.

 

Hash join

Nested loop join의 한계를 탈피한 알고리즘이다. Oracle에서는 예전부터 지원하고 있었지만 MySQL은 비교적 최근인 8.0.18 버전부터 지원하기 시작했다. 참고로 MariaDB에서는 Block nested loop hash라고 부른다. Hash join은 Nested loop join과는 달리 선후 관계가 따로 없다.

 

Hash Table 출처: https://en.wikipedia.org/wiki/Hash_table

 

Hash 테이블은 효율적인 검색, 삽입을 위해 사용되는 데이터 구조이다. 일반적으로 배열로 구현되며 key - value 형태로 저장된다. Hash 함수를 사용하여 key를 Hash 값으로 변환하고 해당 Hash 값을 인덱스로 사용하여 배열 내의 위치를 정한다. 버킷은 Hash 테이블 내에서 데이터를 저장하는 작은 공간이다.

 

Hash join

 

드리븐 테이블(Order)을 메모리에 읽어 Hash 테이블을 생성하고, 조인 기준이 되는 컬럼의 Hash 값을 계산하고 해당 Hash 값을 가진 행들을 같은 버킷에 저장한다. 이후 드라이빙 테이블(User)을 메모리에 읽어와 Hash 함수를 사용하여 각 행의 Hash 값을 계산한다. 이를 통해 해당 행을 조인할 버킷을 결정한다. 즉, User 테이블의 사용자 아이디 1 데이터는 내부적으로 생성된 Hash 값과 Order 테이블의 사용자 아이디 1의 Hash 값을 비교하고 동일한 경우에만 Join Buffer에 저장된다.

 

이렇게 몇가지 조인 알고리즘에 대해서 알아봤다. 하지만 드라이빙 테이블을 선택하는 것은 개발자가 아닌 옵티마이저이다. 쿼리를 실행시키면 옵티마이저로 해당 쿼리가 전송된다. 옵티마이저는 데이터의 크기, 인덱스의 유무, 결합키 등의 요인에 따른 가능한 모든 경우의 실행계획을 작성한다. 최종적으로 각각의 비용을 계산하여 가장 저비용의 실행계획을 선택한다. Join 하는 테이블들이 모두 인덱스가 있거나 없을 경우 레코드 수에 따라 옵티마이저가 알아서 드라이빙 테이블을 선택한다.

 

그러나 Join중 Outer Join의 경우 Outer가 되는 테이블을 먼저 스캔해야 하므로 위 규칙을 따르지 않는다. Left, Right Join도 각각 왼쪽, 오른쪽의 테이블이 드라이빙 테이블이 된다. 만약 Outer, Inner Join의 결과가 같다면 Outer Join을 통하여 드라이빙 테이블을 선택할 수도 있겠다. 고로, 상황에 따라 가장 적은 횟수의 접근을 통해 원하는 데이터를 조회할 수 있도록 해야 한다.

 

 

 

 

 

* 아래의 자료들을 참고하였습니다.

양바른, 『업무에 바로 쓰는 SQL 튜닝』, 한빛미디어(2021), p68-75.

Hash table - Wikipedia