SQL 엔진에서 JOIN 을 수행하는 원리 (MySQL)

SQL최적화를 수행하는 도중, 최적화를 수행한 쿼리의 내용은 다음과 같다. 

 

table b를 table a에 left join 하는 과정에서 on 의 조건이 어차피 b의 PK 였던 경우. 

예를 들면 이런 경우이다. 

select * from
b
left join a 
on a.id = "1234"

 

이런식의 조인 쿼리는 서브쿼리로 조회하는 게 더 빠르지 않을까 싶어서 서브쿼리로 바꿨더니, explain analysis 분석결과는 sql 2배 가량 속도가 빨라졌다.

그러나 막상 JPA 상에서 실행 결과를 확인할 때는 별로 시간 차이가 없었다.  (오히려 조금 더 느렸다.)

이 과정에서 세운 여러 가설을 검증하다보니 SQL 엔진에서 join을 수행하는 원리에 대해서도 찾아보게 되었다. 

(이 문제를 해결한 내용은 추후 글에서 공개하도록 하려고 한다. )

 

이 글에서는 MySQL 엔진이 내부적으로 테이블을 JOIN할 때, 여러 가지 방법을 사용하는 것에 대해 논한다. 내부적으로 어떤 원리와 최적화 방법을 가지고 JOIN을 수행하는지 알아보자. 추후 최적화하는데도 도움이 될 것이다. 

 

 

SQL 엔진은 두 개 이상의 테이블을 조인할 때 내부적으로 다른 알고리즘을 사용하여 데이터를 결합한다. 어떤 알고리즘이 사용될지는 데이터 크기, 인덱스 여부, 테이블 스캔 비용 등을 기준으로 SQL 엔진이 자동으로 결정한다. 물론 JOIN 방식을 직접 지정할 수도 있다. 

 

1. Nested Loop Join

 

• 가장 기본적인 join 방식이다. 
• 한 테이블을 기준으로 하나씩 데이터를 가져오면서 다른 테이블과 비교한다. 
• 예를 들어, 첫 번째 테이블에서 한 줄을 가져오고, 두 번째 테이블을 전부 뒤져서 매칭되는 걸 찾는 방식이다. 
• 작은 테이블에서는 괜찮지만, 큰 테이블에서는 느릴 수 있다. 

 

SELECT *
FROM A
JOIN B ON A.id = B.id;

A 테이블을 하나씩 조회하면서, 테이블 B에서는 조건에 맞는 행을 찾는 방식. 

B 테이블에서 인덱싱이 되어있는 경우 유리하다. 

 

내부에서 돌아가는 동작은 이런 느낌일 것이다. 

for each row in A {
    for each row in B {
        if (A.id == B.id) {
            output(A, B);
        }
    }
}

 

중첩 루프같은 동작이라서 'nested' 라는 이름이 붙었다. 

 

8.4버전 기준으로 설명은 다음과 같다.  (링크)

 

nested loop 사용할 때 최적화를 위해서 mysql이 하는 동작은 다음과 같다. (참고)

 

 

1. 조인 순서 변경(Join Order Optimization)
   • MySQL은 테이블을 조인할 때 가장 적은 비용이 드는 순서로 조인의 순서를 바꿀 수 있다. 
   • 작은 테이블을 먼저 처리하면, 나머지 테이블을 탐색할 범위가 줄어들어서 속도가 빨라진다. 
2. 인덱스 사용(Index Usage)
   • 조인할 때 인덱스가 걸려 있다면, MySQL은 Index Nested Loop Join을 사용해서 빠르게 조인할 수 있다. 
   • 예를 들어, B 테이블의 a_id 열에 인덱스가 걸려 있다면, A에서 한 줄을 가져온 뒤 인덱스를 사용해서 B에서 빠르게 찾을 수 있다. 
3. 조건 조기 적용(Predicate Pushdown)
   • WHERE 조건을 최대한 빨리 적용해서, 조인할 데이터의 양을 줄이는 방식이다. 
   • 불필요한 데이터를 조인하기 전에 걸러내서 성능을 높일 수 있다. 

 

2.블록 중첩 루프 조인(Block Nested Loop Join)

• 중첩 루프 조인의 업그레이드 버전이다. 
• 한 번에 하나의 행을 가져오는 게 아니라, 여러 개의 행(블록 단위)을 가져와서 비교한다. 
• 이렇게 하면 디스크 읽기 횟수를 줄일 수 있어서 속도가 더 빠르다. 

 

 

 

3. 인덱스 중첩 루프 조인(Index Nested Loop Join)

• 두 번째 테이블이 인덱스를 가지고 있을 때 사용하는 방식이다. 
• 한 테이블의 한 행을 가져온 뒤, 인덱스를 이용해서 빠르게 검색한다. 
• 일반 중첩 루프 조인보다 훨씬 빠르지만, 인덱스가 필요하다. 

 

 

4. Hash Join

두 테이블이 크지만, 조인 조건을 만족하는 인덱스가 없을 때 사용한다. 

이름에서 알 수 있듯, 해시테이블을 사용하는 방식이다.

 

작은 테이블에서 조인 칼럼에 대해 hash 테이블을 만들어두고, 큰 테이블에서는 해싱결과가 매치하는 행을 찾는 방식이다. 

이 과정은 2단계로 나뉜다.

 

• 빌드 단계(Build Phase):
  • 먼저, 작은 테이블을 선택한다. 
  • 이 테이블을 해쉬테이블로 만든다. 
• 프로브 단계(Probe Phase):
  • 이제 큰 테이블을 하나씩 살펴본다. 
  • 각 데이터마다, 한 행씩 해쉬테이블을 찾아보며 일치하는 데이터를 찾는다. 

 

Build Hash Table from smaller table A on id column
for each row in table B {
    if (B.id exists in Hash Table) {
        output(A, B);
    }
}

 

특징은 다음과 같다. 

• 작은 테이블- 큰 테이블 간의 join 시에 유용하다. 
• 메모리를 많이 사용하므로, 메모리 사용크기에 따라 분할도 가능하다. 반대로 메모리를 많이 사용하는 것이 한계점이기도 하다. 
• 이 방식은 인덱싱이 없을 때, 특히 대용량일 때 성능이 좋다고 한다. 
• 한계점: 메모리를 많이 잡아먹는다. 같은 값을 조회할 때만 성능 상의 이점이 있다.

 

explain analysis 쿼리를 실행했을 때 실행 계획에 Using join buffer (hash join)이라는 문구가 나타나는 것으로 hash join을 사용했다는 것을 알 수 있다.

 

hash join을 사용할 때 최적화 포인트와 주의점은 다음과 같다. 

1. join_buffer_size 시스템 변수를 통해 해시 조인에 사용할 메모리 크기를 설정할 수 있다.

2. 만약 해시 조인에 필요한 메모리가 설정된 크기를 초과하면, MySQL은 디스크의 임시 파일을 사용하여 조인을 수행한다.

3.  이러한 경우, open_files_limit 설정에 따라 조인이 실패할 수 있으므로, 필요에 따라 join_buffer_size나 open_files_limit 값을 조정해야한다. 

 

 

지금까지 nested loop join 과 그 업그레이드 버전, hash join 에 대해 알아봤다. 

 

오라클도 join 방법에 대해 정리해둔 문서가 있으니, 봐두면 좋을 것 같다. : 링크