Hash join in MySQL 8

MySQL 8.0.18 부터 Hash Join 을 지원한다. 

Hash Join 은 Hash Table을 사용하여 두 입력간에 일치하는 행을 찾는 Join  방법이다. 

입력 중 하나가 메모리에 들어갈 수 있는 경우 Nested Loop Join 보다 효율적이다. 

 

빌드 단계

일반적으로 Hash Join을 빌드 단계와 프로브 두단계로 나눈다.

빌드 단계에서 서버는 조인 속성을 해시 테이블 키로 사용하여 입력 중 하나의 행이 저장되는 인메모리 해시 테이블을 빌드한다. 

이 입력을 빌드 입력이라고도하며 'countries'가 빌드 입력으로 지정되었다고 가정했을때, 이상적으로 서버는 두 입력중 더 작은것을 빌드 입력으로 선택한다. (행수가 아닌 바이트로 측정) 'countries.country_id'는 빌드 입력에 속하는 조인 조건이므로 해시 테이블에서 키로 사용된다. 모든 행이 해시 테이블에 저장되면 빌드 단계가 완료된다. 

프로브 단계

프로브 단계 동안 서버는 프로브 입력(이 예에서는 'persons')에서 행을 읽기 시작한다. 

각 행에 대해 서버는 'persons.country_id'의 값을 조회 키로 사용하여 행과 일치하는 해시 테이블을 조사한다. 각 일치에 대해 조인된 행이 클라이언트로 전송된다. 결국 서버는 두 입력간에 일치하는 행을 찾기 위해 일정한 시간 조회를 사용하여 각 입력을 한번 만 스캔했다. 

이것은 서버가 전체 빌드 입력을 메모리에 저장할 수 있다는 점을 감안할때 매우 잘 작동한다. 사용 가능한 메모리양은 시스템변수 join_buffer_size에 의해 제이되며 운영중에 조정할 수 있다. 그러나 빌드 입력이 사용 가능한 메모리보다 크면 디스크를 사용한다. 

 

디스크로 유출

빌드 단계에서 메모리가 가득차면 서버는 빌드 입력의 나머지 부분을 디스크의 여러 청크 파일에 쓴다. 서버는 가장 큰 청크가 메모리에 정확히 맞도록 청크 수를 설정하려고 하지만 MySQL은 입력당 최대 128개의 청크파일제한한다. 행이 기록되는 청크 파일은 조인 속성의 해시를 계산하여 결정된다. 그림에는 메모리 내 빌드 단계에서 사용된것과 다른 해시 함수가 사용된다. 그 이유는 나중에 살펴본다. 

프로브 단계 동안 서버는 모든 것이 메모리에 맞을때와 마찬가지로 해시 테이블에서 일치하는 행을 조사한다. 그러나 행은 디스크에 기록된 빌드 입력의 행중 하나와 일치할 수도 있다. 따라서 프로브 입력의 각 행도 청크 파일 세트에 기록된다. 행이 기록되는 청크 파일은 빌드 입력이 디스크에 기록될때 사용되는 동일한 해시 함수 및 공식을 사용하여 결정된다. 이렇게 하면 두 입력사이에 일치하는 행이 동일한 청크파일쌍에 위치하게 된다. 

프로브 단계가 완료되면 디스크에서 청크 파일을 읽기 시작한다. 일반적으로 서버는 첫번째 청크 파일 세트를 빌드 및 프로브 입력으로 사용하며 빌드 및 프로브 단계를 수행한다. 빌드 입력의 첫번째 청크 파일을 메모리 내 해시 테이블로 로드한다. 이것은 우리가 메모리에 정확히 맞는 가장 큰 청크를 원하는 이유를 설명한다. 청크 파일이 너무 크면 더 작은 청크로 분할해야한다. 빌드 청크가 로드된후 프로브 입력에서 해당 청크 파일을 읽고 모든 것이 메모리에 맞을때와 마찬가지로 해시 테이블에서 일치항목을 검색한다. 청크 파일의 첫번째 쌍을 처리하면 다음 쌍의 청크 파일로 이동하고 모든 청크파일이 처리 될때까지 계속한다. 

이제 행을 청크 파일로 분할하고 해시 테이블에 행을 쓸때 두개의 다른 해시함수를 사용해야하는 이유를 짐작했을 것이다. 두작업 모두에 동일한 해시 함수를 사용하면 동일한 청크 파일의 모든 행이 동일한 값으로 해시되므로 빌드 청크 파일을 해시 테이블에 로드 할때 매우 나쁜 해시 테이블을 얻게 된다. 

 

Hash Join 사용방법

해시 조인은 기본적으로 활성화되어 있으므로 해시 조인을 사용하기 위해 필요한 작업이 없다. 한가지 주목할만한 점은 해시 조인이 새로운 반복자 실행기를 기반으로 구축된다는 것이다. 즉 EXPLAIN FORMAT=tree를 사용하여 해시 조인이 사용되는지 여부를 확인할 수 있다. 

mysql> EXPLAIN FORMAT=tree
    -> SELECT
    ->   given_name, country_name
    -> FROM
    ->   persons JOIN countries ON persons.country_id = countries.country_id;
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Inner hash join (countries.country_id = persons.country_id)  (cost=0.70 rows=1)
|   -> Table scan on countries  (cost=0.35 rows=1)
|   -> Hash
|      -> Table scan on persons  (cost=0.35 rows=1)
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.01 sec)

일반적으로 하나 이상의 동등 조인 조건을 사용하여 테이블을 조인하고 조인 조건에 사용할 수 있는 인덱스가 없는 경우 해시 조인이 사용된다. 인덱스를 사용할 수 있는 경우 MySQL은 인덱스 조회가 있는 중첩 루프(Nested Loop)를 선호하는 경향이 있다. 

 

모든 쿼리에 대해 해시조인을 비활성화 할수 있는 새로운 optimizer switch를 도입했다. 

mysql> SET optimizer_switch="hash_join=off";
Query OK, 0 rows affected (0.00 sec)
 
mysql> EXPLAIN FORMAT=tree
    -> SELECT
    ->   given_name, country_name
    -> FROM
    ->   persons JOIN countries ON persons.country_id = countries.country_id;
+----------------------------------------+
| EXPLAIN                                |
+----------------------------------------+
|                                        |
+----------------------------------------+
1 row in set (0.00 sec)

해시 조인이 꺼지면 MySQL은 블록 중첩 루프로 돌아가고 따라서 이전 실행 프로그램이 된다. (블록 중첨 루프는 반복기 실행 프로그램에서 지원되지 않는다.) 이 스위치를 사용하면 해서 조인과 블록 중첩 루프의 성능을 쉽게 비교할 수 있다. 

 

빌드 입력이 너무 커서 메모리에 맞지 않아 해시조인이 디스크를 사용하는 경우 조인 버퍼 크기를 늘릴 수 있다. 블록 중첩 로프와 달리 해시 조인은 메모리를 점진적으로 할당하므로 필요한것보다 더 많은 메모리를 사용하지 않는다. 이러한 이유로 해시 조인을 사용할 때 더 큰 조인 버퍼 크기를 사용하는것이 더 안전하다. 

 

해시 조인 제한사항

MySQL은 내부 해시 조인만 지원한다. 

anit, semi, outer join 은 블록 중첩 루프를 사용하여 실행된다. 

optimizer/planner 는 블록 중첩 루프를 사용하여 조인을 실행하는것에 우선을 둔다. 

 

 

참고

https://mysqlserverteam.com/hash-join-in-mysql-8/