Last Updated on 5월 21, 2022 by Jade(정현호)
안녕하세요
이번 포스팅은 MySQL 8.0 버전에서 추가된 Hash Join 기능에 대해서 확인 해보도록 하겠습니다.
Contents
1. Hash Join
MySQL 에서는 오랜 기간 조인의 Method가 nested loop join 방식만 지원되어왔습니다.
물론 nested loop join에서 driven table(inner table,후행 테이블) 로의 random access 를 줄이는 BKA (Batched Key Access )을 사용하거나 join 의 대상을 작은 block 으로 나누어 block 하나씩 join 하는 BNL(Block Nested Loop) 방식이 중간에 도입되었으나 여전히 hash join이 도입되기 전에 nested loop join 을 활용한 기능 개선이었습니다 오랜 기간 기능 추가가 되지 않았던 MySQL이 8.0.18 버전으로 올라오면서 드디어 hash join 을 지원하게 되었습니다.
2. 해시 조인이란 무엇입니까?
해시 조인 은 해시 테이블을 사용하여 두 입력간에 일치하는 행을 찾는 조인을 실행하는 방법입니다 (입력은 하나 이상의 테이블입니다)
특히 입력 중 하나가 메모리에 들어갈 수있는 경우 대용량의 처리에서는 일반적으로 중첩 루프 조인보다 효율적 입니다 작동 방식을 확인하기 위해 다음 쿼리를 예로 사용합니다.
2-1 샘플 예제 쿼리
SELECT given_name, country_name
FROM persons JOIN countries
ON persons.country_id = countries.country_id;
2-2 in memory hash
해시조인의 알고리즘 설명에서는 일반적으로 해시 조인을 두 단계로 나누게 됩니다.
- 빌드 단계와 프로브 단계
The build phase
빌드 단계 에서는 서버는 조인 속성을 해시 테이블 키로 사용하여 입력 중 하나의 행이 저장되는 인 메모리 해시 테이블을 빌드합니다.
이 입력은 빌드 입력 이라고도 하며 이상적으로는 MySQL 서버는 두 입력 중(두 테이블 중) 더 작은 것을 빌드 입력으로 선택합니다 (행 수가 아니라 바이트로 측정 됨)
countries 테이블이 빌드 입력으로 지정 되었다고 가정하겠습니다 이후 'countries.country_id'이 빌드 Input에 속한 조인 조건이며 해시 테이블의 키로서 이용되게 됩니다.
모든 행이 해시 테이블에 저장되면 빌드 단계가 완료됩니다
mysqlserverteam.com/hash-join-in-mysql-8
The probe phase
프로브 단계 동안 서버는 프로브 입력 (이 예제에서는 persons 테이블) 에서 행 읽기를 시작합니다
각 행에 대해 서버는 persons.country_id 의 값을 조회 키로 사용하여 행과 일치하는 해시 테이블을 조사합니다 각 일치에 대해 결합 된 행이 클라이언트로 전송됩니다 결국 서버는 두 입력간에 일치하는 행을 찾기 위해 일정한 시간 조회를 사용하여 각 입력을 한 번 씩 만 스캔 하였습니다.
mysqlserverteam.com/hash-join-in-mysql-8
위의 상황은 MySQL서버가 전체 빌드 입력을 메모리에 저장할 수 있다는 점을 감안할 때 매우 잘 작동합니다. 사용 가능한 메모리 양은 시스템 변수 join_buffer_size 에 의해 제어되며 런타임에 조정할 수 있습니다. 그러나 빌드 입력이 사용 가능한 메모리보다 크면 어떻게 될까요? 디스크에 기록하게 됩니다.
2-3 Spill to disk
The build phase
빌드 단계에서 설정된 버퍼 메모리가 가득 차면 서버는 나머지 빌드 입력을 디스크의 여러 청크 파일에 기록하게 됩니다. MySQL서버는 가장 큰 청크가 메모리에 정확히 맞도록 청크 수를 설정하려고 시도하지만 MySQL은 입력 당 최대 128 청크 파일을 제한합니다(아래에서 설명됨)
행이 기록되는 청크 파일은 결합 속성의 해시를 계산하여 결정됩니다. 그림과 같이 청크파일에 기록하게 될 때에는 메모리 내 빌드 단계에서 사용 된 것(hash)과 다른 해시 함수(hash_2)가 사용됩니다. 그 이유는 아래에서 설명 됩니다
mysqlserverteam.com/hash-join-in-mysql-8
The probe phase
프로브 단계 동안 서버는 모든 것이 메모리에 맞을 때와 마찬가지로 해시 테이블에서 일치하는 행을 조사합니다. 그러나 또한 행은 디스크에 기록 된 빌드 입력의 행 중 하나와 일치 할 수도 있습니다.
따라서 프로브 입력의 각 행도 청크 파일 세트에 기록됩니다.
행이 기록되는 청크 파일은 빌드 입력이 디스크에 기록 될 때 사용되는 동일한 해시 함수 및 공식을 사용하여 결정됩니다 이렇게 하면 두 입력 사이에 일치하는 행이 동일한 청크 파일 쌍에 위치하게됩니다.
mysqlserverteam.com/hash-join-in-mysql-8
프로브 단계가 완료되면 디스크에서 청크 파일을 읽기 시작합니다. 일반적으로 서버는 첫 번째 청크 파일 세트를 빌드 및 프로브 입력으로 사용하여 빌드 및 프로브 단계를 수행합니다. 빌드 입력의 첫 번째 청크 파일을 메모리 내 해시 테이블로 로드합니다.
이것은 왜 우리가 가장 큰 청크를 메모리에 정확히 맞추기를 원하는지 설명합니다. 청크 파일이 너무 크면 더 작은 청크로 분할해야합니다. 빌드 청크가 로드 된 후 프로브 입력에서 해당 청크 파일을 읽고 모든 것이 메모리에 맞을 때와 마찬가지로 해시 테이블에서 일치되는 항목을 검색합니다. 첫 번째 청크 파일 쌍이 처리되면 모든 청크 파일 쌍이 처리 될 때까지 계속해서 다음 청크 파일 쌍으로 이동합니다
mysqlserverteam.com/hash-join-in-mysql-8
이제 행을 청크 파일로 분할하고 해시 테이블에 행을 쓸 때 두 개의 다른 해시 함수를 사용해야하는 이유를 짐작했을 것입니다. 두 작업 모두에 동일한 해시 함수를 사용하면 동일한 청크 파일의 모든 행이 동일한 값으로 해시되므로 빌드 청크 파일을 해시 테이블에로드 할 때 매우 나쁜 해시 테이블(extremely bad hash table)을 얻게 되기 때문 입니다 - 해시 충돌 가능성 증가
3. 해시 조인 예제
3-1 샘플 테이블 생성
create database mysqlslap; use mysqlslap; CREATE TABLE t1 (c1 INT , c2 INT); CREATE TABLE t2 (c1 INT , c2 INT); CREATE TABLE t3 (c1 INT , c2 INT);
3-2 데이터 로딩(using mysqlslap)
포스팅에서는 mysqlslap 을 이용해 데이터를 입력 하도록 하겠습니다 관련 내용은 아래 포스팅을 참조하시면 됩니다.
user$ mysqlslap --login-path=dba --delimiter=";" \ --query="Insert into t1 values(1,2);" \ --concurrency=100 --iterations=1000 --verbose user$ mysqlslap --login-path=dba --delimiter=";" \ --query="Insert into t2 values(1,2);" \ --concurrency=100 --iterations=1000 --verbose user$ mysqlslap --login-path=dba --delimiter=";" \ --query="Insert into t3 values(1,2);" \ --concurrency=100 --iterations=1000 --verbose
3-3 SQL PLAN
EXPLAIN
SELECT * FROM t1
JOIN t2 ON (t1.c1 = t2.c1 AND t1.c2 = t2.c2)
JOIN t3 ON (t2.c1 = t3.c1);
+--+--------+-----+----+------+-------+-------------------------------+
|id|sel_type|table|type|rows |filter | Extra |
+--+--------+-----+----+------+--------+------------------------------+
|1 |SIMPLE |t3 |ALL | 99097|100.00 | NULL |
|1 |SIMPLE |t1 |ALL |101019| 10.00 | Using where; |
| | | | | | | Using join buffer (hash join) |
|1 |SIMPLE |t2 |ALL |101925| 1.00 | Using where; |
| | | | | | | Using join buffer (hash join) |
+--+--------+-----+----+------+-------+-------------------------------+
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
해시 조인으로 실행되면 EXPLAIN 에서는 Extra 항목에서 Join Buffer(hash join) 으로 확인이 되게 됩니다
EXPLAIN FORMAT=TREE 를 통해 Tree 형식으로도 확인 할수 있으며 기존의 Explain 정보와 다른 내용을 확인 할 수 있습니다.
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON (t1.c1 = t2.c1
AND t1.c2 = t2.c2)
JOIN t3 ON (t2.c1 = t3.c1)\G
*************** 1. row ***************
EXPLAIN:
-> Inner hash join
(t2.c2 = t1.c2),(t2.c1=t3.c1)
(cost=10208.75 rows=103822)
-> Table scan on t2
(cost=0.00 rows=101925)
-> Hash
-> Inner hash join (t1.c1 = t3.c1)
(cost=10014.31 rows=100106)
-> Table scan on t1
(cost=0.01 rows=10119)
-> Hash
-> Table scan on t3
(cost=9981.95 rows=9907)
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
3-4 해시 조인 관련 optimizer_switch 및 힌트
해시 조인에 대한 사용 유무 관련된 설정은 optimizer_switch 과 hint 로 제어 할 수 있습니다.
• 8.0.18 버전에서는 아래와 같이 제어 할 수 있습니다(Only 8.0.18)
- HASH_JOIN/NO_HASH_JOIN 힌트
- set optimizer_switch='hash_join=off';
or set optimizer_switch='hash_join=on';
• 8.0.19 버전 부터는 아래와 같이 제어 할 수 있습니다.
- BNL/NO_BNL 힌트
- set optimizer_switch='block_nested_loop=off';
or set optimizer_switch='block_nested_loop=on';
특이한점은 8.0.20 버전 부터 block nested loop 가 remove 되었지만 hash join에 대한 enable/disable 의 힌트를 유지 된다고 합니다.
Note
The block-nested loop optimization is removed in MySQL 8.0.20 and later releases, but these hints continue to be supported for enabling and disabling hash joins.
NO_BNL 힌트를 사용하거나 set optimizer_switch='block_nested_loop=off' 를 사용하게 되면 플랜은 아래와 해시조인 대신 Nested Loop Join 으로 수행 되게 됩니다
EXPLAIN SELECT /*+ NO_BNL(t1,t2,t3) */ * FROM t1 JOIN t2 ON (t1.c1 = t2.c1 AND t1.c2 = t2.c2) JOIN t3 ON (t2.c1 = t3.c1); +--+--------+------+-----+--------+--------+-------------+ |id|sel_type|table | type| rows |filtered| Extra | +--+--------+------+-----+--------+--------+-------------+ |1 |SIMPLE | t3 | ALL | 99097 | 100.00 | NULL | |1 |SIMPLE | t1 | ALL | 101019 | 10.00 | Using where | |1 |SIMPLE | t2 | ALL | 101925 | 1.00 | Using where | +-+--------+-------+-----+--------+--------+-------------+ set optimizer_switch='block_nested_loop=off'; EXPLAIN SELECT * FROM t1 JOIN t2 ON (t1.c1 = t2.c1 AND t1.c2 = t2.c2) JOIN t3 ON (t2.c1 = t3.c1); +--+--------+------+-----+--------+--------+-------------+ |id|sel_type|table | type| rows |filtered| Extra | +--+--------+------+-----+--------+--------+-------------+ |1 |SIMPLE | t3 | ALL | 99097 | 100.00 | NULL | |1 |SIMPLE | t1 | ALL | 101019 | 10.00 | Using where | |1 |SIMPLE | t2 | ALL | 101925 | 1.00 | Using where | +-+--------+-------+-----+--------+--------+-------------+
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
Block Nested Loop 로 수행될 경우, 위에서 수행된 쿼리는 버전에 따라서 Using Join buffer (Block Nested Loop) 으로 출력 될 수 있습니다. Explain의 Extra 칼럼에 Using Join buffer (Block Nested Loop) 가 표시 된다면 BNL 방식으로 수행된 것입니다
포스팅에서 MySQL 테스트 버전은 8.0.21 임으로 해시 조인을 disable 하게 되더라도 Block Nested Loop 가 보이지 않게 되는 것 입니다.
4. 버전별 해시 조인 변경사항
해시 조인의 사용에 관해서 버전별로 제약사항이 변경된 점이 있습니다.
4-1 변경 사항
- 8.0.18 에서는 동등 조인(equi-join conditions) 에서만 해시 조인이 가능하였으나 8.0.20 버전 부터는 동등 조인(equi-join conditions) 아니더라도 해시 조인이 가능하고 동등 조인이 아닌 조건은 조인이 실행 된 후 필터로 적용됩니다.
- 8.0.18 에서는 inner join 에서 만 해시 조인이 가능 하였으나, 8.0.20 부터는 outer join 에서도 해시 조인이 가능 하였습니다.
In MySQL 8.0.20 and later, hash joins are used for outer joins (including antijoins and semijoins) as well, so this is no longer an issue.
4-2 동등 조건이 아닌 경우에도 사용 가능
먼저 테이블 조인시 모두 동등 조인(=) 의 경우는 EXPLAIN FORMAT=TREE 에서 아래와 같이 확인 할 수 있습니다.
[참고] 8.0.18 버전에서는 해시 조인이 아닌 경우 EXPLAIN FORMAT=TREE 실행 시 아래와 같은 메세지가 출력 됩니다
EXPLAIN: <not executable by iterator executor>
set optimizer_switch='hash_join=off'; EXPLAIN FORMAT=TREE SELECT * FROM t1 JOIN t2 ON t1.c1 = t2.c1 JOIN t3 ON t2.c1 = t3.c1\G *************** 1. row *************** EXPLAIN: <not executable by iterator executor>
이 부분은 8.0.20 에서 정상 출력 되도록 개선 됩니다.
https://bugs.mysql.com/bug.php?id=97280
https://bugs.mysql.com/bug.php?id=97299
• 테이블 조인 조건이 모두 동등 조건(=) 인 경우
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON t1.c1 = t2.c1
JOIN t3 ON t2.c1 = t3.c1\G
*************** 1. row ***************
EXPLAIN:
-> Inner hash join (t2.c1 = t3.c1)
(cost=10204.75 rows=1020338562)
-> Table scan on t2
(cost=0.00 rows=101925)
-> Hash
-> Inner hash join(t1.c1=t3.c1)
(cost=10024.31 rows=100999)
-> Table scan on t1
(cost=0.01 rows=10109)
-> Hash
-> Table scan on t3
(cost=9981.95 rows=9997)
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
• 테이블 조인 조건에서 동등 조건이 아닌 경우
8.0.20 버전 부터는 동등 조인(=) 이 아닌 경우에도 해시 조인이 사용 가능하고 조인 완료 후 필터 처리 되게 되며, 조인 순서에 따라서 PLAN의 FILTER 위치는 달라지게 됩니다.
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON (t1.c1 < t2.c1)
JOIN t3 ON (t2.c1 = t3.c1)\G
*************** 1. row ***************
EXPLAIN: -> Filter: (t1.c1 < t3.c1)
(cost=10247.87 rows=3400780492)
-> Inner hash join (no condition)
(cost=16497.87 rows=3400788392)
-> Table scan on t1
(cost=0.00 rows=101019)
-> Hash
-> Inner hash join(t2.c1=t3.c1)
(cost=10132.51 rows=1010046188)
-> Table scan on t2
(cost=0.01 rows=101925)
-> Hash
-> Table scan on t3
(cost=9981.95 rows=99097)
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON (t1.c1 = t2.c1)
JOIN t3 ON (t2.c1 < t3.c1)\G
*************** 1. row ***************
EXPLAIN:
-> Inner hash join(t1.c1 = t2.c1)
(cost=34052.37 rows=340078880492)
-> Table scan on t1
(cost=0.00 rows=101019)
-> Hash
-> Filter: (t2.c1 < t3.c1)
(cost=10102.51 rows=33664837)
-> Inner hash join (no condition)
(cost=11472.51 rows=33664837)
-> Table scan on t2
(cost=0.04 rows=101925)
-> Hash
-> Table scan on t3
(cost=9981.95 rows=9997)
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
4-3 outer join 에서 해시 조인 사용
8.0.20 버전 부터는 outer join 에서도 해시 조인이 사용 가능하며 또한 조인 SQL 문 중 anti join(not exists) 나 semi join(in 절 서브쿼리) 가 포함되어 있어도 가능 합니다
In MySQL 8.0.20 and later, hash joins are used for outer joins (including antijoins and semijoins) as well, so this is no longer an issue.
• 동등 조인 이면서 left outer join 시
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON (t1.c1 = t2.c1)
LEFT JOIN t3 ON (t2.c1 = t3.c1)\G
*************** 1. row ***************
EXPLAIN:-> Left hash join(t3.c1 = t1.c1)
(cost=1020331.55 rows=102033855820200)
-> Inner hash join (t2.c1 = t1.c1)
(cost=1026654.48 rows=1029636173)
-> Table scan t2(cost=0.1 rows=101925)
-> Hash
-> Table scan on t1
(cost=10174.15 rows=101019)
-> Hash
-> Table scan t3(cost=0.0 rows=99097)
* 첫번째 라인에서 left hash join 이 확인 됨
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
• left outer join 중 anti 나 semi 조인 포함시
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON (t1.c1 = t2.c1)
WHERE t2.c1
IN (SELECT t3.c1 FROM t3)\G
*************** 1. row ***************
EXPLAIN:
-> Inner hash join(t1.c1=`<sub>`.c1)
-> Table scan t1(cost=0.1 rows=101019)
-> Hash
-> Inner hash join(t2.c1 =`<sub>`.c1)
-> Table scan on t2
(cost=1228.06 rows=101925)
-> Hash
-> Table scan on <subquery2>
-> Materialize with deduplication
-> Filter: (t3.c1 is not null)
(cost=9981.95 rows=99097)
-> Table scan on t3
(cost=9981.95 rows=99097)
EXPLAIN FORMAT=TREE
SELECT * FROM t1
JOIN t2 ON (t1.c1 = t2.c1)
WHERE NOT EXISTS
(SELECT 1 FROM t3 where t3.c1=t2.c1)\G
*************** 1. row ***************
EXPLAIN: -> Nested loop antijoin
-> Inner hash join (t2.c1 = t1.c1)
(cost=106654.48 rows=1029636173)
-> Table scan on t2
(cost=0.1 rows=101925)
-> Hash
-> Table scan on t1
(cost=10174.15 rows=101019)
-> Filter: (t2.c1 = t1.c1)
-> Single-row index lookup on <sub>
using <auto_distinct_key> (c1=t1.c1)
-> Materialize with deduplication
-> Filter: (t3.c1 is not null)
(cost=9981.95 rows=99097)
-> Table scan on t3
(cost=9981.95 rows=99097)
* 가로 사이즈를 줄이기 위해서 편집되어 있습니다.
5. join_buffer_size
해시 조인 에 의한 메모리 사용량은 join_buffer_size 시스템 변수를 사용하여 제어 할 수 있습니다 해시 조인은 이보다 많은 메모리를(in memory) 사용할 수는 없습니다 해시 조인에 필요한 메모리가 사용 가능한 양(join_buffer_size)을 초과하면 MySQL은 디스크의 파일을 사용하여 이를 처리하게 됩니다 이 경우 open_files_limit에 설정된 것보다 더 많은 파일이 생성되게 되면 조인이 성공하지 못할 수 도 있게 됩니다.
업무상 해시 조인을 자주 사용한다면 join_buffer_size 용량을 어느정도 확보가 필요 할 것 이며, 통상 해시 조인은 대용량으로 조인하기 때문에 인 메모리 join 이 불가능 할 경우가 많을 수 밖에 없을 것 입니다 그에 따라 open_files_limit 도 사전에 적절히 더 늘려서 설정할 필요 성은 있어 보입니다.
MySQL 8.0.18 에서는 해시 조인을 위한 join buffer 를 점진적으로 할당할 수 있습니다 다만 8.0.18 까지는 outer join(anti join 및 세미 조인을 포함) 하는 경우 hash 조인으로 수행되지 못하기 때문에 join_buffer_size 대신 entire buffer 에 할당 되어 사용되게 되지만 MySQL 8.0.20 이상에서는 outer join(안티 조인 및 세미 조인 포함)에도 해시 조인을 수행할 수 있게 됨에 따라 join buffer 를 사용할 수 있습니다
6. Conclusion
MySQL 8.0.18 버전 에서 오랜 동안 기다린 해시 조인이 드디어 추가가 되었습니다. 아래 performance 비교 내용으로 확인 하였을 때도 기존의 BNL 보다 더 성능이 좋다는것을 확인 할 수 있습니다 
mysqlserverteam.com/hash-join-in-mysql-8
MySQL 8.0.20 이상에서는 해시 조인을 사용하기 위해 조인에 적어도 하나의 동등 조인 조건이 포함될 필요가 없으며 outer join 에서도 해시 조인이 지원되게 됩니다 그러므로 MySQL 8 버전에서 해시조인까지 사용을 고려 한다면 8.0.20 버전 이상을 고려해야 할 필요가 있어 보입니다.
[참고] AWS Aurora for MySQL 2(MySQL ver 5.7 Compatible) 에서도 Hash Join 을 사용할 수 있습니다
(2.06 버전 부터 Hash Join 이 지원)
Aurora for MySQL 3 버전에서는 Hash Join optimizer 의 사용 활성화가 기본값이며, Aurora for MySQL 2 버전에서는 기본 설정값은 기능 미사용으로 되어있으로 SET optimizer_switch 을 통해 활성화 해서 사용해야 합니다.
7. Reference
Reference link
• dev.mysql.com/switchable-optimizations.html
• dev.mysql.com/optimizer-hints-table-level
• dev.mysql.com/hash-joins.html
• percona.com/understanding-hash-joins-in-mysql-8
• mysqlserverteam.com/hash-join-in-mysql-8
• aws.amazon.com/Aurora.HashJoin
연관된 글
관련된 다른 글
Principal DBA(MySQL, AWS Aurora, Oracle)
핀테크 서비스인 핀다에서 데이터베이스를 운영하고 있어요(at finda.co.kr)
Previous - 당근마켓, 위메프, Oracle Korea ACS / Fedora Kor UserGroup 운영중
Database 외에도 NoSQL , Linux , Python, Cloud, Http/PHP CGI 등에도 관심이 있습니다
purityboy83@gmail.com / admin@hoing.io
